二次剩余与欧拉函数的证明题已知p,q为素奇数且 q=2p+1,p-1为q的原根,求证明 p-1 为q的二次非剩余n为合数且 φ(n) | n-1,那么n为无平方因子数(不存在整数a,a^2 | n)且至少由3个不同的素数构成因数n
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/27 10:35:21
![二次剩余与欧拉函数的证明题已知p,q为素奇数且 q=2p+1,p-1为q的原根,求证明 p-1 为q的二次非剩余n为合数且 φ(n) | n-1,那么n为无平方因子数(不存在整数a,a^2 | n)且至少由3个不同的素数构成因数n](/uploads/image/z/8745739-43-9.jpg?t=%E4%BA%8C%E6%AC%A1%E5%89%A9%E4%BD%99%E4%B8%8E%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0%E7%9A%84%E8%AF%81%E6%98%8E%E9%A2%98%E5%B7%B2%E7%9F%A5p%2Cq%E4%B8%BA%E7%B4%A0%E5%A5%87%E6%95%B0%E4%B8%94+q%3D2p%2B1%2Cp-1%E4%B8%BAq%E7%9A%84%E5%8E%9F%E6%A0%B9%2C%E6%B1%82%E8%AF%81%E6%98%8E+p-1+%E4%B8%BAq%E7%9A%84%E4%BA%8C%E6%AC%A1%E9%9D%9E%E5%89%A9%E4%BD%99n%E4%B8%BA%E5%90%88%E6%95%B0%E4%B8%94+%CF%86%28n%29+%7C+n-1%2C%E9%82%A3%E4%B9%88n%E4%B8%BA%E6%97%A0%E5%B9%B3%E6%96%B9%E5%9B%A0%E5%AD%90%E6%95%B0%28%E4%B8%8D%E5%AD%98%E5%9C%A8%E6%95%B4%E6%95%B0a%2Ca%5E2+%7C+n%29%E4%B8%94%E8%87%B3%E5%B0%91%E7%94%B13%E4%B8%AA%E4%B8%8D%E5%90%8C%E7%9A%84%E7%B4%A0%E6%95%B0%E6%9E%84%E6%88%90%E5%9B%A0%E6%95%B0n)
二次剩余与欧拉函数的证明题已知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整除