Fermat’s little theorem is a fundamental result in number theory describing powers of integers modulo a prime number. It states that, for every prime and every integer ,
Equivalently, if does not divide , then
Named after Pierre de Fermat, the theorem is a basic tool in modular arithmetic, with applications to divisibility, the computation of large powers, modular inverses, and tests for primality. Its converse is false: some composite integers satisfy the corresponding congruence for particular bases, and some do so for every base relatively prime to them.
Statement and interpretation
The notation means that divides . Thus the theorem’s first form says that
for every integer .
The two common forms have slightly different hypotheses:
- Universal form: If is prime, then for every integer .
- Nonzero-residue form: If is prime and , then .
The restriction in the second form is essential. If , then , not .
To pass from the universal form to the nonzero-residue form, one cancels modulo ; this is valid because is relatively prime to . Conversely, multiplying the nonzero-residue form by gives the universal form when , while the case is immediate.
For example, taking and gives
and consequently
History
Fermat stated the result in a letter to Bernard Frénicle de Bessy dated 18 October 1640, without supplying a proof. Leonhard Euler later published a proof in the eighteenth century and developed the more general result now known as Euler’s theorem.
The adjective “little” distinguishes this result from Fermat’s Last Theorem, which concerns the absence of positive integer solutions to for integers . Despite their shared attribution, the two theorems address different problems and require very different methods of proof.
Proofs
Permutation of nonzero residues
Assume is prime and . Consider the nonzero residues modulo :
Multiplying each by produces
None is congruent to zero modulo . Moreover, no two are congruent: if
then . Since , it follows that , which forces when .
Thus multiplication by gives a permutation of the nonzero residues. Their products are therefore congruent:
Here is a factorial. None of its factors is divisible by , so it can be cancelled modulo , yielding
This proof highlights a key property of prime moduli: every nonzero residue has a multiplicative inverse.
Binomial proof
For a prime , every binomial coefficient
is divisible by . The binomial theorem therefore gives
Setting yields
Starting from , mathematical induction establishes for every nonnegative integer . Every integer is congruent modulo to one of , so the statement follows for all integers.
Group-theoretic proof
The nonzero residues modulo form a multiplicative group with elements. In group theory, Lagrange’s theorem implies that the order of any element divides the number of elements in a finite group. Hence every nonzero residue satisfies
in that group.
This presents Fermat’s little theorem as a special case of a general fact about finite groups.
Applications
Reducing large exponents
If , exponents can be reduced modulo . Writing
gives
For example, because ,
This reduction does not apply without qualification when . In that case, every positive power of is congruent to zero modulo ; reducing a positive exponent to zero would incorrectly replace it by .
Computing modular inverses
For , the theorem gives
Thus the multiplicative inverse of modulo is
For instance,
consistent with .
The power can be computed efficiently by repeated squaring. Another method for finding modular inverses uses the extended Euclidean algorithm, which also works for composite moduli whenever the number and modulus are relatively prime.
Primality testing
The theorem provides a necessary condition for primality. If an integer has a base , relatively prime to , for which
then is composite.
This is the basis of the Fermat primality test. A base that violates the congruence is a conclusive witness to compositeness. A base that satisfies it, however, does not prove that is prime.
Modular exponentiation makes such tests practical even for large integers. Stronger methods, including the Miller–Rabin primality test, examine additional consequences of prime-modulus arithmetic to detect composites that a Fermat test may miss.
The failure of the converse
Fermat pseudoprimes
A composite integer satisfying
for a specified base relatively prime to is called a Fermat pseudoprime to base .
For example,
is composite, but
Since , this implies
Thus passes the Fermat test to base .
Carmichael numbers
A Carmichael number is a composite positive integer for which
for every integer relatively prime to . The smallest example is
Consequently, testing additional relatively prime bases cannot make the Fermat congruence alone a definitive primality criterion. A base sharing a nontrivial factor with can reveal compositeness through a greatest common divisor calculation, but that is distinct from passing or failing the coprime-base congruence.
Generalizations and algebraic meaning
Euler’s theorem
Euler’s theorem extends the result from prime moduli to arbitrary positive integer moduli :
where , Euler’s totient function, counts the residue classes modulo that are relatively prime to .
For a prime , every integer from through is relatively prime to , so , recovering Fermat’s little theorem.
The exponent need not be the smallest positive exponent producing . The smallest such exponent for a particular , called its multiplicative order modulo , divides . For example, , so the order of modulo is , rather than .
Finite fields
The residue classes modulo form a finite field, denoted . Fermat’s little theorem says that every element of this field satisfies
More generally, in any finite field with elements,
for every element , because its nonzero elements form a multiplicative group of order .
There is an important distinction between these statements. In a field with elements, the map is an automorphism, called the Frobenius automorphism, but it need not fix every element when . It is the map that fixes every element of that field.