数学

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

フェルマーの小定理を頭の中で整理したので記録しておきたいと思います。

フェルマーの小定理

素数pと任意の自然数aに対して次の式が成り立つ。

$$ a^p \equiv a \bmod p $$

特にaとpが互いに素なとき次の式が成り立つ。

$$ a^{p-1} \equiv 1 \bmod p $$

証明

上式が成り立つことを帰納法で証明します。

$$a = 1$$のとき左辺は1になるため成り立ちます。

$$a = k$$のときに式が成り立つと仮定して、k+1のときにも成り立つことを示します。

$$(k+1)^p \equiv k^p + 1 \equiv k+1 \bmod p$$

よって任意の自然数で上式が成り立つことが示せました。

ここでaとpが互いに素なときは両辺をaで割ることができて下式が導かれます。

参考

フェルマーの小定理の証明と使い方(けんちょんさん)

フェルマーの小定理の証明と例題(マスオさん)