数学A / 整数の性質

素数を法とする二項展開(フロベニウスの夢)

実戦編整数の性質二項定理合同素数単元横断

問題

$p$ を素数とする。(1) $0 < k < p$ のとき二項係数 $(k p)$ は $p$ の倍数であることを示せ。

(2) すべての整数 $a, b$ について $(a + b)^{p} \equiv a^{p} + b^{p} (mod p)$ を示せ。

ヒントを見る

(1) $(k p) = \frac{p}{k} (k - 1 p - 1)$ を整数の等式 $k (k p) = p (k - 1 p - 1)$ に。 $p$ 素数、 $0 < k < p$ なら $p$ と $k$ は互いに素。(2) 二項展開の中間項が(1)で消える。

解答・解説

方針

(1) 等式 $k (k p) = p (k - 1 p - 1)$ を使い、 $p$ が素数で $0 < k < p$ なら $p ∤ k$ から $(k p)$ が $p$ の倍数。(2) それを二項定理に入れて中間項を消す。

解答

⓪ 発想 — どう考え始めるか。 (1) の急所は整数の等式 $k (k p) = p (k - 1 p - 1)$ 。右辺は見るからに $p$ の倍数だ。

左辺を見る。 $p$ は素数で $0 < k < p$ だから、 $k$ は $p$ と互いに素。すると $p$ は $k$ の側を割れないので、 $(k p)$ の側を割るしかない。

(2) はこの事実の収穫だ。 $(a + b)^{p}$ を二項定理で開くと、中間項( $0 < k < p$ )が $mod p$ で全部消え、両端の $a^{p} + b^{p}$ だけが残る。「和の $p$ 乗がバラバラに乗る」。素数だけで起こる現象である。

重要整数の等式

k (k p) = p (k - 1 p - 1)

① $(k p)$ が $p$ の倍数。 上の等式で右辺は $p$ の倍数だから、左辺 $k (k p)$ も $p$ の倍数。 $p$ は素数で $0 < k < p$ より $p ∤ k$ 、すなわち $p$ と $k$ は互いに素。よって $p$ は $(k p)$ を割る(素数が積を割るとき、互いに素でない方を割る)。ゆえに $0 < k < p$ で $(k p) \equiv 0 (mod p)$ 。

② 二項展開の中間項が消える。 二項定理から $(a + b)^{p} = k = 0 \sum p (k p) a^{p - k} b^{k} = a^{p} + 各 (k p) \equiv 0 k = 1 \sum p - 1 (k p) a^{p - k} b^{k} + b^{p} .$ 中間の和は各係数 $(k p) (0 < k < p)$ が $p$ の倍数だから $mod p$ で $0$ 。よって $(a + b)^{p} \equiv a^{p} + b^{p} (mod p) .$

まとめ $k (k p) = p (k - 1 p - 1)$ と $p ∤ k$ から $(k p) \equiv 0 (0 < k < p)$ 。二項定理の中間項が消えて $(a + b)^{p} \equiv a^{p} + b^{p}$ 。これはフェルマーの小定理の土台でもある。整数・二項定理・素数の融合。

発展 — 一歩先へ。 (2) を繰り返すと $(a_{1} + \dots + a_{m})^{p} \equiv a_{1}^{p} + \dots + a_{m}^{p}$ 。とくに $1$ を $a$ 個足した式に使えば $a^{p} \equiv a$ 、フェルマーの小定理が一行で出る。この単元の帰納法による証明と根は同じ( $1$ ずつ足す)ながら、景色の違う道である。

答

(1) $k (k p) = p (k - 1 p - 1)$ の右辺が $p$ の倍数で、 $0 < k < p$ より $k$ は $p$ と互いに素だから $(k p)$ が $p$ の倍数。(2) 二項定理の中間項が $mod p$ で消えて $(a + b)^{p} \equiv a^{p} + b^{p}$ 。

別解

別解 — 円卓の回転で示す(得意な人向けの高い視点)。 $(k p)$ を「円周上に等間隔に並んだ $p$ 個の席から $k$ 席を選ぶ場合の数」と読み替える。

選び方全体を、円の回転( $1$ 席ずつずらす)で仲間分けする。 $1$ つの選び方は $p$ 回の回転で元に戻るから、各グループの大きさは $p$ の約数。 $p$ は素数なので、大きさは $1$ か $p$ しかない。

大きさ $1$ のグループとは「どの回転でも変わらない選び方」。それは全席選ぶ( $k = p$ )か何も選ばない( $k = 0$ )だけで、 $0 < k < p$ ではあり得ない。

よってすべてのグループの大きさはちょうど $p$ 。総数 $(k p)$ は大きさ $p$ のグループの寄せ集めだから、 $p$ の倍数である。

数式の割り算(本解)を使わず、「素数個の回転は途中で戻れない」という対称性だけで示せた。この“回転で仲間分け”は、円順列など数え上げの証明で繰り返し現れる強力な見方だ。

ポイント

$k (k p) = p (k - 1 p - 1)$ と $p ∤ k (0 < k < p)$ から $(k p) \equiv 0$ 。
二項定理の中間項が $mod p$ で消える。
$(a + b)^{p} \equiv a^{p} + b^{p} (mod p)$ 。

よくある間違い

(1) を「分子 $p!$ に $p$ があるから」で済ませる(分母との約分で消えない理由=分母の因数はすべて $p$ 未満、が本体)。
素数の仮定を落とし、一般の $n$ でも $(k n)$ が $n$ の倍数だと思い込む( $(2 4) = 6$ は $4$ の倍数でない)。
(2) で両端の項 $k = 0, p$ まで消してしまう(消えるのは中間項だけ。残る $a^{p} + b^{p}$ が結論そのもの)。