Fermat's little theorem

Statement

Let $p$ be a prime number and let $a$ be an integer that $p$ does not divide. Then $a^{p-1} \equiv 1 \pmod p$.

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.

Explanations

L1 human

Take $p = 5$ and $a = 2$: $2^4 = 16 = 3 \cdot 5 + 1$, so $2^4 \equiv 1 \pmod 5$. The theorem says that this always happens for a prime $p$ and a number $a$ that $p$ does not divide. It lets you reduce large powers: $2^{100} = (2^4)^{25} \equiv 1 \pmod 5$.