 Fermat little theorem

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]