Fermat's Little Theorem

Fermat's Little Theorem is a working tool wherever modular exponentiation appears. In cryptography, RSA encryption and decryption correctness rests on Euler's Theorem, whose proof and structure directly generalize the permutation argument given here; the special prime case is used explicitly when RSA primes are chosen and when computing modular inverses via $a^{-1}\equiv a^{p-2}\pmod p$. In algorithm design, it underlies probabilistic primality testing (the Fermat primality test, and its refinement the Miller–Rabin test), which checks $a^{n-1}\bmod n$ for random bases $a$ to quickly rule out compositeness, accepting the theoretical caveat of pseudoprimes discussed above. In computer algebra and coding theory, fast modular exponentiation combined with Fermat's theorem gives efficient formulas for modular inverses and for evaluating polynomials over finite fields $\mathbb{F}_p$. In pure mathematics, it is the seed from which Euler's Theorem and the theory of the multiplicative order of an element — see The Order of an Element — grow, eventually leading to the structure theorem that the multiplicative group of nonzero residues mod a prime is cyclic.

Ask the tutor: How does the permutation argument used here generalize to prove Euler's Theorem for a composite modulus?

Fix a prime $p$ and think of multiplication by $a$ (with $p\nmid a$) as a function acting on the set of nonzero residues $\{1,2,\dots,p-1\}$ modulo $p$. The claim is that this function does nothing more than shuffle the set: every nonzero residue is hit exactly once. This is because if $a\cdot x \equiv a\cdot y \pmod p$ then, since $a$ has a modular inverse mod $p$ (as $\gcd(a,p)=1$), we can cancel $a$ to get $x\equiv y$. So the map $x \mapsto ax \bmod p$ is injective on a finite set, hence a bijection — a permutation of $\{1,\dots,p-1\}$. Now multiply together all the outputs of this permutation. Since it is just a reshuffling, the product of the outputs equals the product of the inputs:

The left side is $a^{p-1}\,(p-1)!$ and the right side is $(p-1)!$. Since $p$ is prime and $(p-1)!$ is a product of numbers each less than $p$, none of its factors is divisible by $p$, so $(p-1)!$ is invertible mod $p$ and can be cancelled — leaving exactly $a^{p-1}\equiv 1\pmod p$. The picture below shows this shuffling concretely for $p=7$, $a=3$.

The second form, $a^p\equiv a\pmod p$, is really the same statement dressed for all integers at once: if $p\mid a$ then both sides are $0\pmod p$ trivially, and if $p\nmid a$ we may multiply the first form by $a$. Intuitively, the two statements say the same thing about a prime modulus; the difference is only whether you insist on cancelling the common factor $a$ first.

Example 1 — computing a genuinely large power. Compute $7^{222} \bmod 13$. Here $p=13$ is prime and $\gcd(7,13)=1$, so Fermat's Little Theorem gives $7^{12}\equiv 1 \pmod{13}$. Divide the exponent: $222 = 18\cdot 12 + 6$, so

Now compute $7^6 \bmod 13$ directly by repeated squaring:

So $7^{222}\equiv 12 \equiv -1 \pmod{13}$. As a sanity check note $13\mid 78$ so $90-78=12$ is correct, and $12<13$ so it is reduced. Without Fermat's theorem this would require handling a $222$-fold multiplication; with it, the problem collapses to a small computation.

Example 2 — using Fermat's theorem to prove a divisibility statement. Show that $n^{13} \equiv n \pmod{2730}$ for every integer $n$. First factor $2730 = 2\cdot 3\cdot 5\cdot 7\cdot 13$, a product of distinct primes. By the Chinese Remainder Theorem, it suffices to show $n^{13}\equiv n$ modulo each of $2,3,5,7,13$ separately, since if $n^{13}-n$ is divisible by each of five pairwise coprime numbers it is divisible by their product.

• Mod $2$: by Fermat's theorem (form B) with $p=2$, $n^2\equiv n\pmod 2$, so $n^{13} =

(n^2)^6\cdot n \equiv n^6\cdot n=n^7\pmod2$; repeating,$n^7 \equiv n \pmod 2$(since squaring preserves$n\equiv n^2$, any power of$n$is$\equiv n$mod$2$once$n^2\equiv n$: indeed$n^k \equiv n$for all$k\ge1$by induction, since$n^{k+1}=n\cdot n^k \equiv n\cdot n = n^2 \equiv n$). So$n^{13}\equiv n\pmod 2$.

• Mod $3$: form (B) with $p=3$ gives $n^3\equiv n\pmod 3$. Then $n^{13} = (n^3)^4\cdot n$.

Since $n^3\equiv n$, induction as above gives $n^k\equiv n\pmod3$ for all $k\ge 1$ ($n^{k+1}=n\cdot n^k\equiv n\cdot n=n^2$, and one checks separately $n^2\equiv n\pmod3$ fails in general — instead argue directly: $13 = 3\cdot 4+1$, and since $n^{3}\equiv n$, we get $n^{2\cdot3+1}=n^{3}\cdot n^3\cdot n \equiv n\cdot n\cdot n = n^3\equiv n$; more simply, $n^{13}=(n^3)^4\cdot n\equiv n^4\cdot n=n^5=(n^3)\cdot n^2\equiv n\cdot n^2=n^3\equiv n\pmod3$). So $n^{13}\equiv n\pmod 3$.

• Mod $5$: form (B) with $p=5$ gives $n^5\equiv n\pmod5$, and if $5\nmid n$ form (A) gives

$n^4\equiv1$, so $n^{13}=n^{4\cdot3}\cdot n \equiv n \pmod5$ when $5\nmid n$; if $5\mid n$ both sides are $0\bmod5$. Either way $n^{13}\equiv n\pmod5$.

• Mod $7$: if $7\mid n$, both sides $\equiv 0$. If $7\nmid n$, form (A) with $p=7$ gives

$n^6\equiv1\pmod7$, so $n^{13} = n^{6\cdot2}\cdot n \equiv n\pmod 7$.

• Mod $13$: if $13\mid n$, both sides are $0$. If $13\nmid n$, form (A) with $p=13$ gives

$n^{12}\equiv 1\pmod{13}$, and $13 = 12\cdot1+1$, so $n^{13} = n^{12}\cdot n \equiv n \pmod{13}$. All five congruences hold for every integer $n$, so by the Chinese Remainder Theorem, $n^{13}\equiv n \pmod{2730}$ for every integer $n$. This is a genuine, checkable identity: e.g. $n=2$ gives $2^{13}=8192 = 3\cdot2730+2$, confirming $8192\equiv 2\pmod{2730}$.