作者kyoiku (生死間有大恐怖)
看板Math
標題[代數] 證明：奇數為原始數 iff 其為某奇質數之次方
時間Fri May 20 11:44:08 2011
如果一整數 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
1F：→ kyoiku :不太清楚這該歸在代數還是數論，@@ 05/20 11:45
2F：→ keroro321 :當n是奇數,而且至少有2個質數因子,可用以下方法排除 05/20 15:56
3F：→ keroro321 :n is odd , let n=ab , 1<a<b , gcd(a,b)=1 05/20 15:57
4F：→ keroro321 :let 0<c<b and c = (-2) * a^(-1) (mod b) 05/20 15:58
5F：→ keroro321 :then 1<ac+1<ab and (ac+1)^2 = 1 (mod ab) 05/20 15:58
6F：→ keroro321 :上面少打,是 1<c<ab-1 05/20 16:00
7F：→ keroro321 :所以當n是奇數,且為原始數,n不能有2個不同質數因子 05/20 16:02
8F：→ keroro321 :囧...抱歉沒注意到,補打又打錯, 更正是 1<ac+1<ab-1 05/20 16:20
9F：推 woieyufan :數論吧 05/20 23:20