位数の性質と原始根の応用

$m$ を $n$ で割った商を $Q$，余りを $R$ とおく。

$1\equiv a^m=a^{nQ+R}=(a^{n})^Qa^R\equiv 1^Qa^R=a^R\pmod{p}$

途中で条件2を用いた。これより $a^R\equiv 1\pmod{p}$

ここで，$R$ は余りなので $0\leq R< n$ だが，もし $R\neq 0$ と仮定すると，上式は条件1に矛盾する。よって $R=0$ となり冒頭の「位数の性質」が示された。

素数 $p$ の原始根 $r$ をとってくる。つまり，$r$ の位数は $p-1$ である。すると，$r,\:r^2,\cdots,\:r^{p-1}$ を $p$ で割った余りは全て異なり $1$ から $p-1$ までを一巡するので，

$r\cdot r^2\cdots r^{p-1}\equiv 1\cdot 2\cdots p-1\pmod{p}$

よって，$r^m\equiv (p-1)!\pmod{p}$ (※)となる。ただし，$m=1+2+\cdots + (p-1)=\frac{p(p-1)}{2}$

一方，フェルマーの小定理より，$r^{2m}=r^{p(p-1)}\equiv 1\pmod{p}$ なので，

$(r^m-1)(r^m+1)$ は $p$ の倍数。

もし，$r^m\equiv 1\pmod{p}$ と仮定すると，位数の性質より $m$ は $p-1$ の倍数である。よって，$\dfrac{m}{p-1}=\dfrac{p}{2}$ は整数でなければならないが，これは $p$ が奇数であることに矛盾。

よって，$r^m\equiv -1\pmod{p}$ である。（※)と合わせてウィルソンの定理が証明された。