日志
找素数
热度 8 |
很奇怪为什么一直有人在努力找更大的素数。按照欧几里得的素数是无限的证明，找一个比已知的素数更大的素数不是显而易见的吗？只要把已知的所有素数相乘的结果加1，不就得到了吗？
附欧几里得的证明：
假设素数只有有限个，按照大小顺序，分别记为：
。最大的素数
。
。最大的素数。所有素数乘积加1为：
现在考虑s是什么？
如果s是素数， 
，与假设矛盾。
，与假设矛盾。如果s是合数，s不能被已知素数整除，矛盾，说明原来假设素数是有限的是错误的。
证毕。
发表评论 评论 (11 个评论)
- 回复 东中
- 不是找最大的素数，而是人们一直在找更大的素数，素数在密码学中有实际应用。看不到你的证明，不知道你是不是想说“把已知的素数相乘的结果加1就得到一个新的素数。”，如果想说明这个，我举个反例，3×7=21+1=22。如果我理解错了，请告诉我，我删除。
- 回复 zhouzp
- 是我笔误了：
东中: 不是找最大的素数，而是人们一直在找更大的素数，素数在密码学中有实际应用。看不到你的证明，不知道你是不是想说“把已知的素数相乘的结果加1就得到一个新的素 ...
1.不是“最大的素数”，是“更大的素数”；
2.不是“把已知的素数相乘”，而是“把已知的所有素数相乘”。
马上改。谢谢！
- 回复 zhouzp
- A必须是素数，否则欧几里得的那个素数是无限多的证明就错了。
gbdashen: 已知所有素数相乘加一，恩，把这个数叫做A吧，A不见得就是素数啊！可能有比现在已知素数更大的素数，能够被A整除。 ...
- 回复 gbdashen
- 举个例子：假设我们只知道前六个素数，即2,3,5,7,11,13。这六个数相乘再加1，是30031。30031=59*509
zhouzp: A必须是素数，否则欧几里得的那个素数是无限多的证明就错了。
- 回复 gbdashen
- 欧基里德的证明没有问题。问题是，证明过程中，首先假设素数数量有限，也就是说，存在一个最大素数，比它大的数都是合数。所以，在最大素数与A之间，不会有其它素数了。而在您所说的情况下，已知最大素数与A之间，还是存在素数的。在欧基里德的证明中，A不是所有素数的倍数，而在您所说的情况下，A仅仅不是已知素数的整数倍，但还有可能是大于已知最大素数但小于A的其它素数的倍数，这是问题所在。
zhouzp:
。看来那个证明确实有问题了。