二次剩余与欧拉函数的证明题已知p,q为素奇数且 q=2p+1,p-1为q的原根,求证明 p-1 为q的二次非剩余n为合数且 φ(n) | n-1,那么n为无平方因子数(不存在整数a,a^2 | n)且至少由3个不同的素数构成因数n

二次剩余与欧拉函数的证明题已知p,q为素奇数且 q=2p+1,p-1为q的原根,求证明 p-1 为q的二次非剩余n为合数且 φ(n) | n-1,那么n为无平方因子数(不存在整数a,a^2 | n)且至少由3个不同的素数构成因数n
二次剩余与欧拉函数的证明题
已知p,q为素奇数且 q=2p+1,p-1为q的原根,求证明 p-1 为q的二次非剩余
n为合数且 φ(n) | n-1,那么n为无平方因子数(不存在整数a,a^2 | n)且至少由3个不同的素数构成因数
n为正整数, 24 | n+1,求证24 | n的除数函数( n的正因子之和,包括自己)
3的例子:比如n=23.有1,23 |23,所以n的除数函数为1+23,再比如n=95有1,5,19,95 | 95,除数函数为120.

二次剩余与欧拉函数的证明题已知p,q为素奇数且 q=2p+1,p-1为q的原根,求证明 p-1 为q的二次非剩余n为合数且 φ(n) | n-1,那么n为无平方因子数(不存在整数a,a^2 | n)且至少由3个不同的素数构成因数n

由原根定义 (p-1)^φ(q)=1(modq)...φ(q)=2q,..所以(p-1)^p=-1(modq).由欧拉判别法可知为非二次剩余.

φ
因为无平方因子.所以n的每个素因子的幂次都等于1.即(p1-1)(p2-1).(pi-1)|n-1.假设只有两个素因子.则(p-1)(q-1)|pq-1.(p-1)|pq-1.p-1|q-1..同理q-1|p-1...所以p=q矛盾.

尝试所有余数发现-1是模24的非二次剩余.所以n的素因子幂次均为1.所以除数函数为(p1+1)...(pi+1)易知n有3k+2型的素因子和8k+7型或8k+3型和8k+5型.两种情况均能被24整除