脈衝光

7的N次方的餘數Question: 7^(37^102)這個數除以11所得的餘數為？請別拿計算機算了，按的出來的計算機我想應該不多…令A=117^n = k×A + B ← B是我們要的數7^n = kn×A + Bn 寫成這樣7^1= k1×A + 7 (我們都知道k1=0, 但不是重點)7^2= (k1×A + 7)×(k1×A + 7) = (7×k1×A+7×k1×A+(k1A)^2) + 49 = (K)A + 44 + 5 = k2×A + 57^3= (k2×A + 5)×(k1×A + 7) = (K)A + 5×7 = (K+3)A + 2 = k3×A + 2我們只在乎餘數，故無論是(K)A還是k，都是A的倍數，是多少都不是重點，實際上我們只需要計算紅色文字、餘數的部份n=4, B4 = (2×7) mod (11) = 3n=5, B5 = (3×7) mod (11) = 10上面有點亂，重列一次7^1~7^10(表1)n=1, B1=7 n=2, B2=5n=3, B3=2n=4, B4=3n=5, B5=10n=6, B6=4n=7, B7=6n=8, B8=9n=9, B9=8n=10, B10=1 (以下循環)由於是10循環也就是說，我們只需要知道37^102的個位數部份是多少即可(我們用的數學剛好是10進位的關係)(30+7)^n = (30+7) (30+7) (30+7) (30+7) (30+7) (30+7) (30+7) … (n個相乘)= 30^n + 30^(n-1)×(7) + 30^(n-2)×(7^2) + … + 30×7^(n-1) + 7^n展開後看起來又是露露長的一串，實際上我們只在乎7^n部分，因為綠字部分可以提出一個30，一定是10的倍數，而我們只在乎個位數而已。7^102也不需要完全算出來，同樣只在乎個位數而已。7^1=77^2=497^3=??3 (?9×7=??3)7^4=???1 (??3×7=???1) 看到1就循環了，4循環7^5=????7 那麼，7^102的個位數是多少？102÷4 = 25…2餘2，所以7^102的個位數是9對照一下表1，n=9，B9 = 8答案為8。最後：我沒有驗證這個答案。數學我也不是很強，只能想到這種算法了。進階可參考任何整數的N次方除以任何整數的餘數這篇。 .msgcontent .wsharing ul li { text-indent: 0; } 分享 Facebook Plurk YAHOO! .