平方數與餘數的問題

Question

1. n為自然數 323n被667除餘1 求n的最小值?
2.正整數111111111111........(有100個1)是否為完全平方數??

麻煩要加做法喔!!

prime 為什麼11^2 不能整除Q 還有為什麼這樣就可確定他不是完全平方數

Answer 1

1.
雖然原理類似，不過我還是搞不懂輾轉相除法，
我只好用Euler法。
設323n=667a+1
667a+1≡0(mod 323) → 21a+1≡0(mod 323)
設21a+1=323b
323b-1≡0(mod 21) → 8b-1≡0(mod 21)
設8b-1=21c
21c+1≡0(mod 8) → 5c+1≡0(mod 8)
數字小就方便用湊的了，
取c=3，則
b=(21c+1)/8=8
a=(323b-1)/21=123
n=(667a+1)/323=254
通解是n=254+667t，t為整數
所以n的最小值就是254
2.
若111111111111........(有100個1)是完全平方數，
因為111.....111是奇數，表示它是奇數的平方，
而奇數平方除以8必定餘1。
111....111(有100個1)除以8的餘數即為末三位111除以8的餘數，
而111除以8餘7，不合，
所以111....111(只要是2個以上的1)不可能是完全平方數，
當然也包括100個1。

Answer 2

第一題

667=23*29, 323n≡1(mod 23) → n≡1(mod 23). Let n=23a+1

323n≡1(mod 29) → 4n≡1(mod 29) → 60n≡15(mod 29)
→ 2n≡15(mod 29) → 30n≡225(mod 29) → n≡22(mod 29). Let n=29b+22

Then, n=23a+1=29b+22 → 29b+21≡0(mod 23) → 6b-2≡0(mod 23)
→ 24b-8≡0(mod 23) → b≡8(mod 23)

Hence, b=8, 29*8+22=254 → n≡254(mod 667)