14868：証明...任意の正の整数mに対して 2^n+1が少なくともm個の相異なる素因数をもつような正の整数nが存在する...

問題14868・・・http://en.whotwi.com/handmade_math/tweets?&page=12 より 引用 Orz〜

任意の正の整数mに対して,2^n +1が少なくともm個の相異なる素因数をもつような正の整数nが存在することを示せ.

解答

・わたしの...

例えば...

2^3^3^3^...^3+1・・・3がm-1個

2+1

2^3+1

2^3^3+1

...

2^3^3^...^3+1・・・3がm-1個

の少なくともm個の因子は存在できる...^^

↑

ちょいいい加減でしたぁ ^^;

↓

・鍵コメT様からのもの Orz〜

これでは不完全です．
例えば，2+1と2^3+1は，素因数としては1種類(3)しか持たず，
m個並べても，素因数がm種類存在する保証はありませんね．

熟考してみると...次のようにできると思います．

以下において，aは3以上の奇数とする．
・2^aは3で割って2余るから，2^a+1は3の倍数．
・2^(3a)+1=(2^a+1)(4^a-2^a+1)において，4^a-2a+1について調べる．
4^a-2^a+1=(2^a+1)(2^a-2)+3であるから，2^a+1と4^a-2^a+1の最大公約数は
2^a+1と3の最大公約数に等しく，3である．
よって，(2^a+1)/3と(4^a-2^a+1)/3は，(ともに整数であり，)互いに素．
・4^a-2^a+1=(2^a)(2^a-1)+1>3より，(4^a-2^a+1)/3は1より大きいから，
素因数を持ち，その素因数は(2^a+1)/3の素因数ではない．
特に，(2^a+1)/3が3の倍数のときは，2^a+1が持たない素因数を持つ．

以上より，次のようになる．
2^3+1=9=3^2.
2^9+1=(2^3+1)*(4^3-2^3+1)であり，
(4^3-2^3+1)/3は2^3+1が持たない素因数を持つから，
2^9+1は3^2の倍数で，かつ2種類以上の素因数を持つ．
2^27+1=(2^9+1)(4^9-2^9+1)であり，
(4^9-2^9+1)/3は2^9+1が持たない素因数を持つから，
2^27+1は3^2の倍数で，かつ3種類以上の素因数を持つ．
以下同様に，
2^(3^m)+1はm種類以上の素因数を持つことがわかります．

*熟読玩味ぃ〜^^;v

[スモークマン]

＞4:31pmの鍵コメT様へ ^^
ほんに ^^;
2^3^3^...^3+1・・・3がm+1個
だったら...(2^3)^3+1,...,(2^3^3^3^...)^3のm-1個は3以外の素因数をもつから...2+1,2^3+1 の素因数3とでm個になるので...いいのかな？...Orz〜

[スモークマン]

＞11:37pmの鍵コメT様へ ^^
なら...2^(1*3*5*7*...*(2m+1))+1
みたいにすればどうでっしゃろ...?
いい加減な発想でメンゴ...Orz〜
こりゃギヴだなぁ...^^;;

[スモークマン]

＞9:59pmの鍵コメT様へ ^^
よくわかってませんけど ^^;
紹介させていただきまっす〜m(_ _)m〜v