[代數] 證明：奇數為原始數 iff 其為某奇質數之次方

[kyoiku (生死間有大恐怖)]

如果一整數 n 滿足下列條件，則我們稱 n 為原始數。

如果 x 為整數，且 x^2 = 1 (mod n)，
則必 x = 1 or -1 (mod n)

試證：

若一奇數 n 為原始數 <=> n 為某奇質數之次方
-----------------------------------------------------------------------------

沒啥頭緒。作了幾個例子：

3、4、5、7、9 都是原始數。
8、35 都不是原始數。


--

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 125.229.241.33
→ kyoiku      :不太清楚這該歸在代數還是數論，@@
→ keroro321   :當n是奇數,而且至少有2個質數因子,可用以下方法排除
→ keroro321   :n is odd , let n=ab , 1<a<b , gcd(a,b)=1
→ keroro321   :let 0<c<b and c = (-2) * a^(-1) (mod b)
→ keroro321   :then 1<ac+1<ab and (ac+1)^2 = 1 (mod ab)
→ keroro321   :上面少打,是 1<c<ab-1
→ keroro321   :所以當n是奇數,且為原始數,n不能有2個不同質數因子
→ keroro321   :囧...抱歉沒注意到,補打又打錯, 更正是 1<ac+1<ab-1
推 woieyufan   :數論吧