問2^99 mod 33 [2的99次方除以33的餘數]

2^5≡32≡-1(mod 33)，
所以2^95≡32^19≡(-1)^19≡-1(mod 33)，
所以2^99≡2^95 * 2^4≡(-1)*16≡-16≡17(mod 33)
如果一定要捨近求遠用費馬小定理的話，
2^99≡2^97≡2^95≡2^93≡.......≡2^1≡2(mod 3)
2^99≡2^89≡2^79≡2^69≡.......≡2^9≡6(mod 11)
令2^99=x，則
x≡2(mod 3) → 同乘以11，11x≡22(mod 33)___甲
x≡6(mod 11) → 同乘以3，3x≡18(mod 33)___乙
甲減乙，
8x≡4(mod 33)，
4與33互質，可同除以4，2x≡1≡1+33≡34(mod 33)，
2與33互質，可同除以2，x≡17(mod 33)。

沒有這種性質：
a≡b (mod n)
c≡d (mod k)
相乘合併成ac≡bd (mod nk)
但有這種性質：ak≡bk (mod nk)

根據費馬定理
3是質數 所以2^2=1(mod3)
11是質數 所以2^10=1(mod11)
因此2^10=1(mod33)
2^99=(2^10)^9*2^9=2^9=512=17(mod33)

另外一種算法
顯然2^5=32=-1(mod33)
2^99=(2^5)^19*2^4=(-1)^19*16=-16=17(mod33)


2010-03-14 10:53:22 補充：
想一下
某數除以3餘1
某數除以11也餘1
因為(3,11)=1
所以某數除以33當然也餘1呀

我省略一個步驟 就是2^10=(2^2)^5=1(mod3)

17