Fermat's Little Theorem is an important result connecting prime numbers with modular exponentiation. If p is a prime number and a is an integer not divisible by p, then a^(p−1) ≡ 1 (mod p). An equivalent form states that a^p ≡ a (mod p) for every integer a. The theorem provides a powerful way to simplify large powers modulo a prime. For example, when calculating a^k modulo p, the exponent can often be reduced using the fact that a^(p−1) is congruent to 1 when p does not divide a. The theorem is also used in primality testing, modular inverse calculations, and cryptography. However, satisfying the theorem's congruence condition does not always prove that a number is prime, because some composite numbers can also satisfy related conditions for particular bases.
Fermat's Little Theorem
Fermat's Little Theorem states that if p is prime and p does not divide a, then a raised to the power p − 1 is congruent to 1 modulo p.
If p is prime and p ∤ a, then a^(p−1) ≡ 1 (mod p). Equivalently, a^p ≡ a (mod p).
Explanation
Variables
A
An integer base.
P
A prime number used as the modulus.
P − 1
The exponent appearing in the nonzero-residue form.
P ∤ a
The statement that p does not divide a.
Example or application
Problem
Verify Fermat's Little Theorem for a = 2 and p = 7.
Solution
Since 7 is prime and does not divide 2, the theorem applies. Calculate 2^(7−1) = 2^6 = 64. Since 64 = 9 × 7 + 1, we obtain 64 ≡ 1 (mod 7).
Answer
2^6 ≡ 1 (mod 7)
Text
Fermat's Little Theorem applies to a prime modulus. Its nonzero-residue form gives a^(p−1) ≡ 1 (mod p), while its equivalent general form gives a^p ≡ a (mod p) for every integer a.
Key Points
The modulus p must be prime.
The nonzero-residue form requires p not to divide a.
The expression a^(p−1) is congruent to 1 modulo p under the theorem's conditions.
The equivalent form a^p ≡ a (mod p) holds for every integer a when p is prime.
The theorem helps simplify large modular powers.
The theorem can support primality testing but does not by itself guarantee primality.
Applications
Simplifying large powers modulo prime numbers.
Finding modular inverses.
Developing primality tests.
Cryptographic algorithms.
Solving number-theoretic congruences.
Learning Outcomes
State Fermat's Little Theorem.
Identify the conditions required to apply it.
Use the theorem to simplify modular exponentiation.
Explain why the theorem alone cannot prove that every tested number is prime.
Practice Questions
Verify Fermat's Little Theorem for a = 3 and p = 5.
Calculate 2^10 modulo 11 using the theorem.
Find 3^20 modulo 7.
Explain why the condition p ∤ a matters in the nonzero-residue form.
Distinguish Fermat's Little Theorem from Fermat's Last Theorem.
Related Concepts
Prime Numbers
Modular Exponentiation
Euler's Theorem
Modular Inverses
Primality Testing
Common Mistakes
Applying the theorem with a composite modulus.
Using the nonzero-residue form when p divides a.
Confusing Fermat's Little Theorem with Fermat's Last Theorem.
Assuming that a number satisfying a Fermat congruence must be prime.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Kenneth H. Rosen, Elementary Number Theory and Its Applications
- David M. Burton, Elementary Number Theory
Suggest a correction or source · More in Arithmetic & Number Theory