フェルマーの小定理
フェルマーの小定理とは、素数の性質についての定理であり、実用面でもRSA暗号に応用されています。$p$ を素数、$m$ を $p$ と互いに素な整数とすると、以下が成り立ちます。
$$m^{p-1}\pmod{p}=1 -①$$
フェルマーの小定理を導く
$p$ を素数、$a,b$ を整数とし、次の二項定理により、
$$(a+b)^p=\sum_{k=0}^p\frac{p!}{k!(p-k)!}a^kb^{p-k} -②$$
$$=a^p+pa^{p-1}b+\frac{1}{2}p(p-1)a^{p-2}b^2+\dots+pab^{p-1}+b^p$$
②の係数は常に自然数となりますが、分子の $p$ は素数で割り切れないため、②の最初と最後の係数以外は常に $p$ の倍数となります。従って、以下が成り立ちます。
$$(a+b)^p\equiv(a^p+b^p)\pmod{p} -③$$
これを一般化すると、
$$(a_1+a_2+\cdots+a_m)^p\equiv(a_1^p+a_2^p+\cdots+a_m^p)\pmod{p}$$
ここで、$a_1=\cdots=a_m=1$ とすると、
$$m^p\equiv m\pmod{p}$$
両辺を $m$ で割ると①が得られます。
フェルマーの小定理の対偶
互いに素な２つの整数 $m,p$ について、
$$m^{p-1}\pmod{p}\ne1$$
が成り立つならば、$p$ は合成数である。
対偶を導く
$p$ が合成数の場合、③が成り立たないことを示します。②より、
$$(a+b)^p=a^p+\cdots+\frac{p!}{k!(p-k)!}a^kb^{p-k}+\dots+b^p$$
ここで、$p=mn$（$m\le n$）とすると、$k=m$ の係数は以下になります。
$$\frac{p!}{m!(p-m)!}=\frac{p(p-1)\cdots(p-m+1)}{1\cdot2\cdots m}$$
右辺の分子は、$m$ 個の連続した自然数の掛算になりますが、先頭の $p$ 以外に $m$ で割り切れる自然数はありません。しかし、この右辺は自然数になる（割り切れる）ため、$p$ は $m$ で割る必要があります。そうすると、この項は $p$ の倍数でなくなるため、結果、③が成り立たなくなります。
