Fermat's Little Theorem
Statement
Equivalently, if p∤a: \(a^{{p-1}}\equiv1\pmod{{p}}\).
Examples
Example 1. 2¹⁰ mod 11.
Solution. By FLT, 2¹⁰≡1 (mod 11).
In Depth
Fermat's little theorem is a cornerstone of number theory with direct applications to primality testing and cryptography. The Miller–Rabin primality test is a probabilistic algorithm based on a strengthening of Fermat's theorem: if \(n\) is prime, then for any \(a\) coprime to \(n\), either \(a^d\equiv1\) or \(a^{2^r d}\equiv-1\pmod{n}\) for some \(r\).
Carmichael numbers are composite integers \(n\) satisfying \(a^{n-1}\equiv1\pmod{n}\) for all \(a\) coprime to \(n\) — they fool the naive Fermat primality test. The smallest is 561=3·11·17. The Miller–Rabin test is not fooled by Carmichael numbers.
Euler's generalization: \(a^{\varphi(n)}\equiv1\pmod{n}\) for \(\gcd(a,n)=1\). This is the mathematical basis of RSA decryption: the decryption exponent \(d\) satisfies \(ed\equiv1\pmod{\varphi(n)}\), so \((m^e)^d=m^{ed}\equiv m\pmod{n}\).
Further Reading & Context
Fermat's little theorem: if \(p\) is prime and \(\gcd(a,p)=1\), then \(a^{p-1}\equiv1\pmod{p}\). Equivalently, \(a^p\equiv a\pmod{p}\) for all \(a\). The proof uses the fact that \(\{a,2a,\ldots,(p-1)a\}\) is a permutation of \(\{1,2,\ldots,p-1\}\) modulo \(p\).
The Fermat primality test: if \(a^{n-1}\not\equiv1\pmod{n}\) for some \(a\) with \(\gcd(a,n)=1\), then \(n\) is composite. The test is fast but not definitive — Carmichael numbers pass for all valid \(a\). The Miller–Rabin test strengthens this by also checking square roots of 1.
Euler's generalization: \(a^{\phi(n)}\equiv1\pmod{n}\) for \(\gcd(a,n)=1\). This is the basis of RSA: with \(n=pq\) and \(ed\equiv1\pmod{\phi(n)}\), we have \(m^{ed}=(m^{\phi(n)})^k\cdot m^r\equiv m\pmod{n}\) (where \(ed=k\phi(n)+r\) with \(r=1\)).
Wilson's theorem complements Fermat's: \((p-1)!\equiv-1\pmod{p}\) iff \(p\) is prime. Together, these characterize primes via modular arithmetic. Wilson's theorem is impractical for primality testing but elegant theoretically.
Applications in combinatorics: Fermat's little theorem proves that \(\binom{p}{k}\equiv0\pmod{p}\) for \(0