[數學] 同餘定理

Question

(怎麼利用同餘定理解題)
2的50次方 除以5之餘數為?

不好意思再問一題～
我可以理解第二位大大的算法
可是假如遇到這種題目: 4的100次方除以63之餘數?
要怎麼代換?因為代出來數字有點大~不太清楚怎麼計算ㄟ

Answer 1

通常這種問題都是循環的
2的一次方 / 5...........2
2的平方 / 5 ..............4
2的三次方 / 5 ..........3
2的四次方 / 5 ..........1
2的五次方 / 5 ..........2
2的六次方 / 5 ..........4
2的七次方 / 5 ..........3
依此類推
故每四個一循環
50 / 4 ....2
故2的五十次方 / 5 等於 4
餘數為4

那你另外問的那題也是用一樣的方法
4的一次方 / 63 ..........4
4的平方 / 63 ..............16
4的三次方 / 63 ..........1
4的四次方 / 63 ..........4
4的五次方 / 63 ..........16
4的六次方 / 63 ..........1
依此類推
故每三個一循環
100 / 3 .....1
得到4的一百次方 / 63 ......4
餘數為4

Answer 2

時代不同

觀念也不同


同餘感覺滿難的!!

Answer 3

同餘定理？有這種說法嗎？同餘式用到的定理很多，而且都很常用，都重要，應該沒有單獨一個可以稱為同餘定理吧！就好像沒有一元一次方程式定理一樣。250≡425≡(-1)25≡-1≡4(mod 5)很簡單呀！至於你補充的問題.....4100≡4*(64)33≡4*133≡4(mod 63)技巧在於把指數變小，不一定要把指數的因數放下來，非因數也行。上例中，3就不是100的因數。不過你舉這個例子還太簡單了，因為64和63只差1而已，如果是2200除以77的餘數呢？筆算而且不用其他定理的話，那我們就找2的前幾個乘冪中最接近77者，64比128更接近77，所以選64來降次，接下去都一樣，選底數的前幾個乘冪中最接近77的倍數者來降次，(為什麼是前幾個？因為後幾個就太大了)2200≡4*6433≡4*(64-77)33≡4*(-13)33≡4*(-13)*(169)16≡4*(-13)*(169-2*77)16≡4*(-13)*1516≡4*(-13)*2258≡4*(-13)*(225-77*3)8≡4*(-13)*(-6)8≡4*(-13)*36*2162≡4*(-13)*36*(216-77*3)2≡4*(-13)*36*(-15)2≡4*(-13)*36*225≡-52*36*(225-77*3)≡(-52+77)*36*(-6)≡25*(-216)≡25*(-216+77*3)≡25*15≡375≡67(mod 77)嗯！果然很複雜，其實有比較簡略的方法啦！不過我用得不純熟就是了。

Answer 4

原式＝（２¹º）的5次方
　　→１０２４除５餘４
　　→４的５次方除５餘４
２的５０次方除以５的餘數為４

Answer 5

2^50 = (2^2)^25 = 4^25

4^25(mod5) ≡ (-1)^25(mod5) ≡ -1(mod5) ≡ 4(mod5)

Ans: 4