close
問2^99 mod 33 [2的99次方除以33的餘數]
問2^99mod33[2的99次方除以33的餘數]可參考數論演算法之Euler理論或費馬理論更新:數學同餘問題更新2:我看同餘運算只有說a=b(modm)c=d(modm)可以相乘合併成ac=bd(modm)可是沒看到下面這種方式:a=b(modn)c=d(modk)相乘合併成ac=bd(modnk)就是你說的"因此2^10=1(mod33)"我有點懷疑.能不能解釋一下更新3:我舉例說明:(1)2^91=2^11=2(mod11),2^7=2^3=2(mod3)以你的方式=>2^98=4(mod33)(2)2^90=2^10=1(mod11),2^8=2^2=1(mod3)以你的方式=>2^98=1(mod33)很明顯4=/=1(mod33)矛盾阿..
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-1410:53:22補充：想一下某數除以3餘1某數除以11也餘1因為(3,11)=1所以某數除以33當然也餘1呀我省略一個步驟就是2^10=(2^2)^5=1(mod3)參考資料：ME17
以上文章來自奇摩知識家，如有侵犯請留言告知
https://tw.answers.yahoo.com/question/index?qid=20100313000016KK11117