フェルマーの小定理

素数$${p}$$と正整数$${a}$$の間で
$${a^{p} \equiv a \mod p}$$
が成り立つ。
特に、$${p}$$と$${a}$$が互いに素のとき
$${a^{p-1} \equiv 1 \mod p}$$

この関係をフェルマーの小定理という。

例えば、ある正整数が素数か合成数かを判定するのに使える。

フェルマーの小定理の対偶を取ると
『ある正整数$${a}$$に対して$${a^n \not\equiv a \mod n}$$であれば正整数$${n}$$は合成数である。』

$${4}$$が素数か合成数かを調べたいとき、$${a = 2}$$として$${2^4 \equiv 16 \not\equiv 2 \mod 4}$$だから$${4}$$は合成数である。

$${a^n \equiv a \mod n}$$ であれば$${n}$$は高確率で素数だが、稀に本当は合成数なのに素数として振舞ってしまう数もある。($${561}$$など)

他には、RSA暗号に応用されている。

フェルマーの小定理の証明は、次のようになる。

$${p}$$を法とすると
$${a =1}$$のとき$${a^p \equiv a}$$だからフェルマーの小定理が成り立つ。
ここで正整数$${m}$$に関して、二項定理より
$${(m + 1) ^ p = m^p + 1 + \sum_{k = 1}^{p} {}_p C_k m^k}$$
$${p}$$が素数で$${1 \leq k \leq p-1}$$のとき$${{}_p C_k m^k}$$は$${p}$$の倍数(※後述する)なので、$${\sum_{k = 1}^{p} {}_p C_k m^k \equiv 0}$$となる。
したがって、$${(m + 1) ^ p \equiv m^p + 1}$$
$${a = m}$$のときフェルマーの小定理が成り立つと仮定すると、$${(m + 1) ^ p \equiv m^p + 1\equiv m + 1}$$より$${a = m＋1}$$のときもフェルマーの小定理が成り立つことが導かれる。
以上より、全ての正整数$${a}$$に対してフェルマーの小定理が成り立つことが証明された。

証明の途中で登場した『$${p}$$が素数で$${1 \leq k \leq p-1}$$のとき$${{}_p C_k m^k}$$は$${p}$$の倍数』に触れる。

まず、以下の関係式が成り立つことを証明する。

$${k {}_p C_k = p {}_{p-1} C_{k-1}}$$

この式が成り立てば、$${{}_{p-1} C_{k-1}}$$は整数なので$${k {}_p C_k}$$は$${p}$$の倍数であり、$${k}$$と素数$${p}$$は互いに素だから$${{}_p C_k }$$は$${p}$$の倍数となる。

つまり、$${{}_p C_k m^k}$$は$${p}$$の倍数となる。

$${k {}_p C_k = p {}_{p-1} C_{k-1}}$$は$${p}$$人から$${k}$$人を選ぶ組合せから、さらにリーダーを決める方法の総数を2通りで表したものである。

左辺$${k {}_p C_k}$$は$${p}$$人のグループから$${k}$$人を選ぶ組合せ$${{}_p C_k}$$の各々に対して、リーダーを一人選ぶ$${k}$$通りの方法があることを表す。

右辺$${p {}_{p-1} C_{k-1}}$$は、まず$${p}$$人から一人リーダーを選ぶ$${p}$$通りの各々に対して、リーダー以外の$${k-1}$$人を$${p-1}$$人から選ぶ組合せ$${{}_{p-1} C_{k-1}}$$が存在することを表す。

左辺$${k {}_p C_k}$$と右辺$${p {}_{p-1} C_{k-1}}$$はどちらも同じ事態を表すので$${k {}_p C_k = p {}_{p-1} C_{k-1}}$$

証明が完了した。