2のべき乗+1が素数になる条件

方針

解答

⓪ 発想 — どう考え始めるか。 「素数でない」ことを示すには、1と自分以外の約数を実際に見つける。つまり因数分解を作るのが本筋だ。

鍵は、$m$ が奇数のときの恒等式 $x^m+1=(x+1)(x^{m-1}-x^{m-2}+\cdots -x+1)$($x=-1$ を代入すると0になるから、$x+1$ を因数にもつ)。

$n$ が奇数の約数 $m(\ge 3)$ をもつなら $n=mt$ と書けて、$2^n=(2^t{)}^m$。$x=2^t$ を代入すれば、因数 $2^t+1$ が浮かび上がる。

① (1) の証明。 $n=mt$($m$ は3以上の奇数、$t$ は自然数)とする。$x=2^t$ とおくと

$$2^n+1=(2^t{)}^m+1=(2^t+1)\left((2^t{)}^{m-1}-(2^t{)}^{m-2}+\cdots +1\right)$$

ここで $m\ge 3$ より $n>t$ だから

$$1<2^t+1<2^n+1$$

つまり $2^t+1$ は $2^n+1$ の真の約数で、$2^n+1$ は素数でない。

② 素数になり得る $n$ の形。 (1)の対偶から、$2^n+1$ が素数なら $n$ は3以上の奇数の約数をもたない。すなわち $n$ は $2^k$ の形($n=1,2,4,8,16,\dots$)だ。

③ (2) の答え。 $n\le 10$ で2のべきの形は $n=1,2,4,8$。値を確かめる:

$$2^1+1=3,2^2+1=5,2^4+1=17,2^8+1=257$$

3, 5, 17 は素数。257 は $\sqrt{257}<17$ だから 2, 3, 5, 7, 11, 13 で割れないことを確かめればよく、実際どれでも割れないので素数。ほかの $n$($3,5,6,7,9,10$)はすべて3以上の奇数の約数をもつので、(1)より不適。

まとめ: 素数性の議論は「合成数になる仕組み=因数分解」から攻める。指数の奇数因子がそのまま因数分解を生むので、$2^n+1$ が素数になり得るのは $n$ が2のべきのときに限られる。

発展 — 一歩先へ。 $2^{2^k}+1$ の形の数はフェルマー数と呼ばれる。$3,5,17,257,65537$ と5連続で素数だったため、フェルマーは「すべて素数」と予想した。だが次の $2^{32}+1=4294967297$ は $641$ で割り切れる(オイラーの発見)。その先、新しい素数は1つも見つかっていない。

別解

合同式で1行に畳む(得意な人向け)。 因数分解の恒等式を、合同式の言葉に翻訳するとさらに短くなる。

$n=mt$($m$ は3以上の奇数)とする。法を $2^t+1$ に取ると

$$2^t\equiv -1(\mathrm{mod}{2}^t+1)$$

(これは定義そのもの。)両辺を $m$ 乗すれば、$m$ が奇数だから

$$2^n=(2^t{)}^m\equiv (-1{)}^m=-1(\mathrm{mod}{2}^t+1)$$

すなわち $2^n+1\equiv 0$。つまり $2^t+1$ は $2^n+1$ を割り切る。あとは $1<2^t+1<2^n+1$ で真の約数と確認するだけだ。

恒等式の長い第2因子を書かずに、「$-1$ の奇数乗は $-1$」の一言で同じ約数に到達する。因数分解と合同式は、同じ事実の2つの言語である。