|
d**********1
发帖数: 569 | 2 自然数是无穷多的，1到10是自然数的一个子集，但是1到10不是无限的。
素数的证明很简练。
假设素数是有限的，那么所有的素数的乘积+1一定是一个比所有素数还大的一个素数，
因为他显然不能被所有的素数整除（都余1），这就与前提矛盾了。所以素数是无限的。 |
|
m********3
发帖数: 2125 | 3 刚刚去看了欧几里德关于素数无穷多的证明，觉得真的是简洁，巧妙。
反证法：
假设只有n个素数，a1,a2,a3,...an
那么a1*a2*a3*...*an+1这个数被所有的素数除都除不尽，还余1，这个数也只能是素数
，所以矛盾了。
当然文科生会说根本不用证明就是对的。 |
|
x***s
发帖数: 851 | 4 是的。我昨天还在重温那本从一到无穷大的科普书，留意到这个素数是无穷的证明。
的。 |
|
w******3
发帖数: 882 | 5 你真的理解了这个证法吗？
这个证法是说明无论如何你总能找到一个比已知素数an大的素数，这对证明无穷性已经
够了。 |
|
c**n
发帖数: 5275 | 6
",
Kummer
第二个证法严格遵循了反证法的流程。
假设只有N个质数 =》这N个质数相乘-1是合数=》这个“合数”不以任何已知质数为因
子=》矛盾
人家可没有说这个矛盾必然导致（这N个质数相乘-1）是质数。
你的推导：
假设只有N个质数 =》这N个质数相乘+1 无法被已知质数整除=》这个数是质数，质数有
无穷多。
看出区别了么？你的第二个箭头并不成立，因为无法被已知质数整除可以有两个结果，
有别的未知质数可以整除OR这个数是质数，OK？ |
|
c**n
发帖数: 5275 | 7
{
哈哈哈。要证明你定义的素数集合不是完全的，难道必须有“这些素数连乘+1是质数”
么？如果能够推出有别的质数分解这个数，不是也证明了这一点么？所以我说这个证明
是不完备的。
这么说吧，你都推出假设错误了，你这个新定义的“质数”还合理吗？你说他是质数本
身也就是矛盾的吧？
还有，需要证明的是“有无穷多个质数”，而不是“已知质数连乘+1是质数”。我看自
以为数学好的另有其人吧 |
|
c****n
发帖数: 1646 | 8 文科生，你的31楼是这样说的
刚刚去看了欧几里德关于素数无穷多的证明，觉得真的是简洁，巧妙。
反证法：
假设只有n个素数，a1,a2,a3,...an
那么a1*a2*a3*...*an+1这个数被所有的素数除都除不尽，还余1，这个数也只能是素数
，所以矛盾了。
欧几里德自己是这么说的：
First, let it be prime. blablabla........
Next, let EF not be prime. blabalbla.................
我说31楼的证明不完备，因为至少在欧本人和我们这些跟随的小喽罗们看来，next也是
值得论证一下，first不是must be
屌炸天的阁下是这么说的
人家直接无视掉了这种情形, 你还说人家的证明 "不完备", 这让人说什么好? |
|
g*********g
发帖数: 1139 | 9 没啥好吵的了，你们几个的证明都正确。
都可以推出质数是无穷多的。
反证法就是精妙在这里。 不必要只有一种证明方法。 |
|
l*3
发帖数: 2279 | 10 自己翻遍全贴看看, 我什么时候说过你的证明不对?
我一直说的都是 "你指出31楼的证明不完备" 这一点是不对的, 人家证明没问题.
for the record, 你是在51楼说 "证明是不完备的", 根据上下文, 以及后来的多层回
复, 我认为你是指31楼的证明.
至于你自己列出的证明, 是对的, 如果你认为我说过你的证明 (这里 "证明" 是指对 "
素数有无穷多个" 这一命题的证明) 不对, 麻烦找出具体楼层.
另外, 单就你这一层回复来说的话, N=（a3*a5+7)*(a250-1)目测可能是个合数, 因为
你已经写成两个因子相乘了, 当然我不排斥a250=2的情况, 这样N可能是个质数. 我不
排除你随手打了一个有问题的表达式, 然后那两个新素数是那两个也没说清楚. 当然,
这个随手打的东西具体有没有道理, 和咱们讨论的东西关系不大, 就不多说了.
另外, 你貌似是真心搞不懂什么叫 "假设", 你说 "根据我的假设 "已知的素数表是全
的"，那N也不应该存在。" 这句话当然没有问题啊, 事实上N存在, 所以这假设错了.
我实在不明白你说这句话有什么意义. |
|
l*3
发帖数: 2279 | 11 假设素数只有有限个, 记为 p_1,p_2,...,p_k
考察 N = p_1*p_2*...*p_k + 1
可知: 对于任意i = 1,2,3,...,k, p_i 不能整除 N
由素数的定义:
a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
可知: N是素数
这与素数只有p_1,p_2,...,p_k矛盾.
故假设不成立.
所以素数有无穷多个. |
|
j****q
发帖数: 204 | 12 我想问。。。他的推理为什么没问题？无论他的哪一个假设，构造出来的N都不可能是
合数。
假设除了1，a1, a2,...ak外都是合数，N=1+ai连乘无法被任何小于N的质数整除，于是
N是质数，和假设矛盾于是假设不成立。
假设除了1，a1,a2...ak之外都是合数，那么任何不是这几个数的自然数都是合数。。
。这跟N实际是不是合数有关系么？假前提一定是真命题，这和结论真假有关系么？
另外，反证法真的能证明？？你的假设是a1,a2,...ak是素数的全集A，那么1+ai连乘必
然也是素数，那么假设不成立，a1,a2,...ak不是素数的全集。A不是素数的全集就等于
素数无穷多？
本人非数学专业理科生。
另外实在无法忍受为什么假设了只有那么多质数还要去讨论如果存在别的质数会怎么样
。。。。
在假设只有2和3是质数的前提下，25也是质数。5是不是质数都不影响这个逻辑的完整
性，我们要证明的都是不止2和3这两个质数，25能分解成5X5不说明任何问题，就像36
能分解成6X6一样，最终影响证明的是5不能被2和3分解，而这个和25不能被2和3分解是
等价的，即是存在不等于2和3的其他质数。分情况讨... 阅读全帖 |
|
l*3
发帖数: 2279 | 13 哦, 你没看清楚证明方式.
首先是假设素数只有有限个,
既然有有限个, 你就可以列出来: a1,a2,...,ak
最后根据逻辑推导, 又找到了一个N, 也是素数, 并且不是a1,a2,...,ak中的任何一个,
所以假设不成立.
假设不成立不只是说 "素数不止有a1,a2,...,ak", 而是说 "素数有无穷个" |
|
d**********x
发帖数: 4083 | 14 最后点你一句：
任何合数最终可以分解为质数的乘积，这个证明和假设是无关的。
N如果只能分解成合数的乘积，那意味着N可以无限分解下去，等同于N有无限多个因子
，于是N为无穷。这显然是错误的。 |
|
A***e
发帖数: 130 | 15 好，那你同意根据lz的质数定义，他的证明完整，没有问题，是吧？
如果是，那我们说等价性的问题。我们可不可以在lz的证明之前，先“证明”lz的定义
和标准定义等价呢？这个证明很简单（比如用递归），并且同质数有穷无穷无关。你觉
得是不是？ |
|
l*3
发帖数: 2279 | 16 真怀疑你是否看过证明
一楼原文如下:
----------
假设素数只有有限个, 记为 p_1,p_2,...,p_k
考察 N = p_1*p_2*...*p_k + 1
可知: 对于任意i = 1,2,3,...,k, p_i 不能整除 N
由素数的定义:
a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
可知: N是素数
这与素数只有p_1,p_2,...,p_k矛盾.
故假设不成立.
所以素数有无穷多个.
---------
其中是不是说明了, 在这个前提假设下, N就是素数?
只有这么几行, 看起来也不麻烦. 你居然都会认为我没证明 "在前提假设下, N是素数"
. |
|
x*****p
发帖数: 1707 | 17 而且，上面证明的最后一步，依赖于算术基本定理。
The Fundamental Theorem of Arithmetic: Any integer greater than 1 is either
a prime number, or can be written as a unique product of prime numbers (
ignoring the order).
而算术基本定理的证明，又依赖于欧拉引理或者称为欧拉第一定理
Euclid's lemma: Let p be a prime number, and assume p divides the product of
two integers a and b. (In symbols this is written p|ab. Its negation, p
does not divide ab is written p∤ab.)
Then p|a or p|b (or both).
以上一系列的证明，并不依赖于“素数有无穷多个”这个假设。
我看了半天，所有楼上的，没一个是学数学的。 |
|
m**x
发帖数: 8454 | 18 用定义还是用推论不影响证明的过程。因为要证明的是无穷性，并不是什么是素数。 |
|
x*****p
发帖数: 1707 | 19 如果用素数的推论的话，那么从素数的定义，就可以推导出有无穷多个素数，那还证什
么。 |
|
m**x
发帖数: 8454 | 20 推论是从定义出发证明出来的。你可以说素数无穷是推论。但你如果要证明此推论，那
么此推论不能用来作为证明的前提。 |
|
m**x
发帖数: 8454 | 21 证明自己定义出来的“素数”而不是公认定出来的“素数”的无穷性有任何意义么？ |
|
l*3
发帖数: 2279 | 22 另外, 求您老给来一个 "素数有无穷多个" 的 "美观" 的证明方法.
记住, 千万别用反证法哟~ 因为罗素悖论告诉你, 反证法都是错的. |
|
m**x
发帖数: 8454 | 23 这是你定义的素数，不是公认定义的素数。和公认定义的素数不等价。但也可以用相同
方法证明其无穷性。有问题么？ |
|
c**n
发帖数: 5275 | 24 我再叨一段吧。这是lz的证明：
“假设素数只有有限个, 记为 p_1,p_2,...,p_k
考察 N = p_1*p_2*...*p_k + 1
可知: 对于任意i = 1,2,3,...,k, p_i 不能整除 N
由素数的定义:
a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
可知: N是素数
这与素数只有p_1,p_2,...,p_k矛盾.
故假设不成立.
所以素数有无穷多个. ”
好，我们现在发现，用这个方法，找出来许多“伪素数”，30031算一个。lz你现在有
两个选择：
1. 证明这种“伪素数”是有限的；
2. 这种红“伪素数”是无限的。
请证明1或者2。如果你能证明1，好，补到原证明上去。如果你无法证明，那好，请继
续证明素数有无限多个。 |
|
g***e
发帖数: 584 | 25 你的结果不是证明了素数是无穷的吗？你得到的59不是素数吗？得到的结果不是证明素
数是无限的吗？ |
|
j****n
发帖数: 7636 | 26 这个楼实在太欢乐乐。这个不是无穷多素数的经典证明吗？第一个想到的人还是挺厉害
的。 |
|
d*****u
发帖数: 17243 | 27 我不是这个意思
他要是能证明“不能被比其小的质数整除的数有无穷多个”
我一点意见都没有
问题不在这 |
|
l*3
发帖数: 2279 | 28 转171楼如下:
这个推导不知道你能看懂不:
--------
若a不是自然数, 则a不是素数.
若a是自然数, 那么:
1. a≤1 <=> a不是素数
2. a>1,
那么:
a不是素数 <=> a是合数 <=> a有小于a的素因子
即:
a是素数 <=> a没有小于a的素因子 <=> a不被任何小于a的素数整除
综上:
a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
---------
对的还是错的?
哪一步用到了 "质数必须有无穷个"? |
|
d*****u
发帖数: 17243 | 29 我可没说你用了“素数有无穷多”
但是你默认用了“N=p1*p2*...*pn+1”的质因数必然小于等于p_n
然后推出N是质数
你没看出问题吗？ |
|
l*3
发帖数: 2279 | 30 那请问他的证明规定了素数一定要是无穷个吗?
你的逻辑呢?
你的意思是 "证明中不要求素数是有限个, 那么一旦素数是有限个, 证明就错了" 吗?
神逻辑. |
|
t*******r
发帖数: 22634 | 31 其实你如果用 (if exist k, then for k+1 ...) 的正规数学写法格式，就容易
看出来循环论证在哪里了。
你要么先假设了 k 开始于无穷个素数 -- 循环论证。
如果是假设 k 从 1 个素数开始，那就断在 2*3*5*7*11*13+1=30031=59*509 了 |
|
|
l*3
发帖数: 2279 | 33 你以后回答问题可以先清楚直白一些.
我就当你的回答是 "不对", 可以吧?
继续往下:
那么你的意思就是:
"a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除" 成立的前提, 是 "
素数必须有无穷个".
是这个意思吗? |
|
d*****u
发帖数: 17243 | 34 我的意思是
要使等价定义成立
你必须保证比a小的所有数都考虑到
而不仅仅是考虑到p_n以下的数
因为这个是等价定义成立的前提
（这里面可能已经有无穷多个数了，不过这个没关系） |
|
t*******d
发帖数: 12895 | 35 发信人: nikeman (已经颓了的北京超酷男胖子，简称酷胖), 信区: WaterWorld
标 题: Re: 关于使用反证法证明 "素数有无穷多个"
发信站: BBS 未名空间站 (Fri May 24 00:36:13 2013, 美东)
他不知道质因数和因数的区别。呵呵
【 在 thinkhard (think hard) 的大作中提到: 】
: LZ的质因数已经包括了所有质数,你还在上界上界的, 太弱了 |
|
d*****u
发帖数: 17243 | 36 我给你认真写一下吧
你自己可能不知道，但是你已经把A偷换成了
a是素数<=>a是大于1的自然数，且a不被任何p_n以下的素数整除
这个结论本身就是错的
跟素数是不是有限个其实是无关的
然后你用它来反证出素数有无穷多个 |
|
s******k
发帖数: 168 | 37 把楼主的证明改写了一下，大家看看对不对。我觉得和楼主的证明是等价的。
素数定义：
* 最小的素数是2
* 一个数是素数，如果这个数是不被任何小于它的素数整除的自然数
素数的性质一：
* 素数只有有限个
假设性质一为真, 将所以素数记为 p_1,p_2,...,p_k
考察 N = p_1*p_2*...*p_k + 1
可知: 对于任意i = 1,2,3,...,k, p_i 不能整除 N
可知: 如果性质一为真,则N是满足前面素数定义的素数
这与素数只有p_1,p_2,...,p_k矛盾.
故性质一为假，素数有无穷多个，前面N是素数的推论未必成立。 |
|
l*3
发帖数: 2279 | 38 改写是正确的.
"素数有无穷多个" 这个命题的证明方式太多了.
我本意只是想强调: 1楼的证明没有错误. |
|
l*3
发帖数: 2279 | 39 谢谢你这么多回复.
我的目的不是让他们认为 "素数有无穷多个" 这个命题正确, 这个命题本身确实是有很
多种证明方法.
我的目的是想通过自己的说理, 让他们认为1楼的证明是正确的.
看上去这很困难. |
|
l*3
发帖数: 2279 | 40 你举例子的目的是什么?
我只是让你指出773楼的证明, 哪一步用到了和假设有关的性质 (即素数有无穷个/素数
有有限个),
我是让你找出哪一步 用 到 了 和假设有关的性质.
你举例子是不是答非所问?
你写的有些东西我逻辑上不能理解, 请你先回答我这个问题:
问题1: 773楼的证明中, 哪一步用到了和假设有关的性质?
-------
如果你觉得你780楼回答的就是如上这个 "问题1" 的话, 那麻烦回复明示. |
|
b******r
发帖数: 1137 | 41 这么样吧，你能不能证一下两个定义等价。我们都知道对于我们的自然数集它们是等价
的，你证一下，必须保证不牵涉素数是无穷的这个结论。很多人的论点就是这不是一个
trivial的东西。这个要求合理吧？ |
|
n******h
发帖数: 97 | 42 看着坑大，忍不住跳一个。
就像前面一个人说的，光是 "a是素数 <=> a是大于1的自然数, 且a不被任何不等于a的
素数整除" 是正确的命题不够把。你需要说明这个正确性并不建立在素数无穷的基础上
。虽然你后来证明了，但是你需要把这样的证明加到1楼里面才能完备。加进去之后看
上去并不比欧几里得的要简洁了。 |
|
d*****n
发帖数: 3033 | 43 发信人: l63 (l63), 信区: WaterWorld
标 题: 关于使用反证法证明 "素数有无穷多个"
发信站: BBS 未名空间站 (Thu May 23 00:34:22 2013, 美东)
假设素数只有有限个, 记为 p_1,p_2,...,p_k
考察 N = p_1*p_2*...*p_k + 1
。。。。。
可知: N是素数
--------------------------------------------------
k=1的时候，就一个质数2，
k=2的时候，就两个质数2和3，
k=3的时候，就三个质数2，3，5，
k=4的时候，就4个质数2 3 5 7
k=5的时候，就5个质数2 3 5 7 11
k=6的时候，就6个质数2 3 5 7 11 13
所有的质数都在这儿了，一个没有漏。
p1=2
p2=3
p3=5
p4=7
p5=11
p6=13
N=p1*p2*p3*p4*p5*p6+1=30031=59*509 不是质数。 |
|
b******r
发帖数: 1137 | 44 素数不那么好找，所以有一个我们人类已知的最大的素数，当然天天可能都在变大。不
失一般性，假设我们脑容量不比蚂蚁大多少，现在我们已知最大素数是13，总共6个：2
,3,5,7,11,13。有一天来了一只老鼠和蚂蚁对话
蚂蚁：素数只有六个
老鼠：不对，素数无穷多
蚂蚁：你能证明吗？
老鼠：如果如你所说素数只有六个，那看一下这个数2*3*5*7*11*13+1=30031
蚂蚁：怎么样？
老鼠：30031不能被2,3,5,7,11或是13整除
蚂蚁：然后呢？
老鼠：所以根据我们的假设（只有6个素数），30031是一个素数，这样我们就发现还有
一个不是2,3,5,7,11,13的素数？
蚂蚁：？？？什么叫根据我们的假设，30031是一个素数？30031是不是素数跟我们的假
设有关系吗？我会除法，让我慢慢算。。。30031=59*509
鼹鼠：你不懂反证法，这样就已经证明完毕了
蚂蚁：？？？
老鼠：我的测试素数的方法是啮齿类公认的，一共六个素数，不能被任意一个整除就是
素数
蚂蚁：你怎么知道13到30031之间没有素数了？
老鼠：因为我们假设只有六个素数？
蚂蚁：？？？那为什么多出来一个3003... 阅读全帖 |
|
b*********z
发帖数: 26 | 45 哇，memorial day长假出去玩回来想起这个帖子，楼又高了许多，代码都出来了，我等
码工真欢乐！
以前上mitbbs，我只潜水。不过，我承认这次我也灌了许多水，试图引起LZ思考哪里错
了。
好吧，楼很高了，我就总结一下我的发言吧。
首先说，素数的定义是大于1除了自己和1不能被其他自然数整除的自然数。
我把一楼的证明拷贝过来，并在下面一步一步举个简单的例子说明哪步错了。
－－－－－－－－－－
假设素数只有有限个, 记为 p_1,p_2,...,p_k
（假设素数只有有限个，为2，3，5，7，11，13.这些都是符合定义的素数，而且在13
以下没有遗漏，p_k就是13）
考察 N = p_1*p_2*...*p_k + 1
（考察N＝2*3*5*7*11*13＋1=30031）
可知: 对于任意i = 1,2,3,...,k, p_i 不能整除 N
（2，3，5，7，11，13都不能整除N。这句话是对的）
由素数的定义:
a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
可知: N是素数
（这是错的。30031=59*509，N不是素数）
这与素数只有p_1,p_... 阅读全帖 |
|
l*3
发帖数: 2279 | 46 你的意思是不是:
我要证明 "a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除" 这个命题
的话, 必须要用到 "素数有无穷多个"?
回答 "是", 或者 "不是". |
|
d*****u
发帖数: 17243 | 47 反证，就是要在假设的条件下利用公理等推出与假设相反的结论
你先回答我一个问题
如果我们“不知道素数是不是有无穷多个”
能不能说 a是素数<=>a没有小于a的质因数
回答能或者不能 |
|
d*****u
发帖数: 17243 | 48 好
你说即使不知道素数是不是有无穷多，也可以认为他们等价
那么假设素数是有限的，最大是p_n
比p_n大的，且不能被其他自然数整除的数，
按照素数的定义（等价符号左边部分），是素数
但是按照等价符号右边部分的表述，是合数
所以就不等价了，是不是
只要你回答是不是等价，不要扯其他的 |
|
l*3
发帖数: 2279 | 49 你再表述一遍, 你是说明 "不需要反证法, 也可以证明 素数有无穷个 " 的?
谢谢. |
|
l*3
发帖数: 2279 | 50 错, 你那不是更准确的说法, 你那是自我意淫出来的说法. 我不认同你意淫出来的说法
.
我就问你, 你是不是认为: 我在没有素数无穷多的前提下, 证明不了 "a是素数 <=> a
是大于1的自然数, 且a不被任何小于a的素数整除" 这个命题?
请回答 是 or 不是.
请简单回答, 不要做其他补充. |
|
