数学B / 漸化式と数学的帰納法

メルセンヌ数の最大公約数(漸化式と整数)

実戦編漸化式整数の性質最大公約数互除法単元横断

問題

$M_{n} = 2^{n} - 1$ とする。 $m > n$ のとき $g cd (M_{m}, M_{n}) = g cd (M_{m - n}, M_{n})$ が成り立つことを示し、これを用いて $g cd (M_{m}, M_{n}) = 2^{g c d (m, n)} - 1$ を示せ。

ヒントを見る

$2^{m} - 1 = 2^{m - n} (2^{n} - 1) + (2^{m - n} - 1)$ を確かめる。すると $M_{n}$ で割った余りが $M_{m - n}$ 。互除法が指数の引き算になり、 $g cd (m, n)$ に対応する。

解答・解説

方針

$2^{m} - 1$ を $2^{n} - 1$ で割った余りを求める恒等式 $M_{m} = 2^{m - n} M_{n} + M_{m - n}$ を作る。指数について互除法(引き算)が回り、指数の $g cd$ に落ちる。

解答

⓪ 発想 — どう考え始めるか。 $g cd (2^{m} - 1, 2^{n} - 1)$ を、指数の世界の互除法に翻訳したい。

カギは割り算の恒等式 $M_{m} = 2^{m - n} M_{n} + M_{m - n}$ 。 $2^{m} - 1$ を $2^{n} - 1$ で割ると、余りがちょうど $M_{m - n} = 2^{m - n} - 1$ になる。

つまりユークリッドの互除法で指数の引き算 $m - n$ が起こる。指数について互除法を回すと $g cd (m, n)$ に落ち、 $g cd (M_{m}, M_{n}) = 2^{g c d (m, n)} - 1$ が出る。

重要恒等式

2^{m} - 1 = 2^{m - n} (2^{n} - 1) + (2^{m - n} - 1)

、すなわち

M_{m} = 2^{m - n} M_{n} + M_{m - n}

① 割り算の恒等式。 $2^{m - n} (2^{n} - 1) = 2^{m} - 2^{m - n}$ だから $2^{m} - 1 = (2^{m} - 2^{m - n}) + (2^{m - n} - 1) = 2^{m - n} M_{n} + M_{m - n} .$ よって $M_{m}$ を $M_{n}$ で割った余りは $M_{m - n}$ ( $0 \leq M_{m - n} < M_{n}$ 、 $m > n$ より)。ゆえに $g cd (M_{m}, M_{n}) = g cd (M_{n}, M_{m - n}) = g cd (M_{m - n}, M_{n}) .$ ② 互除法が指数に対応。 この操作は指数について $(m, n) \to (m - n, n)$ 、まさにユークリッドの互除法(引き算版)。互除法を繰り返すと、指数は最終的に $g cd (m, n)$ に落ちる。

③ 結論。 よって $g cd (M_{m}, M_{n}) = M_{g c d (m, n)} = 2^{g c d (m, n)} - 1.$ (例: $g cd (M_{6}, M_{4}) = g cd (63, 15) = 3 = 2^{2} - 1 = M_{g c d (6, 4)}$ 。)

まとめ $M_{m}$ を $M_{n}$ で割った余りが $M_{m - n}$ 、という恒等式で互除法が指数の引き算になる。回し切ると $g cd (M_{m}, M_{n}) = 2^{g c d (m, n)} - 1$ 。漸化式(互除法)と整数の融合。

発展 — 一歩先へ。 $M_{p} = 2^{p} - 1$ が素数(メルセンヌ素数)になるには $p$ 自身が素数であることが必要だ( $p = ab$ なら $M_{a} ∣ M_{p}$ で分解してしまう)。逆は成り立たず、 $M_{11} = 2047 = 23 \times 89$ は合成数。史上最大の素数がいつもメルセンヌ数の形なのは、この構造と高速判定法(リュカ・レーマー法)のおかげである。

答

$M_{m} = 2^{m - n} M_{n} + M_{m - n}$ (恒等式)から、 $M_{n}$ で割った余りが $M_{m - n}$ 。ユークリッドの互除法が指数の引き算に対応し、 $g cd (M_{m}, M_{n}) = M_{g c d (m, n)} = 2^{g c d (m, n)} - 1$ 。

別解

別解 — 「 $d ∣ n ⟺ M_{d} ∣ M_{n}$ 」を先に押さえる(得意な人向けの高い視点)。 割り切れる関係を直接使うルートもある。

$2^{n} - 1$ を等比数列の和とみると、 $d ∣ n$ のとき

$2^{n} - 1 = (2^{d} - 1) (2^{n - d} + 2^{n - 2 d} + \dots + 1)$

と因数分解できる。つまり $d ∣ n \Rightarrow M_{d} ∣ M_{n}$ 。逆に $d ∤ n$ なら割り切れない(余りが $M_{n mod d} \neq = 0$ )。まとめると

$M_{d} ∣ M_{n} ⟺ d ∣ n .$

すると $g cd (M_{m}, M_{n})$ の正体が見える。 $M_{m}$ と $M_{n}$ をともに割る最大の $M_{d}$ は、 $d ∣ m$ かつ $d ∣ n$ を満たす最大の $d$ 、すなわち $d = g cd (m, n)$ に対応する。よって

$g cd (M_{m}, M_{n}) = 2^{g c d (m, n)} - 1.$

互除法を回す本解と、「割り切れる条件」を先に確立するこの解。どちらも「指数の整除が、メルセンヌ数の整除に写る」という一点に支えられている。

ポイント

$M_{m} = 2^{m - n} M_{n} + M_{m - n}$ で余りが $M_{m - n}$ 。
$g cd (M_{m}, M_{n}) = g cd (M_{m - n}, M_{n})$ (互除法の1ステップ)。
互除法が指数の $g cd$ に落ち、 $2^{g c d (m, n)} - 1$ 。

よくある間違い

恒等式 $M_{m} = 2^{m - n} M_{n} + M_{m - n}$ を作れず、 $M_{m}$ を $M_{n}$ で割った余りが $M_{m - n}$ だと示せない。
指数の互除法(引き算 $m - n$ )と、通常の数の互除法を混同する。
$g cd (m, n) = 1$ のとき $g cd (M_{m}, M_{n}) = 2^{1} - 1 = 1$ (互いに素)を、 $0$ や別の値と誤る。