Fermat's Little Theorem
Holds when p is prime and gcd(a,p)=1.
Formula
Variables
Example
For p = 5, a = 2: 2⁴ = 16 ≡ 1 (mod 5). ✓
How it works
Fermat's Little Theorem says that if p is prime and a is not divisible by p, then raising a to the power p−1 gives a number that is congruent to 1 modulo p. One way to understand this is that multiplication by a nonzero number modulo a prime just permutes the nonzero residue classes, so the product of all nonzero residues stays the same up to a factor of a^{p−1}. This is a key structural fact about arithmetic modulo primes, and it is often used to simplify large powers and prove divisibility results.
When to use it
Use this theorem whenever you need to reduce a large exponent modulo a prime, especially in modular arithmetic problems in algebra, cryptography, or contest number theory. It is also useful for finding modular inverses, since a^{p-2} is the inverse of a modulo p when p is prime and gcd(a,p)=1.
Worked example, step by step
Take p = 7 and a = 3. Since gcd(3, 7) = 1, Fermat's Little Theorem applies. We need to check that 3^(7-1) = 3^6 is congruent to 1 modulo 7. 3^2 = 9 ≡ 2 (mod 7) 3^4 = (3^2)^2 ≡ 2^2 = 4 (mod 7) 3^6 = 3^4 · 3^2 ≡ 4 · 2 = 8 ≡ 1 (mod 7) Therefore, 3^6 ≡ 1 (mod 7), as expected.
Common mistakes to avoid
- Using the theorem when p is not prime
- Forgetting the condition gcd(a, p)=1, especially when a is a multiple of p
- Confusing the theorem with the statement a^p ≡ a (mod p), which is a related but different result
Did You Know?
Fermat's little theorem is a workhorse of primality testing and the RSA encryption that secures the web.
Share this formula
More in Number Theory
View allEuclidean Algorithm
BasicRecursively finds the greatest common divisor.
Modular Congruence
Basica and b have the same remainder when divided by m.
Euler's Totient
AdvancedCounts integers up to n coprime to n.
Prime Number Theorem
AdvancedApproximates the number of primes below x.
LCM from GCD
BasicLeast common multiple via the greatest common divisor.
Sum of First n Integers
BasicClosed form for the sum of the first n natural numbers.