2^n +1 と 2^n -1 がともに素数になる自然数 n をすべて求めよ。

2^n +1 と 2^n -1 がともに素数になる自然数 n をすべて求めよ。
この問題について考えています。
-----------------------------------------------------------------------
n=2のとき、5と3となるので、n=2は求める解の１つです。
n=1,3,4,5,…のように小さなnについては、解とならないことを調べることができました。

（A）　2^n -1　はnが偶数のときに３の倍数
（B）　2^n +1　はnが奇数のときに３の倍数
となることを数学的帰納法で証明できたので、
解の可能性は
（a）　2^n -1 =3 つまりn=2のとき
（b）　2^n +1=3 つまりn=1のとき
に絞られて、
（a）のときは 2^n+1 =5 （素数）でOK
（b）のときは 2^n -1 =1 （素数でない）でNG
これから、n=2 のみが解である
----------------------------------------------------------------------
と考えました。

この考え方の良し悪しや、その他の求め方があれば教えてください。

No.1 ベストアンサー 回答者： ShowMeHow 回答日時： 2019/12/10 15:42

３連続する整数はどれかが、かならず３で割り切れる

2＾ｎ　（ｎ∈Z）は3で割り切れない
⇒2^n +1 、2^n -1　のどちらかは３で割り切れる
ｎ＞2の場合、2^n +1 、2^n -1のどちらかは３より大きくなるので、３の倍数である方は素数ではない。

のほうが、少し短くなるかな。

この回答へのお礼

連続する３つの整数の性質。なるほどです。小難しい小定理も必要とせず、しかもわかりやすいです！なるほど！

お礼日時：2019/12/10 16:27

No.6 回答者： Tacosan 回答日時： 2019/12/12 00:31

あ, 2^11+1 はもちろん 2^11-1 の間違いです. 感謝しつつ指摘しておくと, 2^(2^3)+1 = 257 は素数.

因数の形に対する証明は, メルセンヌ数では見たことがあるけどけっこう大変だったような気がする. フェルマー数の方は... 記憶にないなぁ.

あとフェルマー数に対しては Wikipedia の項
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7 …
にもあるけど, オイラーが反例を見付けたときには k・2^(n+1)+1 の形で調べてる. また, 英語版には
n≧2 なら k・2^(n+2)+1 の形
と書いてある.

フェルマー数については (「全部素数」と思ったフェルマーの予想に反し) 「もう素数はないんじゃないか」という予想すら立てられているというのが, なんというか切ない感じがする.

この回答へのお礼

>感謝しつつ指摘しておくと, 2^(2^3)+1 = 257 は素数.

計算ミスをしてまいました。257=８・2^(3+2)+1 で因数の形式を満たしますね。

>因数の形に対する証明は, メルセンヌ数では見たことがあるけどけっこう大変だったような気がする. フェルマー数の方は... 記憶にないなぁ.

そうなのですね。難しそうです。2^n か±1 から因数の形を示す、いったいどんな方針の証明なのでしょう、と興味や恐怖心のような感覚になりました。

Wikipediaについての観察もありがとうございます。「英語版」を観る、という視点から、ようやく英語版のページへの行き方を知り、英語版を見たら、フェルマー数の因数の形式についての証明が載っているようですね。証明のはじまりが
>Let Gp denote the group of non-zero elements of the integers modulo p under multiplication, which has order p-1.
とあるので、群を使うのか、剰余を考察するのかな、、、などと簡単に思考するにとどまりました。考えるには、それなりの時間がかかりそう。

>フェルマー数については (「全部素数」と思ったフェルマーの予想に反し) 「もう素数はないんじゃないか」という予想すら立てられているというのが, なんというか切ない感じがする.

（　「全部素数」と思ったフェルマーの予想に反し　）については、散見されるような気がしますが、後述の「「もう素数はないんじゃないか」という予想すら立てられている」ということについては初めて聞きました。切ない。なんとなく、その気持ち、わかります。大きな数は苦手です。

お礼日時：2019/12/12 07:59

No.5 回答者： Tacosan 回答日時： 2019/12/11 23:11

2^n+1 で n = pq (p は正整数, q は 3以上の奇数) と書けるとすると

2^n+1 = (2^p)^q + (1^p)^q
で, 2^p+1^p で割り切れちゃうから不可.

つまり 2^n+1 が素数であるためには, n が (3以上の) 奇数で割り切れてはいけない.

フェルマー数やメルセンヌ数はその約数の形も知られていて, 例えば
・p が素数のとき 2^p-1 の因数は 2pk+1 (k は整数)
・n が整数のとき 2^(2^n)+1 の因数は k・2^(n+2)+1 (k は整数)
が証明されています. 例えば 2^11+1 だと 23 = 1×(2・11)+1, 89 = 4×(2・11)+1.

この回答へのお礼

2^n+1（"フェルマー"）の証明を頂きありがとうございます。とても初等的なんですね。（初等的ですが私にはとても思いつくものではありません。）
a^n + b^nの形式がnが奇数の場合に因数分解できる、
つまり　a^n - b^n の形式が因数分解可能であることが論拠になっているわけですね。
nが奇数のときに後半の式にb=(-b)を代入すればよい。

