YLL討論網

證明:
可被1001整除.


[我記得這應該可以利用費馬小定理...]

不懂什麼定理，以下是用高中程度的解法

只要證300^300除以1001餘1即可

300^300  (mod 1001)
=(300^3)^100  (mod 1001)
=27^100  (mod 1001)
=(27^4)^25  (mod 1001)
=(-90)^25  (mod 1001)
=[(-90)^5]^5  (mod 1001)
=1^5  (mod 1001)
=1

得證

300^300-1≡300^(42*7+6)-1≡300^6-1≡0(mod 7)
300^300-1≡300^(30*10)-1≡(300^10)^30-1≡0(mod 11)
300^300-1≡300^(23*13+1)-1≡300-1≡0(mod 13)
∴300^300-1≡0(mod 1001)

piny 寫到:不懂什麼定理，以下是用高中程度的解法

只要證300^300除以1001餘1即可

300^300  (mod 1001)
=(300^3)^100  (mod 1001)
=27^100  (mod 1001)
=(27^4)^25  (mod 1001)
=(-90)^25  (mod 1001)
=[(-90)^5]^5  (mod 1001)
=1^5  (mod 1001)
=1

得證

請問:
=(300^3)^100=27^100  (mod 1001)這裡是如何得到的?
還有:=(27^4)^25  (mod 1001)=(-90)^25  (mod 1001)這裡呢?

宇智波鼬 寫到:

piny 寫到:不懂什麼定理，以下是用高中程度的解法

只要證300^300除以1001餘1即可

300^300  (mod 1001)
=(300^3)^100  (mod 1001)
=27^100  (mod 1001)
=(27^4)^25  (mod 1001)
=(-90)^25  (mod 1001)
=[(-90)^5]^5  (mod 1001)
=1^5  (mod 1001)
=1

得證

請問:
=(300^3)^100=27^100  (mod 1001)這裡是如何得到的?
還有:=(27^4)^25  (mod 1001)=(-90)^25  (mod 1001)這裡呢?

300^3=27000000=1001*26973+27
所以其100次方之展開除以1001，其餘數必等於27^100除以1001之餘數(因為其他項數都為1001之倍數)

27^4=531441=1001*531-90，之後解釋同上