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

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

166:１３２人目の素数さん
10/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 (ﾐｽﾌﾟﾘﾝﾄ有り)

URLﾘﾝｸ(www.math.s.chiba-u.ac.jp)
　第1回(1959) ～第40回(1999)の問題

次ページ

続きを表示

1を表示