Fermat little theorem ($a^{p-1}\equiv 1(\mathrm{mod}p)$)

For a prime number $p$ and an integer $a$ not divisible by $p$, Fermat's little theorem states the modular congruenceEquivalently, for every integer $a$, including $a<0$ and multiples of $p$,The first formulation follows from the second by multiplying by a modular multiplicative inverse of $a$. Conversely, multiply the first by $a$ when $p\nmid a$; when $p\mid a$, both sides of the second are zero modulo $p$. The divisibility condition in the first formulation is essential.^[ref]

For $p=7$, $3^6=729=7\cdot 104+1$, so $3^6\equiv 1(\mathrm{mod}7)$ and $3^7\equiv 3(\mathrm{mod}7)$. Also $(-2{)}^6=64\equiv 1(\mathrm{mod}7)$, while $7^6\equiv 0(\mathrm{mod}7)$: a zero residue class cannot satisfy the first formulation. It does satisfy $7^7\equiv 7\equiv 0(\mathrm{mod}7)$. A failure at a zero residue class therefore says nothing against a candidate's being a prime number.

The prime number $p=2$ is included. Its only nonzero residue class is one: every odd integer $a$ satisfies $a^{2-1}=a\equiv 1(\mathrm{mod}2)$. Every integer also satisfies $a^2\equiv a(\mathrm{mod}2)$, because $a(a-1)$ is even. Testing the first formulation with an even integer would violate its hypothesis.

The useful surprise is that every nonzero residue class returns to one at the same exponent $p-1$, although its shortest return can be earlier. This gives exponent reduction for units: for a nonnegative integer $k$, $a^k\equiv a^{k\mathrm{mod}(p-1)}(\mathrm{mod}p)$ when $p\nmid a$. It also computes a modular multiplicative inverse as $a^{p-2}$ modulo $p$, including $p=2$. Repeated squaring makes these modular exponentiations practical.

In group theory, the nonzero residue classes form the multiplicative group of integers modulo n with $n=p$, of group order $p-1$. Lagrange's theorem says that the multiplicative order of $a$ divides $p-1$, giving the guaranteed return. Euler's theorem extends this to a general integer modulus $n$, using the units and Euler's totient function $\phi (n)$; the Carmichael function gives the least common return exponent for all units. A nonzero residue class modulo a composite number need not be a unit.

Leonhard Euler's paper presented in 1732 and published in 1738 states a historical formulation: Theorem 1 says that powers with exponent $n-1$ leave zero or one upon division by a prime number $n$. The preceding discussion states the difference-of-powers version and explicitly says that he does not have its proof.^[ref]

For a prime number $p$ and $p\nmid a$, multiplication by $a$ gives a permutation of the $p-1$ nonzero residue classes. For $a=3$ modulo seven, the representatives $1,2,3,4,5,6$ map to $3,6,2,5,1,4$: the same collection in a different order. Repeating this permutation from one visits all six representatives before returning.

For $a=2$ modulo seven, the permutation cycles are instead $(1,2,4)$ and $(3,6,5)$. The powers of two visit only the permutation cycle containing one, so their multiplicative order is three. Both permutation cycles return after three steps; applying the permutation six times still fixes every nonzero residue class. Fermat's little theorem guarantees a return at six, not that every base visits every nonzero residue class.

More generally, every permutation cycle of this map has length equal to the multiplicative order of $a$: starting at a nonzero residue class $x$, a return means $a^{k}x\equiv x(\mathrm{mod}p)$, and its modular multiplicative inverse allows cancellation of $x$. Thus the $p-1$ nonzero residue classes split into equal-length permutation cycles, which also explains the divisibility of the multiplicative order into $p-1$.

The product argument gives a short proof outline. Since multiplication by $a$ is a permutation of the nonzero residue classes,Every factor is a unit, so their product has a modular multiplicative inverse and can be cancelled. This leaves $a^{p-1}\equiv 1(\mathrm{mod}p)$. The whole argument works for $p=2$, where the product is just one.^[ref]

A Fermat witness for an integer $n>1$ is a nonzero residue class represented by $1\le a<n$ for which $a^{n-1}\not\equiv 1(\mathrm{mod}n)$. It proves that $n$ is a composite number by Fermat's little theorem. Here the definition includes nonunits; some conventions restrict Fermat witnesses to bases coprime to $n$. The Fermat primality test can first compute the greatest common divisor: if $1<\gcd (a,n)<n$, it already has a proper factor. A zero residue class is excluded. ^[ref]

For the Fermat primality test, a passing base satisfies $a^{n-1}\equiv 1(\mathrm{mod}n)$. Passing proves only this modular congruence, not that $n$ is a prime number. An odd composite number that passes a coprime base is a Fermat pseudoprime to that base. A Carmichael number passes every coprime base, so even testing all the units would not certify that $n$ is a prime number. ^[ref]

This small table uses only the bases $2,3,5,11$, each reduced modulo $n$ first. A numeric entry is $a^{n-1}\mathrm{mod}n$: one passes, while any other numeric entry gives a Fermat witness. A "factor" entry records a proper greatest common divisor and stops before modular exponentiation. The prime/composite classification is independently established by trial division or the displayed prime factorization, not by the passing entries. These four bases are illustrative, with no asserted universal coverage or error probability.

For $341=11\cdot 31$, $\gcd (2,341)=1$ and $2^{10}=1024=3\cdot 341+1$, so $2^{340}=(2^{10}{)}^{34}\equiv 1(\mathrm{mod}341)$. Yet $\gcd (3,341)=1$ and $3^{340}\equiv 56(\mathrm{mod}341)$, so three is a Fermat witness. One coprime base passes and another fails: being a Fermat pseudoprime depends on the base. Choosing eleven instead reveals the proper factor through $\gcd (11,341)=11$.

For $561=3\cdot 11\cdot 17$, every coprime base passes: each of $2,10,16$ divides $560$, so Fermat's little theorem gives $a^{560}\equiv 1$ modulo each prime factor; the Chinese remainder theorem combines the three modular congruences. Equivalently, the Carmichael function gives $\lambda (561)=80\mid 560$. Bases two and five have greatest common divisor one and pass, but $\gcd (3,561)=3$, $\gcd (11,561)=11$ and $\gcd (17,561)=17$ expose factors. The qualification "coprime" is therefore crucial even for a Carmichael number.

The Fermat primality test is useful because a Fermat witness can prove compositeness using repeated squaring without finding a factor. Its failure to certify a passing candidate motivates stronger primality testing methods such as the Miller-Rabin primality test.