元祖ワシ的日記

その必要条件は何か？という問題。

まずmod3で考えることにより

2^n+1 ≡ (-1)^n+1 (mod 3)

nが奇数のときは右辺は0になるので、必ず3で割り切れる。故に素数にはなりえない。 ということでnは偶数であることがいえます。

n = 2^(k * 奇数)

ならば

2^n + 1 = (2^k)^(奇数) + 1

となるので、mod 2^k+1で考えれば右辺は0になる。故に素数にはなりえない。 例えば2^12+1 = 4097は 16^3 + 1だから17で割り切れる。

ということで肩の指数は 2^kの形である必要があるわけです。 まぁつまりフェルマー数ということですな。

小さいほうから書いていけば

3, 5, 17, 257, 65537, 4294967297, ...

このうち素数なのは65537まで。その先に素数があるかどうかは 未解決問題。