作者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