数列

質問

2+1, 2^2+1, 2^4+1, 2^8+1, …… , 2^(2^n)+1
という数列が、どの２項も互いに素であることを示せという問題なのですが、帰納法や背理法を使っても証明できません。どなたか教えてください。

回答No.1

yoikagari · ベストアンサー

背理法ですね。

x^(2^k)-1=(x^{2^(k-1)}-1)*(x^{2^(k-1)}+1)という恒等式がポイントになります。

2+1, 2^2+1, 2^4+1, 2^8+1, … , 2^(2^n)+1,…から任意に選んだ2つの数2^(2^m)+1と2^(2^k)+1が、互いに素であることを示せばよい(ただし、mとkをm＜kとなるような自然数とする)。

2^(2^m)+1と2^(2^k)+1の最大公約数をdとする。
2^(2^m)+1=d*u、2^(2^k)+1=d*v

2^(2^k)+1={2^(2^k)-1}+2=(2^{2^(k-1)}-1)*(2^{2^(k-1)}+1)+2=(2^{2^(k-2)}-1)(2^{2^(k-2)}+1)*(2^{2^(k-1)}+1)+2=…={2^(2^m)+1}*(2^{2^(m+1)}+1)*…*(2^{2^(k-1)}+1)+2

ですから
2^(2^k)+1-[{2^(2^m)+1}*(2^{2^(m+1)}+1)*…*(2^{2^(k-1)}+1)]=2
d(u-{v*(2^{2^(m+1)}+1)*…*(2^{2^(k-1)}+1)})=2
したがって、dは2の約数となる。

ところが、dは奇数の2^(2^m)+1と2^(2^k)+1の公約数だから、dは奇数。
よってd=1

これは2^(2^m)+1と2^(2^k)+1が互いに素であることを示している。

よって、2+1, 2^2+1, 2^4+1, 2^8+1, … , 2^(2^n)+1,…のどの2項も互いに素であることがわかる。

お礼

大変分かりやすい解答ありがとうございました。
背理法で公約数から攻めていくことは考え付きませんでした。本当にありがとうございました。