Fermat’s Little Theorem

Statement

If $p$ is prime and $p\nmid a$, then \[ a^{p-1}\equiv 1 \pmod p. \] Equivalently, for any integer $a$, \[ a^p \equiv a \pmod p. \]

Proof

Let $p$ be prime and $p\nmid a$. Consider the nonzero residues \[ 1,2,\dots,p-1 \pmod p. \] Multiply by $a$: \[ a,2a,\dots,(p-1)a \pmod p. \] Claim: these are a permutation of $1,2,\dots,p-1$ mod $p$. If $ia\equiv ja\pmod p$, then $(i-j)a\equiv 0\pmod p$, and since $p\nmid a$, \[ i\equiv j\pmod p \Rightarrow i=j. \] Hence \[ a\cdot 2a\cdots (p-1)a \equiv 1\cdot 2\cdots (p-1) \pmod p. \] So \[ a^{p-1}(p-1)! \equiv (p-1)! \pmod p. \] Since $p\nmid (p-1)!$, cancel to get $a^{p-1}\equiv 1\pmod p$.