Java教程

证明:素数有无穷多个

本文主要是介绍证明:素数有无穷多个,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

素数性质:若a为合数,则a的最小真因子为素数p,故 p|a (即,a = p*q,a,p,q 属于整数)

来源:欧几里得《几何原本》

证明:

假设:只有有限个素数,分别是:2,3,5,7,…,Pn

构造一个数:a = 2*3*5*7*…*Pn + 1 

现在a要么是素数,要么不是素数

1)如果a是素数,那么a是不在我们列表中的素数

2)如果a是合数,那么a的最小真因子为素数p,即 p|a,从而 p | 2*3*5*7*…*Pn + 1

又因为p属于 {2,3,5,7,…,Pn},所以 p | 2*3*5*7*…*Pn

p | 2*3*5*7*…*Pn + 1 且 p | 2*3*5*7*…*Pn ⇔ 对任意的x,y 属于 Z 有 p | x *(2*3*5*7*…*Pn + 1)+ y * 2*3*5*7*…*Pn 

因为是x,y是任意的,令x=1,y=-1,则:p | 1,故 p=1,或p=-1,与p为素数不符合,此情况不存在,a不能是合数

综上所述,a是素数

 

这篇关于证明:素数有无穷多个的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!