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

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

$k \cdot a \equiv r_k ~(\mbox{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 \Pi_{k=1}^{p-1} r_k ~(\mbox{mod}~~ p).$ (2)

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

$(i-j) a \equiv (r_i -r_j)~(\mbox{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)! = \Pi_{k=1}^{p-1} r_k$ ,

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

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

が示される．