证明：素数有无穷多个

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

素数性质：若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是素数

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

Java教程