証明
\[1a,~2a,~3a,~\cdots,(p-1)a\]を考える．これらを\(p\)で割った余りはすべて異なることを以下に示す．\(p\)で割って余りが等しくなるような\(2\)数が存在すると仮定し，それらを\(ia,ja~(1 \leq i,j \leq p-1,~i\neq j )\)とおけば\[ia\equiv ja \pmod p \Longleftrightarrow (i-j)a\equiv 0 \pmod p\]が得られるが，\(a \not\equiv 0 \pmod p\)により\(i-j \equiv 0 \pmod p\)でなくてはならない．しかし，\(1 \leq i,j \leq p-1\)であったから，\(i-j\)は\(p-1\)以下であり，矛盾する．
したがって\(1a,~2a,~3a,~\cdots,(p-1)a\)を\(p\)で割った余りはすべて異なる．また\(a\not \equiv 0 \pmod p\)よりこれらは\(p\)では割り切れない（\(p\)で割っても余りが\(0\)にはならない）から，\(1a,~2a,~3a,~\cdots,(p-1)a\)を\(p\)で割ると余りとして\(1,2,\cdots,p-1\)がそれぞれ\(1\)回ずつ現れることになる．これを\[1a\equiv n_{1}~,2a\equiv n_{2}~,~\cdots~,(p-1)a\equiv n_{p-1}\]と表すことにする（ただし\((n_{1},~n_{2},~\cdots~,n_{p-1})\)は\(1,2,~\cdots~,p-1\)の適当な順列）．辺々掛けることで
\begin{align*}
&1\cdot 2 \cdot \cdots \cdot (p-1) a^{p-1}\equiv n_{1}n_{2}\cdots n_{p-1} \pmod p \\
\Longleftrightarrow ~&(p-1)! a^{p-1}\equiv (p-1)! \pmod p
\end{align*}ここで，\(\gcd(p,(p-1)!)=1\)であるから（実際，\(p\)と\((p-1)!\)に共通な素因数が存在すると仮定すると，\(p\)が素数であることからその共通の素因数は\(p\)であるが，\(1,2,\cdots,p-1\)はいずれも\(p\)では割り切れず，矛盾する），両辺を\((p-1)!\)で割ることができて\[a^{p-1} \equiv 1 \pmod p\]が得られる．
証明終