推 coolbetter33: 我也覺得用mod來證.有更好的做法(眼神死) 06/12 02:22
推 JI1 : love does not know 06/12 08:38
→ Desperato : mod證奇數n秒殺 可是偶數n不知道怎麼辦 06/12 08:47
※ 引述《kku6768 (類)》之銘言：
: 如何證明
: 1^100+2^100+3^100+...+2012^100會被1006整除??
: 不知從何下手?
(果然出包了XD 已訂正版本)
定義 f(n) = 1^n + 2^n + ... + p^n, p odd prime
證明若 n < p-1 則, p | f(n)
p p n+1
sum (k+1)^(n+1) = sum sum C(n+1, t) k^t
k=1 k=1 t=0
n+1 p
= sum sum C(n+1, t) k^t
t=0 k=1
n p
= sum C(n+1, t) f(t) + sum k^(n+1)
t=0 k=1
n-1
因此 (n+1) f(n) = (p+1)^(n+1) - 1 - sum C(n+1, t) f(t)
t=0
現在 f_p(0) = p, p 整除 (p+1)^(n+1)-1
n < p-1 所以 p 不整除 n+1, 根據數學歸納法得到 p | f(n)
現在 1006 = 2*503, 503 prime
100 < 503, 原式被503整除 顯然也被2整除 因此是1006的倍數
...應該有更好的做法(眼神死)
p.s. n >= p-1 的 case 可以用費馬小定理
f(n) = p-1 (mod p) if (p-1) | n
= 0 (mod p) otherwise
沒有全部都整除有點可惜...ow o
--
嗯嗯ow o
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1497196333.A.B39.html
※ 編輯: Desperato (140.112.25.105), 06/12/2017 00:33:02