大师作文网证:2^19－1是质数,2＾31－1是质数
来源：学生作业帮 编辑：大师作文网作业帮 分类：综合作业 时间：2024/11/11 19:03:29
证:2^19－1是质数,2＾31－1是质数
证:2^19－1是质数,2＾31－1是质数
2^19－1=2^18+2^17+...+1
2^19-1=p*q,3=p*qmod4,p=4u+1,q=4v+3,p*q=(4u+1)(4v+3)=16uv+12u+4v+3
7=p*qmod8,4u+4v+3=7mod8,4u+4v=4mod8,u+v=1mod2,即u和v不是同奇偶的
15=p*qmod16,12u+4v+3=15mod16,12u+4v=12mod16,3u+v=3mod4
3(u-1)+v=0mod4
u-1=4x,v=4y or u-1=4x+1,v=4y+3 or u-1=4x+3,v=4y+3
1.u-1=4x,v=4y,u=4x+1,v=4y,
p=4u+1=16x+5,q=4v+3=16y+3
p*q=16uv+12u+4v+3=16(4x+1)*4y+12(4x+1)+4*4y+3
= 16(16xy+4y)+48x+12+16y+3
=256xy+64y+48x+16y+15
=256xy+48x+80y+15
31=16x+16y+15mod32
x+y=1mod2
看来模2^k没有什么矛盾,试着模3,看看
2^19-1=2^18+...+2^2+2^1+2^0=p*q
9*1+9*2+1=p*qmod3
1=p*qmod3
6*(1+4+2)+1=p*qmod7
1=p*qmod7
2^18+2^17+2^16+1=p*qmod31
2^3+2^2+2+1=p*qmod31
15=p*qmod31
似乎可以考虑剩余定理导矛盾
看高手怎么做
2^19－1=2^18+2^17+...+1
2^19-1=p*q,3=p*qmod4,p=4u+1,q=4v+3,p*q=(4u+1)(4v+3)=16uv+12u+4v+3
7=p*qmod8,4u+4v+3=7mod8,4u+4v=4mod8,u+v=1mod2,即u和v不是同奇偶的
15=p*qmod16,12u+4v+3=15mod16,12u+4v=12mod16,3u+v=3mod4
3(u-1)+v=0mod4
u-1=4x,v=4y or u-1=4x+1,v=4y+3 or u-1=4x+3,v=4y+3
1.u-1=4x,v=4y,u=4x+1,v=4y,
p=4u+1=16x+5,q=4v+3=16y+3
p*q=16uv+12u+4v+3=16(4x+1)*4y+12(4x+1)+4*4y+3
= 16(16xy+4y)+48x+12+16y+3
=256xy+64y+48x+16y+15
=256xy+48x+80y+15
31=16x+16y+15mod32
x+y=1mod2
看来模2^k没有什么矛盾,试着模3,看看
2^19-1=2^18+...+2^2+2^1+2^0=p*q
9*1+9*2+1=p*qmod3
1=p*qmod3
6*(1+4+2)+1=p*qmod7
1=p*qmod7
2^18+2^17+2^16+1=p*qmod31
2^3+2^2+2+1=p*qmod31
15=p*qmod31
似乎可以考虑剩余定理导矛盾
看高手怎么做