Mathwords logoMathwords

Fermat's Little Theorem — Definition, Formula & Examples

Fermat's Little Theorem states that if pp is a prime number and aa is any integer not divisible by pp, then ap−1a^{p-1} leaves a remainder of 1 when divided by pp.

Let pp be a prime and a∈Za \in \mathbb{Z} with gcd⁡(a,p)=1\gcd(a, p) = 1. Then ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}. An equivalent formulation, valid for all integers aa (including multiples of pp), is ap≡a(modp)a^{p} \equiv a \pmod{p}.

Key Formula

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}
Where:
  • aa = Any integer not divisible by $p$
  • pp = A prime number

How It Works

The theorem gives you a shortcut for computing large powers modulo a prime. Instead of calculating an mod pa^n \bmod p directly, you reduce the exponent nn modulo p−1p - 1, since ap−1≡1a^{p-1} \equiv 1. Specifically, write n=q(p−1)+rn = q(p-1) + r; then an≡ar(modp)a^n \equiv a^r \pmod{p}. This dramatically shrinks the computation. The theorem also underpins primality testing algorithms and the RSA cryptosystem.

Worked Example

Problem: Compute 3100 mod 73^{100} \bmod 7.
Step 1: Since 7 is prime and 3 is not divisible by 7, Fermat's Little Theorem gives us:
36≡1(mod7)3^{6} \equiv 1 \pmod{7}
Step 2: Reduce the exponent 100 modulo 6 (since p−1=6p - 1 = 6):
100=16×6+4,so 100≡4(mod6)100 = 16 \times 6 + 4, \quad \text{so } 100 \equiv 4 \pmod{6}
Step 3: Replace the exponent with the remainder and compute:
3100≡34=81≡81−11×7=81−77=4(mod7)3^{100} \equiv 3^{4} = 81 \equiv 81 - 11 \times 7 = 81 - 77 = 4 \pmod{7}
Answer: 3100≡4(mod7)3^{100} \equiv 4 \pmod{7}

Why It Matters

Fermat's Little Theorem is foundational to RSA encryption, where messages are encoded and decoded using modular exponentiation with large primes. It also forms the basis of the Fermat primality test, a fast probabilistic method for checking whether a number is prime. In an abstract algebra course, it appears as a special case of Lagrange's theorem applied to the multiplicative group Zp∗\mathbb{Z}_p^*.

Common Mistakes

Mistake: Applying the theorem when the modulus is not prime (e.g., using a8≡1(mod9)a^{8} \equiv 1 \pmod{9}).
Correction: Fermat's Little Theorem requires pp to be prime. For composite moduli, use Euler's theorem with the Euler totient function ϕ(n)\phi(n) instead.