發新話題
打印

111樟樹高中

原來前幾天ptt問的是這份
ptt是用中國剩餘定理去做的可以參考一下
如果用費馬尤拉定理會變成
\( 2^{\phi(1000)}=2^{400}\equiv1(mod1000) \)
這樣可能比較快

#上述方法有誤,因為\(\gcd(2,1000)\ne1\)
\(2^{2023}\equiv0(mod8),2^{2023}=(2^{100})^{20}\cdot2^{23}\equiv108(mod125)\)
由輾轉相除法知\(1=(-3)\times125+47\times8\)
\(2^{2023}\equiv0\times125\times(-3)+108\times8\times47\equiv608(mod1000)\)

TOP

發新話題