数学A / 整数の性質

フェルマーの小定理(二項定理と帰納法)

実戦編整数の性質合同二項定理数学的帰納法単元横断

問題

$p$ を素数とする。すべての整数 $a \geq 0$ について $a^{p} \equiv a (mod p)$ が成り立つことを、二項定理と数学的帰納法で示せ。

ヒントを見る

$0 < k < p$ のとき $(k p)$ は $p$ の倍数。すると $(a + 1)^{p}$ を二項展開すると、中間項が消えて $a^{p} + 1$ に合同。 $a$ について帰納法。

解答・解説

方針

$0 < k < p$ のとき $(k p)$ が $p$ の倍数であることを使うと、 $(a + 1)^{p} \equiv a^{p} + 1$ 。これを使って $a$ に関する数学的帰納法で示す。

解答

⓪ 発想 — どう考え始めるか。 「すべての整数 $a$ で成り立つ」を示すなら、 $a$ に関する帰納法が自然だ。 $a$ から $a + 1$ へ渡る橋がほしい。

橋になるのが二項定理である。 $(a + 1)^{p}$ を展開すると、 $p$ が素数なら $0 < k < p$ の $(k p)$ はすべて $p$ の倍数。つまり中間項が $mod p$ で全部消える。

残るのは $(a + 1)^{p} \equiv a^{p} + 1$ 。この“ $1$ つずつ進める”関係を土台に、 $a = 0$ から積み上げればよい。

定理

p

が素数で

0 < k < p

のとき

(k p) = \frac{p !}{k ! ( p - k )!}

は

p

の倍数(分子の

p

が分母で約されない)

① 二項定理で $1$ 進める。 $0 < k < p$ で $(k p) \equiv 0 (mod p)$ だから $(a + 1)^{p} = k = 0 \sum p (k p) a^{k} \equiv (0 p) a^{0} + (p p) a^{p} = 1 + a^{p} (mod p) .$ すなわち $(a + 1)^{p} \equiv a^{p} + 1 (mod p)$ 。

② 帰納法。 $a = 0$ : $0^{p} = 0 \equiv 0$ で成立。 $a$ で $a^{p} \equiv a$ を仮定すると、①より $(a + 1)^{p} \equiv a^{p} + 1 \equiv a + 1 (mod p) .$ よって $a + 1$ でも成立。

重要数学的帰納法:

a = 0

で成立し、

a

で成立すれば

a + 1

でも成立 → すべての

a \geq 0

で成立

③ 結論。 すべての整数 $a \geq 0$ で $a^{p} \equiv a (mod p)$ 。

まとめ $(k p) \equiv 0 (0 < k < p)$ から $(a + 1)^{p} \equiv a^{p} + 1$ 、 $a$ の帰納法でフェルマーの小定理 $a^{p} \equiv a$ 。整数(合同)・二項定理・帰納法の融合。

発展 — 一歩先へ。 逆は成り立たない。 $2^{341} \equiv 2 (mod 341)$ だが、 $341 = 11 \times 31$ は合成数である(擬素数とよばれる。底を $3$ に変えると見破れる)。「フェルマーの小定理を満たすか」は素数判定の一次試験にすぎず、これをすり抜ける合成数の存在が、現代の素数判定法を精密にした。

答

$0 < k < p$ で $(k p) \equiv 0 (mod p)$ なので $(a + 1)^{p} \equiv a^{p} + 1 (mod p)$ 。 $a$ についての帰納法で $a^{p} \equiv a$ 。

別解

別解 — 「掛けても並べ替わるだけ」の証明(得意な人向けの高い視点)。 $a$ が $p$ の倍数なら両辺とも $\equiv 0$ で明らか。そこで $a$ が $p$ で割れないとする。

$a, 2 a, 3 a, \dots, (p - 1) a$ を $p$ で割った余りを見る。もし $ia \equiv j a$ なら $(i - j) a \equiv 0$ で、 $a$ が $p$ と互いに素だから $i = j$ 。つまり余りはすべて異なり、 $1, 2, \dots, p - 1$ の並べ替えになっている。

全部掛け合わせると

$a^{p - 1} \cdot (p - 1)! \equiv (p - 1)! (mod p) .$

$(p - 1)!$ は $p$ と互いに素だから両辺から払ってよく、 $a^{p - 1} \equiv 1$ 。両辺に $a$ を掛ければ $a^{p} \equiv a$ 。

帰納法で $1$ 段ずつ登る本解に対し、こちらは「 $a$ 倍という操作が余りの世界を並べ替えるだけ」という全体の対称性を使う。ひとつの定理に別々の景色がある好例だ。

ポイント

$0 < k < p$ で $(k p)$ は $p$ の倍数(素数だから)。
$(a + 1)^{p} \equiv a^{p} + 1 (mod p)$ 。
$a$ についての帰納法で $a^{p} \equiv a$ 。

よくある間違い

$(k p) \equiv 0$ の理由を「分子に $p$ があるから」で済ませる( $p$ が素数で、分母 $k! (p - k)!$ の因数がすべて $p$ 未満だから約分で消えない、まで言う)。
帰納法の出発点( $a = 0$ で $0^{p} \equiv 0$ )を書き忘れる。
$a^{p} \equiv a$ と $a^{p - 1} \equiv 1$ を混同する(後者は $a$ が $p$ の倍数のとき成り立たない。 $a$ で割る前に互いに素の確認が要る)。