作者JohnMash (Paul)
看板Math
标题Re: [代数] 证明：奇数为原始数 iff 其为某奇质数ꐠ…
时间Fri May 20 14:17:17 2011
※ 引述《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
1F：推 kyoiku :感谢大师 ORZ 05/21 07:36
我只是业余的数学爱好者 不要乱叫
※ 编辑: JohnMash 来自: 112.104.141.226 (05/21 09:09)