求大數的餘數

Question

求2^100除以7的餘數
我們常用同餘來算上述的問題，方法大概是把指數變小，底數不要讓它太大，直到數字小到我們可以容易筆算為止。
例如上題，2^100≡16^25≡2^25≡2*8^8≡2*1^8≡2(mod 7)
所以餘2
但是如果數字大一點呢？
例如求2^178除以74的餘數
目前我只想到這樣，
根據費馬小定理，2^36≡1(mod 37)，故2^144≡1(mod 37)，2*2^144≡2*1(mod 2*37)，2^145≡2(mod 74)，因此2^178≡2^145*2^33≡2*2^33≡2^34(mod 76)
而
2^7/76≒1.6842
2^8/76≒3.3684
2^9/76≒6.7368
2^10/76≒13.4736
2^11/76≒26.9473
取小數點後一位是9或0的來用，2^11≡(-4)(mod 76)
2^178≡2^34≡2*(2^11)^3≡2*(-4)^3≡-128≡24(mod 76)
可是這樣還是很繁複，請問有沒有更快的？

Answer 1

數字大一點就只能用費馬小定理了不過你這題有個比較快的方法236≡1≡38(mod37)235≡19≡56(mod37)234≡28(mod37)233≡14(mod37)2177≡236*4+33≡233≡14(mod37)所以2178≡28(mod74)

Answer 2

糟糕，我在寫的時候，一再改題目，居然改到自己都算錯了。