※ 引述《stu2005131 (自由幻夢)》之銘言：
: 2.
: 已知m , n為正整數，且m > n
: 若3^m 與 3^n 的末三位相同
: 求m - n的最小值
由1000|(3^m-3^n)=3^n[3^(m-n)-1]
3^n不能被2^3, 5^3整除(1000=2^3*5^3)
知1000|3^(m-n)-1
為求簡化，假設k=m-n
3^k=1 (mod 1000)
分解為 1.3^k=1 (mod 2^3=8) 觀察得知 k=2
2.3^k=1 (mod 5^3)
3^k=1 (mod 5) 觀察得知 k=4，之後都檢查4的倍數
同時是2的倍數，所以對8的餘數為1
3^ 4=81=6 (mod 25), 3^ 8=36=11 (mod 25),
3^12=66=-9 (mod 25), 3^16=-54=-4 (mod 25),
3^20=-24=1 (mod 25)，之後檢查20之倍數
3^ 5=243=-7 (mod 125), 3^10=49 (mod 125)
3^15=-343=32 (mod 125), 3^20=26 (mod 125)
3^40=(1+25)^2=1+2*25=51 (mod 125)
3^60=(1+25)*(1+2*25)=76 (mod 125)
3^80=(1+25)*(1+3*25)=101 (mod 125)
3^100=(1+25)*(1+4*25)=1 (mod 125)
最小值k=100=m-n
--
似乎有點太長
--
聰明的人喜歡猜心...
雖然每次都猜對了卻失去了自己的心
傻氣的人喜歡給心...
雖然每次都被笑了卻得到了別人的心
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.192.102.222