n=pqの分解において、qを３以上の奇数とおくことが肝になっている、この発想がすごいと思いました。

----------------------------
後半の約数の形も、すごいですね。（この命題の証明も簡単なのでしょうか。）
確かに23と89は形式に従っています。
※「例えば 2^11+1」は「例えば 2^11-1」ですね。

---------------------------
2^(2^n)+1 の因数はどうでしょう。
>・n が整数のとき 2^(2^n)+1 の因数は k・2^(n+2)+1 (k は整数)★★★
は、・n が整数のとき 2^(2^n)+1 の因数は k・2^(m+2)+1 (k,m は整数)？？？

n=1のときは、2^(2^1)+1=4+1=5　であり、
5≠k・2^(1+2)+1　？？？　　　★5=1・2^(0+2)+1　？？？

n=2のときは、2^(2^2)+1=16+1=17　であり、
17=1・2^(2+2)+1

n=3のときは、2^(2^3)+1=128+1=129　であり、129=43・3
3≠k・2^(3+2)+1　　？？？　　★3=1・2^(-1+2)+1　？？？
43≠k・2^(3+2)+1　　？？？　　★43=21・2^(-1+2)+1　？？？


★★★については、理解が難しいです。

お礼日時：2019/12/12 00:00

No.4 回答者： syotao 回答日時： 2019/12/11 16:20

さっきの(4^n)-1が3の倍数である.

の関連問題じゃないの？
問題の2数が両方素数ならその積は3の倍数
だから、その2数のうちどちらかが3でなければならない。

この回答へのお礼

>さっきの(4^n)-1が3の倍数である.の関連問題じゃないの？
そうです！自分なりに考えて、質問を整理して２回に分けました。

ただ、私は、"さっきの質問"は
「2^n -1　はnが偶数のときに３の倍数」
の証明に関心を持って行ったものだったため、
syotaoさんの視点

>問題の2数が両方素数ならその積は3の倍数
>だから、その2数のうちどちらかが3でなければならない。

には、なるほど！と、とても参考になりました。

①AB=(2^n-1)(2^n+1)=4^n-1は３の倍数である（＊）
②A=(2^n-1), B=(2^n+1)の両方が素数なら（＊）より
AまたはBのどちらかは3に等しい。
③A=3ならn=2，このときB=5でOK
④B=3ならn=1，このときA=1でNG

①と②の論理が巧くいっているということですね。
とても勉強になりました。

お礼日時：2019/12/11 22:23

No.3 回答者： Tacosan 回答日時： 2019/12/10 23:29

・2^n-1 が素数になるためには n が素数でなければならない (メルセンヌ)

・2^n+1 が素数になるためには n が (1 を含む) 2 のべきまたは 0 でなければならない (フェルマー)
ので, 2^n+1 と 2^n-1 の両方が素数になるためには n が
素数である 2 のべき
でなければならない.

よって n=2.

この回答へのお礼

回答ありがとうございます。
２つの定理は、有名な偉人の発見としても史実があるのですね。それぞれの定理について、秀逸な証明などはあるのでしょうか。

私自身、思考の整理をしました。
>・2^n-1 が素数になるためには n が素数でなければならない (メルセンヌ)
この証明はNo2(rnakamraさん)が教えてくれた。
興味を持って少し調べたところ、この逆（nが素数ならば2^n-1が素数）は成り立たない。
《反例》
2^11-1=2048-1=23*89
2^23-1=8388608-1=47*178481

>・2^n+1 が素数になるためには n が (1 を含む) 2 のべきまたは 0 でなければならない (フェルマー)
これはどうしてだろう？と思案中です。

お礼日時：2019/12/11 22:12

No.2 回答者： rnakamra 回答日時： 2019/12/10 16:23

nが合成数であるとき2^n-1は合成数です。

つまり2^n-1が素数となるのはnが素数である場合に限られます。

n=pqと因数分解できるとする。(p,q>1)
2^(pq)-1=(2^p-1){(2^p)^(q-1)+(2^p)^(q-2)+(2^p)^(q-3)+...+2^p+1}
と因数分解でき、p,q>1であるから2^p-1>2,(2^p)^(q-1)+(2^p)^(q-2)+(2^p)^(q-3)+...+2^p+1>1であることから2^(pq)-1は合成数である。

(nが素数の場合、p=1となるが2^1-1=1であり合成数だとはこれだけでは言えなくなる)

質問者の(B)からnは偶数であるが、偶数の素数は2だけである。

この回答へのお礼

回答ありがとうございます。
2^n-1は、nが合成数であれば、それ自身も合成数。だから、2^n-1が素数であるとすれば、nは素数。（Ｂ）では、nとして偶数を考えているが、2より大きい偶数は合成数だ、という流れが理解できました。2^n-1はnが合成数の奇数の場合にも素数にはならないよ、という視点が得られました。例えば、2^9-1=512-1=511=7*73です。

お礼日時：2019/12/10 16:40