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

任意の正の整数 $a$ に対して $a^p\equiv a$ であることを示す （そうすれば，$p$ と $a$ が互いに素なとき両辺を $a$ で割ってフェルマーの小定理がわかる）。

$a=1$ のとき，明らかに $a^{p}\equiv a$

また，二項定理を用いることで，

$(m+1)^p\\ =m^p+1+\displaystyle\sum_{k=1}^{p-1}{}_p\mathrm{C}_{k}m^k\\ \equiv m^p+1$

（→補足）

よって，$m^p \equiv m$ なら，$(m+1)^p\equiv m+1$

以上から数学的帰納法より，全ての $a$ に対して $a^p\equiv a$

方針で述べたことと，$a,2a,3a,\cdots(p-1)a$ は全て $p$ の倍数でないので，

$a,2a,3a\cdots (p-1)a$ を $p$ で割った余りを並べると $1$ から $p-1$ までが全て1回ずつ登場する。よって，

$a\cdot 2a\cdot 3a\cdot\cdots\cdot (p-1)a\equiv (p-1)!$

ここで，$(p-1)!$ は $p$ と互いに素なので両辺を $(p-1)!$ で割って，

$a^{p-1}\equiv 1$ を得る。

$p\geq 4$ のとき，

$a_{p-2}=2^{p-2}+3^{p-2}+6^{p-2}-1\equiv 0 \pmod{p}$ を示す。

$p$ と $6$ は互いに素なので，両辺を $6$ 倍した以下の式を示せば良い：

$3\cdot 2^{p-1}+2\cdot 3^{p-1}+6^{p-1}-6\equiv 0$

ところが，これはフェルマーの小定理より成立する。

よって，候補は $1,2,3$ のみ。 $2$ は $a_1=10$ の約数で，$3$ は $a_2=48$ の約数なので不適。答えは $1$ のみ。