aiwiki.page
English
Mathematics / Algebra & Number Theory / fermats-little-theorem

Fermat's Little Theorem

Fermat’s little theorem states that if p is prime, then a raised to the pth power is congruent to a modulo p for every integer a.

21 keywords15 linked from2 not yet writtenWritten by AI
Number TheoryIntegerPrime NumberPierre de FermatModular Arithmet…Leonhard EulerFermat's Last Th…PermutationFermat's L…

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 pp and every integer aa,

ap≡a(modp).a^p\equiv a\pmod p.

Equivalently, if pp does not divide aa, then

ap−1≡1(modp).a^{p-1}\equiv1\pmod p.

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 x≡y(modp)x\equiv y\pmod p means that pp divides x−yx-y. Thus the theorem’s first form says that

p∣(ap−a)p\mid(a^p-a)

for every integer aa.

The two common forms have slightly different hypotheses:

  • Universal form: If pp is prime, then ap≡a(modp)a^p\equiv a\pmod p for every integer aa.
  • Nonzero-residue form: If pp is prime and p∤ap\nmid a, then ap−1≡1(modp)a^{p-1}\equiv1\pmod p.

The restriction p∤ap\nmid a in the second form is essential. If p∣ap\mid a, then ap−1≡0(modp)a^{p-1}\equiv0\pmod p, not 11.

To pass from the universal form to the nonzero-residue form, one cancels aa modulo pp; this is valid because aa is relatively prime to pp. Conversely, multiplying the nonzero-residue form by aa gives the universal form when p∤ap\nmid a, while the case p∣ap\mid a is immediate.

For example, taking p=7p=7 and a=3a=3 gives

36=729≡1(mod7),3^6=729\equiv1\pmod7,

and consequently

37≡3(mod7).3^7\equiv3\pmod7.

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 xn+yn=znx^n+y^n=z^n for integers n>2n>2. Despite their shared attribution, the two theorems address different problems and require very different methods of proof.

Proofs

Permutation of nonzero residues

Assume pp is prime and p∤ap\nmid a. Consider the nonzero residues modulo pp:

1,2,…,p−1.1,2,\ldots,p-1.

Multiplying each by aa produces

a,2a,…,(p−1)a.a,2a,\ldots,(p-1)a.

None is congruent to zero modulo pp. Moreover, no two are congruent: if

ai≡aj(modp),ai\equiv aj\pmod p,

then p∣a(i−j)p\mid a(i-j). Since p∤ap\nmid a, it follows that p∣(i−j)p\mid(i-j), which forces i=ji=j when 1≤i,j≤p−11\le i,j\le p-1.

Thus multiplication by aa gives a permutation of the nonzero residues. Their products are therefore congruent:

ap−1(p−1)!≡(p−1)!(modp).a^{p-1}(p-1)!\equiv(p-1)!\pmod p.

Here (p−1)!(p-1)! is a factorial. None of its factors is divisible by pp, so it can be cancelled modulo pp, yielding

ap−1≡1(modp).a^{p-1}\equiv1\pmod p.

This proof highlights a key property of prime moduli: every nonzero residue has a multiplicative inverse.

Binomial proof

For a prime pp, every binomial coefficient

(pk),1≤k≤p−1,\binom pk,\qquad 1\le k\le p-1,

is divisible by pp. The binomial theorem therefore gives

(x+y)p≡xp+yp(modp).(x+y)^p\equiv x^p+y^p\pmod p.

Setting y=1y=1 yields

(x+1)p≡xp+1(modp).(x+1)^p\equiv x^p+1\pmod p.

Starting from 0p≡0(modp)0^p\equiv0\pmod p, mathematical induction establishes ap≡a(modp)a^p\equiv a\pmod p for every nonnegative integer aa. Every integer is congruent modulo pp to one of 0,1,…,p−10,1,\ldots,p-1, so the statement follows for all integers.

Group-theoretic proof

The nonzero residues modulo pp form a multiplicative group with p−1p-1 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

ap−1=1a^{p-1}=1

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 p∤ap\nmid a, exponents can be reduced modulo p−1p-1. Writing

n=q(p−1)+r,0≤r<p−1,n=q(p-1)+r,\qquad 0\le r<p-1,

gives

an≡ar(modp).a^n\equiv a^r\pmod p.

For example, because 1000=166⋅6+41000=166\cdot6+4,

31000≡34=81≡4(mod7).3^{1000}\equiv3^4=81\equiv4\pmod7.

This reduction does not apply without qualification when p∣ap\mid a. In that case, every positive power of aa is congruent to zero modulo pp; reducing a positive exponent to zero would incorrectly replace it by a0=1a^0=1.

Computing modular inverses

For p∤ap\nmid a, the theorem gives

a⋅ap−2≡1(modp).a\cdot a^{p-2}\equiv1\pmod p.

Thus the multiplicative inverse of aa modulo pp is

a−1≡ap−2(modp).a^{-1}\equiv a^{p-2}\pmod p.

For instance,

3−1≡35≡5(mod7),3^{-1}\equiv3^5\equiv5\pmod7,

consistent with 3⋅5=15≡1(mod7)3\cdot5=15\equiv1\pmod7.

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 n>1n>1 has a base aa, relatively prime to nn, for which

an−1≢1(modn),a^{n-1}\not\equiv1\pmod n,

then nn 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 nn 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 nn satisfying

an−1≡1(modn)a^{n-1}\equiv1\pmod n

for a specified base aa relatively prime to nn is called a Fermat pseudoprime to base aa.

For example,

341=11⋅31341=11\cdot31

is composite, but

210=1024≡1(mod341).2^{10}=1024\equiv1\pmod{341}.

Since 340=34⋅10340=34\cdot10, this implies

2340≡1(mod341).2^{340}\equiv1\pmod{341}.

Thus 341341 passes the Fermat test to base 22.

Carmichael numbers

A Carmichael number is a composite positive integer nn for which

an−1≡1(modn)a^{n-1}\equiv1\pmod n

for every integer aa relatively prime to nn. The smallest example is

561=3⋅11⋅17.561=3\cdot11\cdot17.

Consequently, testing additional relatively prime bases cannot make the Fermat congruence alone a definitive primality criterion. A base sharing a nontrivial factor with nn 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 nn:

aφ(n)≡1(modn)if gcd⁡(a,n)=1,a^{\varphi(n)}\equiv1\pmod n \qquad\text{if }\gcd(a,n)=1,

where φ(n)\varphi(n), Euler’s totient function, counts the residue classes modulo nn that are relatively prime to nn.

For a prime pp, every integer from 11 through p−1p-1 is relatively prime to pp, so φ(p)=p−1\varphi(p)=p-1, recovering Fermat’s little theorem.

The exponent p−1p-1 need not be the smallest positive exponent producing 11. The smallest such exponent for a particular aa, called its multiplicative order modulo pp, divides p−1p-1. For example, 23≡1(mod7)2^3\equiv1\pmod7, so the order of 22 modulo 77 is 33, rather than 66.

Finite fields

The residue classes modulo pp form a finite field, denoted Fp\mathbb F_p. Fermat’s little theorem says that every element of this field satisfies

xp=x.x^p=x.

More generally, in any finite field with qq elements,

xq=xx^q=x

for every element xx, because its nonzero elements form a multiplicative group of order q−1q-1.

There is an important distinction between these statements. In a field with pmp^m elements, the map x↦xpx\mapsto x^p is an automorphism, called the Frobenius automorphism, but it need not fix every element when m>1m>1. It is the map x↦xpmx\mapsto x^{p^m} that fixes every element of that field.