試證991^991+993^993能被1984整除

試試:991^991+993^993
=993^991(993^2-991^2)+991^991+993^991*991^2
=991^2(991^989+993^991) mod1984

1984=31*64
1.991^991+993^993同餘(-1)^991+(1)^991同餘0 (mod 31)
2.991同餘31 (mod64) → 991^2同餘31^2同餘1 (mod64)
993同餘33 (mod64) → 993^2同餘33^2同餘1 (mod64)
故991^991+993^993=991*991^990+993*993^992
同餘31*1^495+33*1^496
同餘31+33=64
同餘0 (mod 64)

故原式同時為31的倍數及64的倍數，即為1984的倍數

ttoomm916提供的解法乃是連續提出991^2，
經操作後剩下991+993^3，如此可被1984整除

在此也提供三個作法，供做參考
1.
991^2=(992-1)^2=992^2-2*992+1=1984(496-1)+1
同理993^2=1984(496+1)+1
因此991^991+993^993=(991^2)^495*991+(993^2)^496*993
除以1984的餘數為可視為(991+993)除以1984，可整除

2.
n為奇數時，x+y|x^n+y^n，x-y|x^n-y^n
991^991+993^993
=(991^991+993^991)+(993^993-993^991)
=1984A+993^991(993^2-1)
=1984A+993^991(993+1)(993-1)
=1984A+993^991*(497)*(1984)
=1984A+1984B=1984(A+B)
故991^991+993^993可以被1984整除

3.
本題屬特例，在2次方後餘數即呈規律循環
但最好的做法還是先將被除數和除數分別因式分解
1984=2^6*31，991與2,31互質
2^(6-1)=32，故991^32(mod 64)=1，另991^30(mod 31)=1
[32,30]=480，故991^480(mod 1984)=1
但因2|480，檢驗得知991^2(mod 1984)=1
同理993=3*331，分開討論後得知結果相同
因此(991^991+993^993)(mod 1984)
=(991+993)(mod 1984)=0

當然這個方法看來繁複，但適用所有被除數與除數較複雜情況，尤其當被除數和除數經因式分解後，彼此間含其他共同質因數，在考慮餘數時其次數不得做約分互消，此時就不能用前兩種方法取巧

4.吃晚嶽氶A有幸碰到神豬，向他討教此題，他不假思索告訴我解法，重重擊了我一拳
　　991(mod 1984)= - [993(mod 1984)]
因此(991^991+993^993)(mod 1984)
=993^991(993^2-1)(mod 1984)
=993^991(993+1)(993-1)(mod 1984)=0

　　cfc21的解法踏到人多數人的痛苦點，那就是當詳細去解剖問題時，會讓人不想去碰問題，因為頭會破掉，同時脫殼好幾次．也會發現更多讓人懶得去碰的問題．
　　在網友learing提出1^2006+2^2006+.....9^2006=？問題時，我曾經就a^2006要求神豬探討餘數的循環規律，頗有收穫，今將心得略舉一例分享如下．

1.
設a為小於p且與p互質的自然數，m與p互質，則am(mod p)之所有數必為所有a值的一個排列
證明：設A={r1,r2,r3,.....rp-1}，A為小於p的自然數除以p所得之餘數集合．
a為A之元素，則am(mod p)所得之數必屬A之元素之一
設b亦為A中元素，且a不等於b，若am=bm(mod p)，則(a-b)m=0(mod p)，
因m，p互質，故a=b(mod p)，而a,b均小於p，故a=b，與假設矛盾，
故am(mod p)之所有數必為所有a值的一個排列

2.
設a為小於p且與p互質的自然數，則a^(p-1)(mod p)=1
證明：設A={r1,r2,r3,.....rp-1}，A為小於質數p的自然數除以p所得之餘數集合，a與p互質
則ar1*ar2*ar3*.......arp-1(mod p)=a^(p-1)*r1*r2*r3*......rp-1(mod p)
故a^(p-1)(mod p)=1
如果你對1,2點沒有興趣，那只要曉得a^(p-1)(mod p)=1就可以，問題是你能夠忍受一知半解嗎？

