9473

求大數的餘數

求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.68422^8/76≒3.36842^9/76≒6.73682^10/76≒13.47362^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)可是這樣還是很繁複

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

我在寫的時候

一再改題目

居然改到自己都算錯了。

費馬小定理證明,費馬小定理 應用,費馬小定理 題目費馬小定理,餘數,大數,同餘,mod,數字,方法,小數點,除以,問題

分數|多項式|商高定理|方程式|開根號|拋物線|質數|心算|代數|等比級數|內角和|離散數學|圓周率|矩陣|證明題|體積換算|機率|複數|負數|畢氏定理|演算法|幾何|統計學|長度換算|不等式|微積分|三角函數|雙曲線|向量|倍數|數獨|平均數|面積換算|對角線|小數|分解式|因數|進位法|

9473
參考:http://tw.knowledge.yahoo.com/question/question?qid=1105062208072如有不適當的文章於本部落格，請留言給我，將移除本文。謝謝！