駭客數學 p10-29

[acdimns]

1.試求123456789^25的末兩個數字?
ANS:49

2.12^12乘開後的十位數字是多少?
ANS:5

[thepiano]

第 1 題
123456789 ≡ 89 ≡ -11 (mod 100)
123456789^25 ≡ 89^25 ≡ (-11)^25 ≡ -11^25 (mod 100)
-11^25 = -(10 + 1)^25 = -[..... + C(25，24) * 10 + C(25，25)] = -(...... + 251)
以上 ...... 是 100 的倍數
故所求為 -251 + 300 = 49


第 2 題
12^12 = (10 + 2)^12 = ..... + C(12，11) * 10 * 2^11 + C(12，12) * 2^12 = ...... + 120 * 2048 + 4096 = ...... + 249856
以上 ...... 是 100 的倍數
故所求為 5

[acdimns]

第一題的符號是同餘嗎?
不太清楚123456789 ≡ 89 ≡ -11 (mod 100)是什麼意思?
我在網路上有找到一個做法前面懂,不過倒數第四行開始變成負號就無法理解了...
想請老師看一下,

先備知識:排列組合的二項式定理展開
123456789^2=(123456700+89)^25展開式中只最後一項會影響到末兩字,
所以只要算出(C25取25*89^25)之末兩字即可,因為展開式其他項都會乘上123456700,末兩位均為0,
89^25=(100-11)^25展開式中只最後一項會影響到末兩字,
所以只要算出(C25取25*(-11)^25)之末兩字即可,因為展開式其他項都會乘上100,末兩位均為0,
(-11)^25=-(10+1)^25展開式中只最後兩項會影響到末兩字,
所以只要算出(C25取25*(-11)^25)之末兩字即可,因為展開式其他項都會乘上100,末兩位均為0,
C25取24*10*1^24+C25取25*1^25=251
所以末兩位為-51=100-51=49

[thepiano]

≡ 是同餘的符號沒錯

123456789 ≡ 89 ≡ -11 (mod 100)
表示 123456789，89，-11 這三數除以 100 的餘數相同

49 除以 100，餘數是 49
49 + 100 = 149，149 除以 100，餘數還是 49
149 + 100 = 249，249 除以 100，餘數還是 49
......
同理
49 - 100 = -51，-51 除以 100，餘數是 49
-51 - 100 = -151，-151 除以 100，餘數還是 49
-151 - 100 = -251，-251 除以 100，餘數還是 49

您找到的做法，其實跟小弟的方法一樣，再把小弟的式子看一次吧！

[acdimns]

謝謝老師,不過我看了很多遍,也想了好久,
不懂末兩位數字怎麼會跟同餘有關?
又為什麼要除以100?
最後整個答案算出來251,
末兩位怎麼不是51呢?
不好意思,實在很困惑...

[thepiano]

1. 一個數的末兩位數字 = 它除以 100 的餘數
例如 349 的末二位是 49，而 349 除以 100 的餘數是 49

2. 這題的 123456789^25 很大，要求出它的末兩位數字，比較快的方法是用同餘的概念把數字變小，因為餘數仍是跟原題目要求的一樣

3. 最後算出來的答案是 -251，不是 251

4. 上面說過，把一個數加上 100 的倍數，它除以 100 的餘數仍相同，所以把 -251 + 300 = 49 ，這就是題目要求的
因為除以 100，通常我們會把餘數的範圍定在 0 ~ 99 之間

[acdimns]

謝謝!