3.
對於質數p，設自然數a小於p-1且不等於1，a與p互質，已知a^(p-1)(mod p)=1
考慮p-1的因數m，在a^m時可能成立a^m(mod p)=1，特別在m=(p-1)/2的情形下
a^m(mod p)可能為1或-1，以p=59舉例說明如下：
已知a=1,2,3.......58時，a^59除以59的餘數均為1，但a^29除以59的餘數可能為1,或58
在此將餘數1或58改成1或-1，就a=1,2,3.......58時，討論a^29除以59的餘數

方法：令m(a)=1或-1，m(a)為a^29除以59的餘數
1.a^59=(a^29)^2，故[m(a)]^2=1
2.m(59k+a)=m(a)，m(59k-a)=-m(a)，當k=1時，m(59+a)=m(a)，m(59-a)=-m(a)

我們取a=64,60先求出m(5)與m(3)
m(5)=m(64)=(m(2))^6=1，故5^29除以59的餘數為1
m(60)=1，[m(2)]^2*m(3)*m(5)=1，m(3)=1，故3^29除以59的餘數為1
接下來我們求m(2)，亦即2^29除以59的餘數
m(32)=-m(27)，因[m(2)]^2=[m(3)]^2=1，故m(2)=-m(3)=-1
故2^29除以59的餘數為58
如此，我們可應用以上方法陸續求出a^29除以59的餘數
整理a=1~29時m(1)=1，m(2)=-1，m(3)=1，m(4)=1，m(5)=1，m(6)=-1，
m(4)=m(63)=m(7)=1，故m(7)=1，m(8)=-1，m(9)=1，m(10)=-1，
m(11)=-m(48)=-1，m(12)=1，m(13)=m(52)=-m(7)=-1，m(14)=-1，
m(15)=1，m(16)=1,m(17)=-m(42)=1，.............................，
m(29)=-m(30)=-m(2)*(m3)*m(5)=1
m(30)=-m(29)，a=30~59餘數與a=1~29成對稱負餘關係
輔助VBA程式如下:使用一個按鈕執行程式並使用一個列表框(listbox)輸出結果

for i=1 to 58
k=1
for j=1 to 29
k=k*i
k=k-59*int(k/59)
next
if k=58 then k=-1
listbox1.additem str(i)+":"+str(k)
next

輸出結果如下:
1:1
2:-1
3:1
4:1
5:1
6:-1
7:1
8:-1
9:1
10:-1
11:-1
12:1
13:-1
14:-1
15:1
16:1
17:1
18:-1
19:1
20:1
21:1
22:1
23:-1
24:-1
25:1
26:1
27:1
28:1
29:1
30:-1
31:-1
32:-1
33:-1
34:-1
35:1
36:1
37:-1
38:-1
39:-1
40:-1
41:1
42:-1
43:-1
44:-1
45:1
46:1
47:-1
48:1
49:1
50:-1
51:1
52:-1
53:1
54:-1
55:-1
56:-1
57:1
58:-1
　　

後記:
　　即使在求學時代對數學有點基礎，在面對以上的問題也是從一無所知，因著這個機會而能有進一步的接觸，或釦A對討論這樣的題目沒有興趣，但請找出原因，為什麼喜歡數學的您，對於未知的領域，失去了好奇與衝動．

　　如果一位僅有國小程度的年輕人，他會開車，有一天他帶著他的車回到幾千年的時代，或野L就是那個時代的資優生，或者被當成神，只要他不說出秘密，沒有人會懂得如何去駕駛車輛，甚至他不交出發動時所需的鑰匙，則沒有人曉得這個最開始的關鍵．

　　這就是我樂於分享孩子學習過程的原因，我們原可默默自得其樂，但我們明白到，學習方法的改變與教育方法的重要，使得我們的孩子比起以前的人更加優秀，同時一些普通的孩子，也可以在花費較少的時間，比別人看起來懂得多，其中並沒有什麼值得誇耀之處．