[ 中学の数学 ] フェルマーの小定理
[サイトマップを見る ]
フェルマーの小定理
フェルマーの小定理とは，素数 p と整数 a があるとき，次の式が成り立つというものです。
$$
a^p \equiv a\pmod p
$$
フェルマーの小定理を数学的帰納法を用いて証明しましょう。
ステップ１
a が 1 のとき，
$$
1 ^ p \equiv 1\pmod p
$$
1 をどんな素数で割ってもあまりは 1 になります。素数は1と自分以外では割り切れない数のことでした。具体的には p は次のような数をいいます。
$$
2, 3, 5, 7, 11 \cdots
$$
1 を 2 で割ったら，あまりは 1 です。1 を 3 で割っても，あまりは 1 です。ですから，a が 1 のときは，必ず $${ 1 ^ p \equiv 1\pmod p}$$ が成り立ちます。
ステップ２
a が k のとき，$${ k ^ p \equiv k\pmod p}$$ が成り立つと仮定して，a が k+1 のときを考えてみましょう。
二項定理から，$${(k+1)^p}$$は次のようにかけます。
$$
(k+1)^p = k^p + \binom{p}{1}k^{p-1} + \binom{p}{2}k^{p-2} + \cdots + \binom{p}{p-1}k + 1
$$
右の式の両側 $${k^p}$$ と $${1}$$ を除いた項は全て p で割り切れます。例えば，下の式を見てください。
$$
\binom{p}{r} = \frac{p!}{r!(p-r)!}
$$
具体的に考えた方がわかりやすいでしょうから，p に 7 を r に 3 を代入します。
$$
\binom{7}{3} = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{3 \times 2 \times 1 \times 4 \times 3 \times 2 \times 1}
$$
分子の数にある 6 は分母にある 3 や 2 で割ることができますね。また 4 も分母にある 4 や 1 で割ることができます。
ここで，分子，分母を含めて，一番大きい数 7 に注目してみましょう。7は分子にありますが，この 7 を割る数が分母にあるでしょうか？絶対にありません。なぜなら，7は素数ですから，1 か 7 でしか割り切ることができないからです。分子にある 6 などはさきほど説明したとおり分母にある数で割ることによって消えていくでしょう。けれども，7 はどの数字でも割り切れないので，消えることがありません。
逆に言えばこの式は 7 で割れば，きちんと割り切れることになります。
ですから，以下の式の右を p で割った場合，両はしにある項以外は p で割り切れることがわかります。
$$
(k+1)^p = k^p + \binom{p}{1}k^{p-1} + \binom{p}{2}k^{p-2} + \cdots + \binom{p}{p-1}k + 1
$$
このように書くことが書き直せます。
$$
(k+1)^p \equiv k^p + 1\pmod p
$$
帰納法の仮定より，$${k^p \equiv k\pmod p}$$ ですから，以下の式が成り立つことになります。
$$
(k+1)^p \equiv k + 1\pmod p
$$
[ サイトマップを見る ]
この記事が気に入ったらサポートをしてみませんか？