Fermat's little theorem

Remarks

An equivalent form is Fermat's little theorem in the form a^p = a: $a^p \equiv a \pmod p$ for each integer $a$. In the ring $\mathbb{Z}/p\mathbb{Z}$, the statement is $x^{p-1} = 1$ for each nonzero $x$. It follows from Lagrange's theorem for the multiplicative group of $\mathbb{Z}/p\mathbb{Z}$, which has $p - 1$ elements. Euler's theorem generalizes the result to each modulus $n$. The converse is false. For example, $2^{340} \equiv 1 \pmod{341}$, but $341 = 11 \cdot 31$. See Fermat pseudoprime.

History

Fermat stated the theorem in a letter of 1640, without a proof. Euler published the first known proof in 1736. Leibniz had a proof earlier, in an unpublished manuscript.