面白い問題おしえて～な十六問目

面白い問題おしえて～ ..

164:１３２人目の素数さん
10/05/01 12:24:48
（続き）
995 954 [sage] 2010/04/28(水) 15:52:01 ID: Be:
もう忘れられかけているので自己解答します。結局ググル先生に教えてもらいました。
テニオハがなっていませんが普通に理解できると思います。
適切な指導者がいて特訓すれば数学オリンピックなんて大した事ないのかもと思えてきました。
(天才は指導者がいなくても自力で成長できるんだろうけど・・・)

n＞1 で n^2|2^n+1 が成り立つと仮定する。

(１)．　n|2^n+1よりnは奇数。nの最小素因数をpとする。p|2^n+1、すなわち2^n≡-1(mod p)。
2^i≡-1(mod p)となる最小の数をiとする。2^(p-1)≡1(mod p)より、i<(p-1)。
ｎ=ki+r (0≦r＜i)とおくと、2^n≡(-1)^k・2^r≡-1(mod p)。kは偶数だとすると、2^r≡-1(mod p)
となりiの選び方と矛盾するのでkは奇数。よって2^r≡1(mod p)。
2^(i-r)≡2^r・2^(i-r)≡2^i≡-1(mod p)かつiの最小性により、r=0。
i|n,i<(p-1)によりi=1。よって2≡-1(mod p)すなわちp|3、よってp=3。

(２)．　n=3^k・d, (d,3)=1とする。まずk≧2 と仮定する。n^2|2^n+1より、3^(k+2)|1-(1-3)^n。
よって、3^(k+2)|3^(k+1)・d- Σ[h=2,k+1]{C<n,h>・(-1)^h・3^h}。
h!に含まれる3の指数はh/2(=h/3+h/9+h/27+…)未満かつh≧2なので、3^(k+2)|C<n,h>・3^h。
これは、3|d となるので矛盾する。よってk=1、すなわちn=3d。

(３)．　d＞1と仮定した上でdの最小素因数をqとする(q≧5)。 q|2^n+1すなわち2^n≡-1(mod q)。
2^j≡-1(mod q)となる最小の数をjとする。2^(q-1)≡1(mod q)より、i<(q-1)。
((1)と同様なので中略)、ｊ|n。またqはdの最小素因数であり,j<q-1,nは奇数。
よってｊ=1またはj=3、すなわちq|3またはq|9。どちらもq=3となりq≧5に矛盾する、よってd=1。

以上により、n＞1 の場合の候補は3のみ。
n=3の時に成り立つのは明らか。[証明終了]

次ページ

続きを表示

1を表示