面白い問題おしえて〜な 十六問目
くだらねぇ問題はここへ書け ver.3.14(63桁略)7816
が沈んで消えたので転載
954 １３２人目の素数さん [sage] 2010/04/23(金) 14:29:44 ID: Be:
「数学・まだこんなことがわからない−素数の謎から森理論ｍで−」吉永良正（講談社ブルーバックス）
に載ってた問題です。
「(2^n + 1)/n^2 が整数となるような１より大きい整数ｎを全て決定せよ」
（答えは、「n=3」のみ。）
この証明方法を教えて欲しいです。
『フェルマーの小定理』の小定理を知っていないとまず解けない問題だそうです。
元々は、１９９０年の数学オリンピック北京大会で出題された問題ですが、日本勢で正解した人はいなかったそうです。
本では、これというのも日本の学校では初等整数論さえまともに教えてないから云々といった感じで続いていて
問題の解法には一切触れられていませんでした。
が沈んで消えたので転載
954 １３２人目の素数さん [sage] 2010/04/23(金) 14:29:44 ID: Be:
「数学・まだこんなことがわからない−素数の謎から森理論ｍで−」吉永良正（講談社ブルーバックス）
に載ってた問題です。
「(2^n + 1)/n^2 が整数となるような１より大きい整数ｎを全て決定せよ」
（答えは、「n=3」のみ。）
この証明方法を教えて欲しいです。
『フェルマーの小定理』の小定理を知っていないとまず解けない問題だそうです。
元々は、１９９０年の数学オリンピック北京大会で出題された問題ですが、日本勢で正解した人はいなかったそうです。
本では、これというのも日本の学校では初等整数論さえまともに教えてないから云々といった感じで続いていて
問題の解法には一切触れられていませんでした。
|
|
|
164 ：１３２人目の素数さん：2010/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の時に成り立つのは明らか。[証明終了]
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の時に成り立つのは明らか。[証明終了]
165 ：１３２人目の素数さん：2010/05/01(土) 12:26:20
↑自分で書き込んでおいてなんだけど、結構気に入っている解法です。
もっと簡単またはエレガントな解法はあるでしょうか？
もっと簡単またはエレガントな解法はあるでしょうか？
166 ：１３２人目の素数さん：2010/05/04(火) 00:56:26
>>164
(1) の補足
2^(p-1)≡1 (mod p) (← フェルマーの小定理)
n = ki + r, (0≦r<i) (← nをiで割った)
i|n とpの定義より i=1 または i≧p,
i<p-1 より i=1,
(2) の補足
2^n + 1 = (3-1)^2 + 1
= Σ(h=1,n) C(n,h)･(-1)^(n-k)･3^h (←二項定理)
= 3^(k+1)･d - Σ(h=2,k+1) C(n,h)･(-3)^h + N･3^(k+2), (n:奇数)
h≧2 のとき C(n,h) = n(n-1)･･･(n-h+1)/h! = (3^k)d･(n-1)･････(n-h+1)/h!,
h! の素因数分解における3の冪指数は h/2 未満。 (←補題)
∴ C(n,h)･3^h 中の3の冪指数は k-(h/2)+h = k+(h/2) ≧ k+1 より大きい。
∴ 3^(k+2) | C(n,h)･3^h
題意より 3^(k+2) | 3^(2k) | (2^n + 1),
∴ 3^(k+2) | 3^(k+1)･d
∴ 3 | d (dの定義に矛盾)
〔補題〕 h! の素因数分解におけるpの冪指数I(h,p)は h/(p-1) 未満。
I(h,p) = Σ(e=1,h) [h/(p^e)] ≦ Σ(e=1,h) h/(p^e) = {h/(p-1)}{1 - 1/(p^h)} < h/(p-1), (終)
〔参考書〕
秋山 仁＋ﾋﾟｰﾀｰ･ﾌﾗﾝｸﾙ 共著「完全攻略 数学オリンピック」日本評論社 (1991/11/20)
ISBN 4-535-78185-0 p.68〜70 (ﾐｽﾌﾟﾘﾝﾄ有り)
http://www.math.s.chiba-u.ac.jp/~ando/imo.pdf
第1回(1959) 〜 第40回(1999)の問題
(1) の補足
2^(p-1)≡1 (mod p) (← フェルマーの小定理)
n = ki + r, (0≦r<i) (← nをiで割った)
i|n とpの定義より i=1 または i≧p,
i<p-1 より i=1,
(2) の補足
2^n + 1 = (3-1)^2 + 1
= Σ(h=1,n) C(n,h)･(-1)^(n-k)･3^h (←二項定理)
= 3^(k+1)･d - Σ(h=2,k+1) C(n,h)･(-3)^h + N･3^(k+2), (n:奇数)
h≧2 のとき C(n,h) = n(n-1)･･･(n-h+1)/h! = (3^k)d･(n-1)･････(n-h+1)/h!,
h! の素因数分解における3の冪指数は h/2 未満。 (←補題)
∴ C(n,h)･3^h 中の3の冪指数は k-(h/2)+h = k+(h/2) ≧ k+1 より大きい。
∴ 3^(k+2) | C(n,h)･3^h
題意より 3^(k+2) | 3^(2k) | (2^n + 1),
∴ 3^(k+2) | 3^(k+1)･d
∴ 3 | d (dの定義に矛盾)
〔補題〕 h! の素因数分解におけるpの冪指数I(h,p)は h/(p-1) 未満。
I(h,p) = Σ(e=1,h) [h/(p^e)] ≦ Σ(e=1,h) h/(p^e) = {h/(p-1)}{1 - 1/(p^h)} < h/(p-1), (終)
〔参考書〕
秋山 仁＋ﾋﾟｰﾀｰ･ﾌﾗﾝｸﾙ 共著「完全攻略 数学オリンピック」日本評論社 (1991/11/20)
ISBN 4-535-78185-0 p.68〜70 (ﾐｽﾌﾟﾘﾝﾄ有り)
http://www.math.s.chiba-u.ac.jp/~ando/imo.pdf
第1回(1959) 〜 第40回(1999)の問題