推 kyoiku :感謝大師 ORZ 05/21 07:36
我只是業餘的數學愛好者 不要亂叫
※ 編輯: JohnMash 來自: 112.104.141.226 (05/21 09:09)
※ 引述《kyoiku (生死間有大恐怖)》之銘言：
: 如果一整數 n 滿足下列條件，則我們稱 n 為原始數。
: 如果 x 為整數，且 x^2 = 1 (mod n)，
: 則必 x = 1 or -1 (mod n)
: 試證：
: 若一奇數 n 為原始數 <=> n 為某奇質數之次方
: -----------------------------------------------------------------------------
: 沒啥頭緒。作了幾個例子：
: 3、4、5、7、9 都是原始數。
including 2
: 8、35 都不是原始數。
(i)
n is odd and n=p^m
p is odd prime
x^2=1(mod p^m)
(x+1)(x-1)=h*p^m
(x+1,x-1)=(x+1,2)=1 or 2
hence, p^m | (x+1) or p^m | (x-1)
that is, x=1 or -1 (mod p^m)
(ii) n is odd and n=S*T
and S,T are different odd numbers
and S>T≧3
and (S,T)=1
Hence, there exists integers a,b such that
aS-bT=2
then
(a+kT)S-(b+kS)T=2
hence, we may take
1≦a≦T-1
and aS-bT=2
Let x=aS-1=bT+1
S-1≦x≦ST-S-1
hence, x≠±1 (mod ST)
but, x^2=(aS-1)(bT+1)=abST+aS-bT-1=1 (mod ST)
Done.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 112.104.114.134