素数有哪些数字,常见的素数的判断

素数又称为质数,其定义是在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数;否则称为合数。素数和合数是一组相对的概念(规定1既不是素数也不是合数)。

人类在很早的时候就开始研究素数了,神秘的素数令无数数学家为之魂牵梦绕。在数学中就有一门分支学科专门研究素数(整数)及其性质,称为数论,你一定听闻过我国数学家陈景润攻克哥德巴赫猜想的故事吧,讲的就是这个。

素数从2开始,后续有3、5、7、11等等等等,你是否有这样的疑问:假如素数如果可数,是否可以数完?换句话说,素数是有限个的还是无穷的?

素数有哪些数字,常见的素数的判断

答案是无穷多个的。今天大小吴就将为大家介绍一下“素数有无穷多个”的4种证明方法~

在此之前,我们首先来了解一下“算数基本定理”。

算数基本定理:设为一个大于1的自然数,则有

其中为某自然数,是素数,并且在不记素数排列次序的意义下,上式分解是唯一的。

1 Euclid的证明

关于素数有无穷多个的证明,早期经典的证明可以追溯到欧几里得(Euclid)的《几何原本》。这也用到了数学中的反证法。

素数有哪些数字,常见的素数的判断

  • 假设是全部素数,
  • 令,并且为的一个素因数。
  • 则,
  • 否则
  • 所以是一个新的素数,
  • 所以假设不正确,因此素数有无穷多个。

2 Hermite的证明

第二个证明来自法国数学家埃尔米特(Hermite),过程也是非常简洁优美。

素数有哪些数字,常见的素数的判断

  • 考虑任意的正整数,只需证明必存在大于的素数即可。
  • 构造
  • 若为素数,则结论成立;
  • 若为合数,对于任意的正整数,都不能整除,则必存在一个比大的素数,有。
  • 因此素数有无穷多个。

3 利用费马数证明

另一个证明来源于数学史上一个著名的乌龙事件,数学家费马发现对于

前五个数~均为素数,于是他猜想所有的都是素数,费马没给出证明(他经常这样干)。

素数有哪些数字,常见的素数的判断

有趣的是,天降神人数学猛男欧拉发现

利用费马数证明素数无限可以遵循如下思路:

证明费马数两两互素⇒每个费马数都有其独特的素因数(费马素数的素因数即是它本身)⇒无限的费马数对应无限的素数

后面两步比较好理解,现在只需证明的即是费马数两两互素。考虑如下递推式:

  • 对于上述递推关系的证明可以简单地用数学归纳法证明:

1)易知,,则当时,有

成立

2)当时,

也成立

事实上,对于任意两个不同的费马数和,则由递推关系可知

继而由辗转相除法可知

  • 但由于所有的费马数均为奇数,所以
  • 即任意两个费马数互素,证明完毕。

4 数学归纳法

最后一个证明遵循的原理是数学归纳法,非常巧妙。

  • 任取素数,则有,即
  • 因此的素因数中,至少存在1个不等于的素因数,
  • 令,

则的素因数中,存在2个互不相等的素因数、。

  • 同理因为,因此的素因数中,至少存在1个不等于和的素因数,
  • 令,

则的素因数中,存在3个互不相等的素因数、、。

  • 假设至少有个互不相等的素因数,
  • 因为,因此的素因数中,至少存在1个不等于、、
  • 令,

则的素因数中,存在个互不相等的素因数、、、…、。

  • 由数学归纳法可知,素数有无穷多个。
派优网部分新闻资讯、展示的图片素材等内容均为用户自发上传(部分报媒/平媒内容转载自网络合作媒体),仅供学习交流。用户通过本站上传、发布任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权,请联系我们一经核实,立即删除。并对发布账号进行封禁。
(0)
爱生活的头像爱生活

相关推荐

返回顶部