末位數問題

[happier]

2^2002-1的末四位數該怎麼求呢
謝謝。

[thepiano]

您是不是在做 96 中一中的第 8 題啊？
那題最後是求 2002^2 - 1 的末四位！


而您問的這題是 2^2002 - 1 的末四位，通常只會問 2^2002 的末四位啦！

利用以下定理
a^ψ(p) ≡ 1 (mod p)，其中 a 和 p 互質
ψ(p)：不大於正整數 p，且和 p 互質的正整數個數

ψ(625) = 625 * (1- 1/5) = 500
2^500 ≡ 1 (mod 625)

2^2000 = (2^500)^4 ≡ 1 (mod 625)
令 2^2000 = 625k + 1 = 624k + (k + 1)
由於 2^2000 是 4 的倍數，故 k + 1 亦為 4 之倍數，令 k = 4m - 1
2^2000 = 625(4m - 1) + 1 = 2500m - 624
2^2002 = 4(2500m - 624) = 10000m - 2496 ≡ 7504 (mod 10000)

[happier]

謝謝thepiano老師的發現
是中一中那題沒錯
我果然看錯了
難怪我把它想複雜了
謝謝。

[happier]

想照著thepiano老師的做法找出3^100的末四位數
可是只想到3^100 ≡ 1(mod 125)
接下來怎麼找呢
感謝

[thepiano]

找出3^100的末四位數

這題大概只能用電腦來算了 ......