\(p\)を素数とする.整数\(a\)が\(a \not\equiv 0 \pmod p\)をみたすならば,\[a^{p-1} \equiv 1 \pmod p\]が成り立つ.
証明
\[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\]が得られる.
証明終