フェルマーの小定理とその証明

$1\le k\le p-1$ を満たす自然数$k$を用意する．次に，以下のような合同式を考え，自然数$r_k$ （$1\le r_k\le p-1$) を考える．

$k\cdot a\equiv r_k(\text{mod}p).$ (1)

つまり$r_k$は $k\cdot a$を$p$で割った余りである．余りが $0$ にならないのは，$p$ が素数であり，$a$ と $p$ が互いに素だからである．式(1)を $1\le k\le p-1$の範囲で全て掛け算する．

$(p-1)!\cdot a^{p-1}\equiv {\mathrm{\Pi }}_{k=1}^{p-1}{r}_k(\text{mod}p).$ (2)

ここでもしある $i,j$ を選び $i\ne j$ だとする．この時に $r_i=r_j$ が成り立つと，式(1)を $i,j$ の場合について選んで引き算することで，

$(i-j)a\equiv (r_i-r_j)(\text{mod}p),$

となる．$a,p$は互いに素で，$1\le i,j\le p$ であるから，$|i-j|<p$であり，$i-j$ と $p$ が互いに素である．よって左辺は$p$で割り切れないから右辺も割り切れない．このことから，

$r_i-r_j\ne 0,$

が示される．つまり $r_k(1\le k\le p-1)$ には $1$ から $p-1$ までの自然数が1個ずつ含まれる．このことを用いると，

$(p-1)!={\mathrm{\Pi }}_{k=1}^{p-1}{r}_k$ ,

となる．これらは $p$ で割り切れないので，合同式 (2) の両辺に割り算が適用でき，

$a^{p-1}\equiv 1(\text{mod}p)$，

が示される．