f*******i
发帖数: 1049 | 1 1. 假设p1=2,p2=3,...,pn 是全部的素数...
2. 令 N=p1*p2*...*pn+1, 显然 N比 p1,p2,...,pn都大,因此不再p1,p2,..,pn,中, 所
以根据1, N是一个合数.
3. N是合数,那么必然能够被一个素数整除, 根据1, 所有的素数是p1,..., pn, 所以必
然有其中之一, 比如pj, 能整除N, 特别的, N 除以pj余数为0
4. N= pj*(p2*...*pn 括号内排除pj)+1=pj*something+1, 因此, N除以pj余数为1
5. 3 和 4 矛盾,N不能同时除以pj余0,而且余1.
现在有几种推理方法
6(I), 3和4矛盾, 矛盾的根源在于 假设1 是完全错误的, 于是 证毕,素数无穷 Q.E.D
或者走下列路线(l63路线)
6(II), 3和4矛盾的一个最近的根源来自于第3部的N是合数, 因此 N是合数这个结论错
误, 于是 N是素数,
7 但是6(II) 跟 1 相冲突...
8 于是1的假设错误 , 素数是无穷的... | c****n
发帖数: 1646 | 2 这个才是原版，你把６３坚持了好几天的N一定只能是素数换成了N是合数，小心他跟你
反脸。
发信人: 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
可知: 对于任意i = 1,2,3,...,k, p_i 不能整除 N
由素数的定义:
a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
可知: N是素数
这与素数只有p_1,p_2,...,p_k矛盾.
故假设不成立.
所以素数有无穷多个.
D
【在 f*******i 的大作中提到】
: 1. 假设p1=2,p2=3,...,pn 是全部的素数...
: 2. 令 N=p1*p2*...*pn+1, 显然 N比 p1,p2,...,pn都大,因此不再p1,p2,..,pn,中, 所
: 以根据1, N是一个合数.
: 3. N是合数,那么必然能够被一个素数整除, 根据1, 所有的素数是p1,..., pn, 所以必
: 然有其中之一, 比如pj, 能整除N, 特别的, N 除以pj余数为0
: 4. N= pj*(p2*...*pn 括号内排除pj)+1=pj*something+1, 因此, N除以pj余数为1
: 5. 3 和 4 矛盾,N不能同时除以pj余0,而且余1.
: 现在有几种推理方法
: 6(I), 3和4矛盾, 矛盾的根源在于 假设1 是完全错误的, 于是 证毕,素数无穷 Q.E.D
: 或者走下列路线(l63路线)
| f*******i
发帖数: 1049 | 3 l63路线中, 从p2,p3,.. pn 是所有路线推出N是素数这个 推理逻辑是正确的
有人说
2*3*5*7*11*13+1=30031是合数
正确
单数 N是素数的推理前提是(p2,p3,..,pn是所有素数),
现在 2,3,..., 13 并不是所有的素数! | d*****n
发帖数: 3033 | 4 你这哪是163的版本啊。。。
D
【在 f*******i 的大作中提到】
: 1. 假设p1=2,p2=3,...,pn 是全部的素数...
: 2. 令 N=p1*p2*...*pn+1, 显然 N比 p1,p2,...,pn都大,因此不再p1,p2,..,pn,中, 所
: 以根据1, N是一个合数.
: 3. N是合数,那么必然能够被一个素数整除, 根据1, 所有的素数是p1,..., pn, 所以必
: 然有其中之一, 比如pj, 能整除N, 特别的, N 除以pj余数为0
: 4. N= pj*(p2*...*pn 括号内排除pj)+1=pj*something+1, 因此, N除以pj余数为1
: 5. 3 和 4 矛盾,N不能同时除以pj余0,而且余1.
: 现在有几种推理方法
: 6(I), 3和4矛盾, 矛盾的根源在于 假设1 是完全错误的, 于是 证毕,素数无穷 Q.E.D
: 或者走下列路线(l63路线)
| d*****n
发帖数: 3033 | 5 正确的头。
反例都给你看了，还正确。
看来你被民科洗脑洗的不清。
【在 f*******i 的大作中提到】
: l63路线中, 从p2,p3,.. pn 是所有路线推出N是素数这个 推理逻辑是正确的
: 有人说
: 2*3*5*7*11*13+1=30031是合数
: 正确
: 单数 N是素数的推理前提是(p2,p3,..,pn是所有素数),
: 现在 2,3,..., 13 并不是所有的素数!
| f*******i
发帖数: 1049 | 6 我在6(II)中"又"证明了N是素数,lol
【在 d*****n 的大作中提到】
: 你这哪是163的版本啊。。。
:
: D
| f*******i
发帖数: 1049 | 7 这个例子说明由错误的假设可以合理,逻辑地推出很多自相矛盾的结论,大家不要纠结了 | c****n
发帖数: 1646 | 8 l63路线中, 从p2,p3,.. pn 是所有路线推出N是合数这个 推理逻辑也是正确的
【在 f*******i 的大作中提到】
: l63路线中, 从p2,p3,.. pn 是所有路线推出N是素数这个 推理逻辑是正确的
: 有人说
: 2*3*5*7*11*13+1=30031是合数
: 正确
: 单数 N是素数的推理前提是(p2,p3,..,pn是所有素数),
: 现在 2,3,..., 13 并不是所有的素数!
| f*******i
发帖数: 1049 | 9 是的
我们能推出N既是素数又是合数..有问题吗,
我们还能推出N能被某p1,p2,...pn,之外的某素数整除,尽管p1,p2,...,pn是所有的素数
【在 c****n 的大作中提到】
: l63路线中, 从p2,p3,.. pn 是所有路线推出N是合数这个 推理逻辑也是正确的
| Z*****e
发帖数: 369 | 10 真好奇你是学什么的，这点逻辑也弄不清楚。
【在 c****n 的大作中提到】
: l63路线中, 从p2,p3,.. pn 是所有路线推出N是合数这个 推理逻辑也是正确的
| | | c****n
发帖数: 1646 | 11 没问题，所以原假设错误。
我一直说６３的结论不完备就是这点。
他可是坚持他的推论只能得出N是素数的结论。
【在 f*******i 的大作中提到】
: 是的
: 我们能推出N既是素数又是合数..有问题吗,
: 我们还能推出N能被某p1,p2,...pn,之外的某素数整除,尽管p1,p2,...,pn是所有的素数
| c****n
发帖数: 1646 | 12 我学什么不重要，如何通过同样原假设和推理能得出N是合数的过程也贴了好几次了。
【在 Z*****e 的大作中提到】
: 真好奇你是学什么的，这点逻辑也弄不清楚。
| f*******i
发帖数: 1049 | 13 如果他不承认那个错误的假设能推出N是合数,那他自然错了
不过他找到了足够的矛盾,can get the job done, 后面的讨论也懒得一一去看了
【在 c****n 的大作中提到】
: 没问题，所以原假设错误。
: 我一直说６３的结论不完备就是这点。
: 他可是坚持他的推论只能得出N是素数的结论。
| Z*****e
发帖数: 369 | 14 你脑袋真够糊的，正是因为假设是错的（目的就是证明假使是错的）所以可以推理出自
相矛盾的结论(比如你说的推理出N必然是质数而同时又必然是合数,矛盾，所以假设错
误，证明结束）（这正是反证法需要寻找的）。
【在 c****n 的大作中提到】
: 没问题，所以原假设错误。
: 我一直说６３的结论不完备就是这点。
: 他可是坚持他的推论只能得出N是素数的结论。
| f*******i
发帖数: 1049 | 15 结论就是,既能推出n是素数,也能推出n是合数.
不承认任何一点的都打50巴掌吧
~ | c****n
发帖数: 1646 | 16 1. 63暂时还不承认，他认为得出合数的结论是因为用了合数的定义，而他的推理只用
了素数的定义，N只能是素数。
２。 如果知道N也能是合数，却仍坚持N是素数，不能否定原假设。因为素数有限的假
设推理无法证明所以N有一个一定能是素数，如果不讨论合数，并没有引入矛盾。
【在 f*******i 的大作中提到】
: 如果他不承认那个错误的假设能推出N是合数,那他自然错了
: 不过他找到了足够的矛盾,can get the job done, 后面的讨论也懒得一一去看了
| c****n
发帖数: 1646 | 17 结论N是素数并不能否定原假设错误。
１。如果结论是N一定只能是素数，那和原假设矛盾，没问题。
２。这个证明的假设条件得不出N一定只能是素数，说N是素数就能否定原假设就不对。
因为你没有证明，你构造的N如果是合数，它是否和你的原假设素数有限矛盾。 如果合
数和原假设不矛盾，那N是素数的矛盾就不存在。因为这个证明无法证明N是素数一定存
在,那怕只有一个就好。，如果一个素数也没有，自然没有矛盾。这就是为什么我们看
到的所有关于素数无限的反证法都同时讨论了两种可能。
６３的结论素数无限是对的，这个结果对今天的人来说是一个常识，遗憾的是过程有问
题。
【在 Z*****e 的大作中提到】
: 你脑袋真够糊的，正是因为假设是错的（目的就是证明假使是错的）所以可以推理出自
: 相矛盾的结论(比如你说的推理出N必然是质数而同时又必然是合数,矛盾，所以假设错
: 误，证明结束）（这正是反证法需要寻找的）。
| d******k
发帖数: 4295 | 18 如果假设素数有限，可以推导出N是素数，也可以推导出N是合数。
只要推出的结论和假设矛盾完成反证即可，不需要把所有的可能都给出。
【在 c****n 的大作中提到】
: 1. 63暂时还不承认，他认为得出合数的结论是因为用了合数的定义，而他的推理只用
: 了素数的定义，N只能是素数。
: ２。 如果知道N也能是合数，却仍坚持N是素数，不能否定原假设。因为素数有限的假
: 设推理无法证明所以N有一个一定能是素数，如果不讨论合数，并没有引入矛盾。
| f*******i
发帖数: 1049 | 19 +1
如果较真,可能可以推出不同层次的很多矛盾
但只需要找到一个就(Q.E.D)
【在 d******k 的大作中提到】
: 如果假设素数有限，可以推导出N是素数，也可以推导出N是合数。
: 只要推出的结论和假设矛盾完成反证即可，不需要把所有的可能都给出。
| Z*****e
发帖数: 369 | 20 你还是没理解。首先根据假设可以推断出N必然是质数，而且这个质数大于假使里的所
有质数中任何一个（也就是说假使的所有质数集合是错的），这就已经足够证明假设是
错的。不但如此，我们还可以推出更多的矛盾，比如可以推出N必然是合数，一个数不
可能同时是质数又是合数，所以假设错误。
【在 c****n 的大作中提到】
: 结论N是素数并不能否定原假设错误。
: １。如果结论是N一定只能是素数，那和原假设矛盾，没问题。
: ２。这个证明的假设条件得不出N一定只能是素数，说N是素数就能否定原假设就不对。
: 因为你没有证明，你构造的N如果是合数，它是否和你的原假设素数有限矛盾。 如果合
: 数和原假设不矛盾，那N是素数的矛盾就不存在。因为这个证明无法证明N是素数一定存
: 在,那怕只有一个就好。，如果一个素数也没有，自然没有矛盾。这就是为什么我们看
: 到的所有关于素数无限的反证法都同时讨论了两种可能。
: ６３的结论素数无限是对的，这个结果对今天的人来说是一个常识，遗憾的是过程有问
: 题。
| | | c****n
发帖数: 1646 | 21 问题是你不能推出N只能是素数或一定是素数，不能否认也不能否认N至少能有一个素数
，可同理，也不能否认N全是合数。
素数带来的矛盾这个证明并不能保证一定存在，所以一个完整的证明需要两种可能都要
提到。
【在 d******k 的大作中提到】
: 如果假设素数有限，可以推导出N是素数，也可以推导出N是合数。
: 只要推出的结论和假设矛盾完成反证即可，不需要把所有的可能都给出。
| d*****u
发帖数: 17243 | 22 根据假设不能推断N是质数
推断必须从“定义”出发，
从其他推论出发需要证明此推论在假设条件下也成立
【在 Z*****e 的大作中提到】
: 你还是没理解。首先根据假设可以推断出N必然是质数，而且这个质数大于假使里的所
: 有质数中任何一个（也就是说假使的所有质数集合是错的），这就已经足够证明假设是
: 错的。不但如此，我们还可以推出更多的矛盾，比如可以推出N必然是合数，一个数不
: 可能同时是质数又是合数，所以假设错误。
| d******k
发帖数: 4295 | 23 恩，如果考试的时候写证明过程把那些多余的都写上显得自己考虑完备。
虽然不会倒扣分，但老师的印象分肯定大减。
【在 f*******i 的大作中提到】
: +1
: 如果较真,可能可以推出不同层次的很多矛盾
: 但只需要找到一个就(Q.E.D)
| d******k
发帖数: 4295 | 24 如果考试的时候你把这些分析都写上，不会倒扣分。但老师对你的印象分绝对大减。
【在 c****n 的大作中提到】
: 问题是你不能推出N只能是素数或一定是素数，不能否认也不能否认N至少能有一个素数
: ，可同理，也不能否认N全是合数。
: 素数带来的矛盾这个证明并不能保证一定存在，所以一个完整的证明需要两种可能都要
: 提到。
| f*******i
发帖数: 1049 | 25 错了,
用反证法 证明A=>B,
我们可以假设 A真,B是假,然后利用所有的已知的公理和定理进行推论
只要在逻辑推理的前提下能找到任何一对矛盾,就达到了证明的目的
【在 d*****u 的大作中提到】
: 根据假设不能推断N是质数
: 推断必须从“定义”出发，
: 从其他推论出发需要证明此推论在假设条件下也成立
| Z*****e
发帖数: 369 | 26 你要清清脑子了。从假使我们可以推出N必然是质数，同样可以推出N必然是合数。这结
论是矛盾的（为什么矛盾？因为假使是错误的）。一个错误的假使可以推出很多矛盾。
【在 c****n 的大作中提到】
: 问题是你不能推出N只能是素数或一定是素数，不能否认也不能否认N至少能有一个素数
: ，可同理，也不能否认N全是合数。
: 素数带来的矛盾这个证明并不能保证一定存在，所以一个完整的证明需要两种可能都要
: 提到。
| d*****u
发帖数: 17243 | 27 那你实际上是在说罗圈话：
先假设某某错误情况（实际就否认了推论了，虽然作者没察觉）
然后又说坚持推论可以推出谬误
所以反证成功
这不是循环吗？
因为我否认了推论，所以推论推出错误结果，证毕。不搞笑？
【在 f*******i 的大作中提到】
: 错了,
: 用反证法 证明A=>B,
: 我们可以假设 A真,B是假,然后利用所有的已知的公理和定理进行推论
: 只要在逻辑推理的前提下能找到任何一对矛盾,就达到了证明的目的
| f*******i
发帖数: 1049 | 28 这段说明了你不懂反证法
【在 d*****u 的大作中提到】
: 那你实际上是在说罗圈话：
: 先假设某某错误情况（实际就否认了推论了，虽然作者没察觉）
: 然后又说坚持推论可以推出谬误
: 所以反证成功
: 这不是循环吗？
: 因为我否认了推论，所以推论推出错误结果，证毕。不搞笑？
| d*****u
发帖数: 17243 | 29 别说这些废话，你仔细想想
【在 f*******i 的大作中提到】
: 这段说明了你不懂反证法
| Z*****e
发帖数: 369 | 30 你确实没弄懂反证法是什么意思。
【在 d*****u 的大作中提到】
: 别说这些废话，你仔细想想
| | | b******r
发帖数: 1137 | 31 你下意识的用了质数的等价定义。有人指出了这个等价定义不是显而易见的，其证明复
杂度远超过只用基本素数定义来证明素数无穷多的原本欧几里德证明。
【在 Z*****e 的大作中提到】
: 你要清清脑子了。从假使我们可以推出N必然是质数，同样可以推出N必然是合数。这结
: 论是矛盾的（为什么矛盾？因为假使是错误的）。一个错误的假使可以推出很多矛盾。
| f*******i
发帖数: 1049 | 32 "因为我否认了推论，所以推论推出错误结果，证毕"
我否认了推论,也就是我假设推论是假命题. 然后我从此推出矛盾的结果, 问题从哪儿
来?
说名 "推论是假命题"这个命题是假命题, 因此 推论是真的
ok?
【在 d*****u 的大作中提到】
: 别说这些废话，你仔细想想
| d*****u
发帖数: 17243 | 33 你觉得可能吗？
中国高中就教反证法
【在 Z*****e 的大作中提到】
: 你确实没弄懂反证法是什么意思。
| d*****u
发帖数: 17243 | 34 推论跟原命题都不等价了，你证半天都是白忙活
【在 f*******i 的大作中提到】
: "因为我否认了推论，所以推论推出错误结果，证毕"
: 我否认了推论,也就是我假设推论是假命题. 然后我从此推出矛盾的结果, 问题从哪儿
: 来?
: 说名 "推论是假命题"这个命题是假命题, 因此 推论是真的
: ok?
| d**********x
发帖数: 4083 | 35 广泛地教授反证法，显然是在初中。举例：
http://wenwen.soso.com/z/q199981650.htm
小学奥数里面证明就已经常用反证法了。举例：
http://xiaoxue.eol.cn/xxas_11415/20120816/t20120816_828971.shtm
而你臆想中，中国高中“就”教反证法，可能有两种原因：
1.你没上过初中
2.你上过高中，但是没在国内上，而且这个高中高端到反证法都没教过
你选一个？
【在 d*****u 的大作中提到】
: 你觉得可能吗？
: 中国高中就教反证法
| d*****u
发帖数: 17243 | 36 文字游戏？
高中就教也没否认小学和初中可能教啊
我们都上过高中，所以肯定学过，证毕
【在 d**********x 的大作中提到】
: 广泛地教授反证法，显然是在初中。举例：
: http://wenwen.soso.com/z/q199981650.htm
: 小学奥数里面证明就已经常用反证法了。举例：
: http://xiaoxue.eol.cn/xxas_11415/20120816/t20120816_828971.shtm
: 而你臆想中，中国高中“就”教反证法，可能有两种原因：
: 1.你没上过初中
: 2.你上过高中，但是没在国内上，而且这个高中高端到反证法都没教过
: 你选一个？
| f*******i
发帖数: 1049 | 37 虽然很浪费时间,让我们来实践一下
求证,没有最大的整数
令(p=命题 没有最大的整数)
证明, 用反证法, 假设 (!p)为真, (!p跟p当然不等价,他们相反!)
于是,存在最大整数,记为N
现在因为整数+整数还是整数(我在用已知的定理), 所以N+1为整数
又因为1是正数,所以N+1>N
于是 找到了比N更大的整数N+1, 这跟 N是最大整数矛盾.
于是知道 假设(!p为真)是错的 ,所以(!p为假), 所以(p为真)
【在 d*****u 的大作中提到】
: 推论跟原命题都不等价了，你证半天都是白忙活
| d*****u
发帖数: 17243 | 38 你这个跟lz的证明半点逻辑关系都没有
我给你举例
楼主想证明没有最大整数
用到了某等价推论：没有最大的偶数
然后说假设有最大的整数，可以证明能找到最大偶数（怎么找你可以去想）
然后说矛盾，反证成立
问题是你都假设没有最大整数了，还直接用“没有最大偶数”这个推论？
这是证明吗？
当然这个例子也不是特别贴切，但有那意思
【在 f*******i 的大作中提到】
: 虽然很浪费时间,让我们来实践一下
: 求证,没有最大的整数
: 令(p=命题 没有最大的整数)
: 证明, 用反证法, 假设 (!p)为真, (!p跟p当然不等价,他们相反!)
: 于是,存在最大整数,记为N
: 现在因为整数+整数还是整数(我在用已知的定理), 所以N+1为整数
: 又因为1是正数,所以N+1>N
: 于是 找到了比N更大的整数N+1, 这跟 N是最大整数矛盾.
: 于是知道 假设(!p为真)是错的 ,所以(!p为假), 所以(p为真)
| f*******i
发帖数: 1049 | 39 很有讽刺意义的是,如果没有"最大的偶数"已经是众所周知的事实,那么楼主这个例子没
有任何逻辑错误.
【在 d*****u 的大作中提到】
: 你这个跟lz的证明半点逻辑关系都没有
: 我给你举例
: 楼主想证明没有最大整数
: 用到了某等价推论：没有最大的偶数
: 然后说假设有最大的整数，可以证明能找到最大偶数（怎么找你可以去想）
: 然后说矛盾，反证成立
: 问题是你都假设没有最大整数了，还直接用“没有最大偶数”这个推论？
: 这是证明吗？
: 当然这个例子也不是特别贴切，但有那意思
| d*****u
发帖数: 17243 | 40 那也就不用证明了，那还忙活什么
现在不就是想证明吗
【在 f*******i 的大作中提到】
: 很有讽刺意义的是,如果没有"最大的偶数"已经是众所周知的事实,那么楼主这个例子没
: 有任何逻辑错误.
| | | Z*****e
发帖数: 369 | 41 质数定义不是除１和本身不能被其他数整除吗？
【在 b******r 的大作中提到】
: 你下意识的用了质数的等价定义。有人指出了这个等价定义不是显而易见的，其证明复
: 杂度远超过只用基本素数定义来证明素数无穷多的原本欧几里德证明。
| d*****u
发帖数: 17243 | 42 对，但是lz用的是推论“不能被其他质数整除”（不是自然数了）
这个推论成立是有条件的
在反证假设的时候，已经不存在这个条件
【在 Z*****e 的大作中提到】
: 质数定义不是除１和本身不能被其他数整除吗？
| b******r
发帖数: 1137 | 43 对，但这不是i63的表述。他说一个数如果不能被所有比他小的质数整除就是质数。大
家都知道两个命题等价，但是这个等价命题其实不简单，所以不提就用不严密。即使用
了也是在用复杂的结论倒过来证简单的东西。
【在 Z*****e 的大作中提到】
: 质数定义不是除１和本身不能被其他数整除吗？
| Z*****e
发帖数: 369 | 44 很容易可以证明那个N不能被除１或N本身的数整除啊。
【在 b******r 的大作中提到】
: 对，但这不是i63的表述。他说一个数如果不能被所有比他小的质数整除就是质数。大
: 家都知道两个命题等价，但是这个等价命题其实不简单，所以不提就用不严密。即使用
: 了也是在用复杂的结论倒过来证简单的东西。
| b******r
发帖数: 1137 | 45 只是很容易证明N不能被那些已知素数整除。那合数呢？你是不是需要定义合数？
【在 Z*****e 的大作中提到】
: 很容易可以证明那个N不能被除１或N本身的数整除啊。
| Z*****e
发帖数: 369 | 46 这太简单了啊。首先一个质数不会被比它大的数整除。然后考虑比它小的数，要么是质
数，要么是合数，如果一个数不能被比任何一个比它小的质数整除那么必然不能被比它
小的合数整除，因为合数根据定义会被至少１个比它小的质数整除，所以这质数的定义
也可以说成不能比它小的质数整除的数。
【在 b******r 的大作中提到】
: 只是很容易证明N不能被那些已知素数整除。那合数呢？你是不是需要定义合数？
| f*******i
发帖数: 1049 | 47 这些东西已经讲过好多遍了,该看不懂的还是看不懂
还是表浪费时间了~
【在 Z*****e 的大作中提到】
: 这太简单了啊。首先一个质数不会被比它大的数整除。然后考虑比它小的数，要么是质
: 数，要么是合数，如果一个数不能被比任何一个比它小的质数整除那么必然不能被比它
: 小的合数整除，因为合数根据定义会被至少１个比它小的质数整除，所以这质数的定义
: 也可以说成不能比它小的质数整除的数。
| b*********z
发帖数: 26 | 48 3是错误的。3的前提是任意大于pn的整数都能被已知素数整除，这是错误的。
假设2，3，5是已知素数，14就不满足。
除非这个逻辑被补充，否则论证是不严谨的。我认为素数分解理论在这里不适用。
附3原文
3. N是合数,那么必然能够被一个素数整除, 根据1, 所有的素数是p1,..., pn, 所以必
然有其中之一, 比如pj, 能整除N, 特别的, N 除以pj余数为0
另，反正法要和初始假设矛盾。 | b*********z
发帖数: 26 | 49 反证法是在假设前提下，一步步推出的结论和假设的前提矛盾，所以假设是错误的。没
听说过证着证着说，你瞧，结论和倒数第二步是矛盾的，原因是前提。那只能说明当中
的推理本来就有问题。 | C**********r
发帖数: 8189 | 50
同意你讲的。
让我想到小时候，有些同学貌似很聪明，喜欢跳步骤。有的老师喜欢抓班头，跳步骤的
一律扣分。
跳步骤的有两种情况，一种是真不知道，只好蒙，另一种是真知道。真知道的情况下，
表述完整写又有什么害处呢？
【在 b*********z 的大作中提到】
: 反证法是在假设前提下，一步步推出的结论和假设的前提矛盾，所以假设是错误的。没
: 听说过证着证着说，你瞧，结论和倒数第二步是矛盾的，原因是前提。那只能说明当中
: 的推理本来就有问题。
| | | f*******i
发帖数: 1049 | 51 你这个说法完全错误
你是数学系的吗
【在 b*********z 的大作中提到】
: 反证法是在假设前提下，一步步推出的结论和假设的前提矛盾，所以假设是错误的。没
: 听说过证着证着说，你瞧，结论和倒数第二步是矛盾的，原因是前提。那只能说明当中
: 的推理本来就有问题。
| f*******i
发帖数: 1049 | 52 在保证逻辑正常的情况下,推出任何一对矛盾即可
【在 b*********z 的大作中提到】
: 反证法是在假设前提下，一步步推出的结论和假设的前提矛盾，所以假设是错误的。没
: 听说过证着证着说，你瞧，结论和倒数第二步是矛盾的，原因是前提。那只能说明当中
: 的推理本来就有问题。
| f*******i
发帖数: 1049 | | g******y
发帖数: 126 | 54 这个证明貌似是对的，参见欧几里德的证明 (wikipedia)：
素数有無窮多個。現在已知最早的證明方法是歐幾里得在他的《幾何原本》中提出的，
該證明方法如下：
假設只有有限个素数p_1,p_2,p_3,..., p_n。令N=p_1times p_2times p_3 times
... times p_n。那么，N+1是素数或者不是素数。
如果N+1為素数，則N+1要大于p_1,p_2,p_3...p_n，所以它不在那些假設的素数集
合中。
如果N+1為合数，因為任何一個合数都可以分解為幾個素数的積；而N和N+1的最大
公约数是1，所以N+1不可能被p_1,p_2,p_3ldots p_n整除，所以該合数分解得到的素因
数肯定不在假設的素数集合中。
因此無論該数是素数還是合数，都意味著在假設的有限個素数之外還存在着其他素
数。
對任何有限個素数的集合來說，用上述的方法永遠可以得到有一個素数不在假設的
素数集合中的結論。
所以原先的假設不成立。也就是說，素数有無窮多個。
D
【在 f*******i 的大作中提到】
: 1. 假设p1=2,p2=3,...,pn 是全部的素数...
: 2. 令 N=p1*p2*...*pn+1, 显然 N比 p1,p2,...,pn都大,因此不再p1,p2,..,pn,中, 所
: 以根据1, N是一个合数.
: 3. N是合数,那么必然能够被一个素数整除, 根据1, 所有的素数是p1,..., pn, 所以必
: 然有其中之一, 比如pj, 能整除N, 特别的, N 除以pj余数为0
: 4. N= pj*(p2*...*pn 括号内排除pj)+1=pj*something+1, 因此, N除以pj余数为1
: 5. 3 和 4 矛盾,N不能同时除以pj余0,而且余1.
: 现在有几种推理方法
: 6(I), 3和4矛盾, 矛盾的根源在于 假设1 是完全错误的, 于是 证毕,素数无穷 Q.E.D
: 或者走下列路线(l63路线)
| d**********x
发帖数: 4083 | 55 你要看看英文版wiki吗？
中文版wiki是错的。
, 所
以必
E.
【在 g******y 的大作中提到】
: 这个证明貌似是对的，参见欧几里德的证明 (wikipedia)：
: 素数有無窮多個。現在已知最早的證明方法是歐幾里得在他的《幾何原本》中提出的，
: 該證明方法如下：
: 假設只有有限个素数p_1,p_2,p_3,..., p_n。令N=p_1times p_2times p_3 times
: ... times p_n。那么，N+1是素数或者不是素数。
: 如果N+1為素数，則N+1要大于p_1,p_2,p_3...p_n，所以它不在那些假設的素数集
: 合中。
: 如果N+1為合数，因為任何一個合数都可以分解為幾個素数的積；而N和N+1的最大
: 公约数是1，所以N+1不可能被p_1,p_2,p_3ldots p_n整除，所以該合数分解得到的素因
: 数肯定不在假設的素数集合中。
| C**********r
发帖数: 8189 | 56
牛。
【在 d**********x 的大作中提到】
: 你要看看英文版wiki吗？
: 中文版wiki是错的。
:
: , 所
: 以必
: E.
| d**********x
发帖数: 4083 | 57 当然不是说证明是错的
而是对事实的陈述有错
【在 C**********r 的大作中提到】
:
: 牛。
| m********k
发帖数: 4 | 58 XXX
D
【在 f*******i 的大作中提到】
: 1. 假设p1=2,p2=3,...,pn 是全部的素数...
: 2. 令 N=p1*p2*...*pn+1, 显然 N比 p1,p2,...,pn都大,因此不再p1,p2,..,pn,中, 所
: 以根据1, N是一个合数.
: 3. N是合数,那么必然能够被一个素数整除, 根据1, 所有的素数是p1,..., pn, 所以必
: 然有其中之一, 比如pj, 能整除N, 特别的, N 除以pj余数为0
: 4. N= pj*(p2*...*pn 括号内排除pj)+1=pj*something+1, 因此, N除以pj余数为1
: 5. 3 和 4 矛盾,N不能同时除以pj余0,而且余1.
: 现在有几种推理方法
: 6(I), 3和4矛盾, 矛盾的根源在于 假设1 是完全错误的, 于是 证毕,素数无穷 Q.E.D
: 或者走下列路线(l63路线)
| g******y
发帖数: 126 | 59 我看了一下英文版，原来欧几里德原版是证明如果给定素数集是有限个，那么必然可以
再增加一个素数。
英文wiki 上说经常有错误报道说欧几里德是假设所有的素数集，然后推出自相矛盾的
结果。但是我认为这样证明也是对的啊，只是它不是欧几里德的原版。
【在 d**********x 的大作中提到】
: 你要看看英文版wiki吗？
: 中文版wiki是错的。
:
: , 所
: 以必
: E.
| d**********x
发帖数: 4083 | 60 恩，看我后面的回复
我只是说中文wiki陈述错误
【在 g******y 的大作中提到】
: 我看了一下英文版，原来欧几里德原版是证明如果给定素数集是有限个，那么必然可以
: 再增加一个素数。
: 英文wiki 上说经常有错误报道说欧几里德是假设所有的素数集，然后推出自相矛盾的
: 结果。但是我认为这样证明也是对的啊，只是它不是欧几里德的原版。
| | | l*3
发帖数: 2279 | 61 不要没事干揣测我的行为.
也不要随口就说我曾经说过 "N一定是素数", 你能找出证据说明我在没有前提假设的情
况下, 说过这句话吗?
【在 c****n 的大作中提到】
: 这个才是原版，你把６３坚持了好几天的N一定只能是素数换成了N是合数，小心他跟你
: 反脸。
: 发信人: 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
: 可知: 对于任意i = 1,2,3,...,k, p_i 不能整除 N
: 由素数的定义:
: a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
| l*3
发帖数: 2279 | 62 不要没事干揣测我的行为.
也不要随口就说我曾经说过 "N一定是素数", 你能找出证据说明我在没有前提假设的情
况下, 说过这句话吗?
【在 c****n 的大作中提到】
: 这个才是原版，你把６３坚持了好几天的N一定只能是素数换成了N是合数，小心他跟你
: 反脸。
: 发信人: 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
: 可知: 对于任意i = 1,2,3,...,k, p_i 不能整除 N
: 由素数的定义:
: a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
| l*3
发帖数: 2279 | 63 你懂不懂什么叫 "反例"?
你给举个反例说明我的证明不对来看看?
【在 d*****n 的大作中提到】
: 正确的头。
: 反例都给你看了，还正确。
: 看来你被民科洗脑洗的不清。
| l*3
发帖数: 2279 | 64 呵呵, 我又被代表了.
请问我什么时候说过 "在前提假设下, 只能得出N是素数"?
你能不能把记录找出来? 找不出来就滚.
【在 c****n 的大作中提到】
: 没问题，所以原假设错误。
: 我一直说６３的结论不完备就是这点。
: 他可是坚持他的推论只能得出N是素数的结论。
| l*3
发帖数: 2279 | 65 傻逼, 你把我说过 "在前提假设下, 只能推出N是素数" 的言论找出来, 敢不?
连造谣的手段都开始用上了, 厉害.
【在 c****n 的大作中提到】
: 1. 63暂时还不承认，他认为得出合数的结论是因为用了合数的定义，而他的推理只用
: 了素数的定义，N只能是素数。
: ２。 如果知道N也能是合数，却仍坚持N是素数，不能否定原假设。因为素数有限的假
: 设推理无法证明所以N有一个一定能是素数，如果不讨论合数，并没有引入矛盾。
| l*3
发帖数: 2279 | 66 2楼你贴的我的证明贴的清清楚楚, 请问你哪只狗眼从里面看出来 "根据假设, 只能推
出N是素数, 不能推出N是合数" 这种话?
【在 c****n 的大作中提到】
: 1. 63暂时还不承认，他认为得出合数的结论是因为用了合数的定义，而他的推理只用
: 了素数的定义，N只能是素数。
: ２。 如果知道N也能是合数，却仍坚持N是素数，不能否定原假设。因为素数有限的假
: 设推理无法证明所以N有一个一定能是素数，如果不讨论合数，并没有引入矛盾。
| l*3
发帖数: 2279 | 67 你还是没有说明l63的证明是错的.
是不是人们一旦发现自己说的东西不成立了以后, 就会开始找各种借口?
比如你最开始认为 "l63的证明是错的", 后来发现证明没有问题, 结果只能改口为 "
l63的证明太繁琐, 太复杂, 太低级, 太没有档次, 太没有趣味"
我说的对不对?
【在 b******r 的大作中提到】
: 你下意识的用了质数的等价定义。有人指出了这个等价定义不是显而易见的，其证明复
: 杂度远超过只用基本素数定义来证明素数无穷多的原本欧几里德证明。
| l***o
发帖数: 7937 | 68 发信人: luobo (菠萝), 信区: Mathematics 标 题: Re: 素数有无穷多个, 你会证吗?
给大家奉上几篇欢乐的帖子. 发信站: BBS 未名空间站 (Thu May 23 03:55:43 2013,
美东)
你这个证明有点绕，感觉不够严密。这样证会更好一些 (给你改进了一下)。
假设：素数只有有限个, 记为 p_1, p_2, ..., p_k
考察 N = p_1*p_2*...*p_k + 1
显然 N 不能被所有 p_i 整除。（1）
但根据假设，N必为合数，必为已有素数之积，即必可被某些 p_i 整除。（2）
（1）（2）矛盾，假设不成立。
D
【在 f*******i 的大作中提到】
: 1. 假设p1=2,p2=3,...,pn 是全部的素数...
: 2. 令 N=p1*p2*...*pn+1, 显然 N比 p1,p2,...,pn都大,因此不再p1,p2,..,pn,中, 所
: 以根据1, N是一个合数.
: 3. N是合数,那么必然能够被一个素数整除, 根据1, 所有的素数是p1,..., pn, 所以必
: 然有其中之一, 比如pj, 能整除N, 特别的, N 除以pj余数为0
: 4. N= pj*(p2*...*pn 括号内排除pj)+1=pj*something+1, 因此, N除以pj余数为1
: 5. 3 和 4 矛盾,N不能同时除以pj余0,而且余1.
: 现在有几种推理方法
: 6(I), 3和4矛盾, 矛盾的根源在于 假设1 是完全错误的, 于是 证毕,素数无穷 Q.E.D
: 或者走下列路线(l63路线)
| l***o
发帖数: 7937 | 69 发信人: luobo (菠萝), 信区: Mathematics 标 题: Re: 素数有无穷多个, 你会证吗?
给大家奉上几篇欢乐的帖子. 发信站: BBS 未名空间站 (Fri May 24 00:19:43 2013,
美东)
发信人: 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 可知:
对于任意i = 1,2,3,...,k, p_i 不能整除 N 由素数的定义: a是素数 <=> a是大于1的
自然数, 且a不被任何小于a的素数整除 可知: N是素数 这与素数只有p_1,p_2,...,p_k
矛盾. 故假设不成立. 所以素数有无穷多个. -------------------------------------
回你最后一贴。你再看一下你的这个证明，是严格意义上的反证法吗？说说你哪里用到
了第一行的假设？
没有用到第一行假设的条件，直接得出N是素数。最后说“这与素数只有p_1,p_2,...,p
_k矛盾.” 你这还是不叫反证法的好，我看不如叫直接否定法。
另外，合数必被某个素数整除，注意这里是某个，不是全部，很弱的条件。用得着
fundamental theorem of arithmetic吗？再说这个theorem公元前300年Euclid就提出
来了，算是最最基本的定理了。
D
【在 f*******i 的大作中提到】
: 1. 假设p1=2,p2=3,...,pn 是全部的素数...
: 2. 令 N=p1*p2*...*pn+1, 显然 N比 p1,p2,...,pn都大,因此不再p1,p2,..,pn,中, 所
: 以根据1, N是一个合数.
: 3. N是合数,那么必然能够被一个素数整除, 根据1, 所有的素数是p1,..., pn, 所以必
: 然有其中之一, 比如pj, 能整除N, 特别的, N 除以pj余数为0
: 4. N= pj*(p2*...*pn 括号内排除pj)+1=pj*something+1, 因此, N除以pj余数为1
: 5. 3 和 4 矛盾,N不能同时除以pj余0,而且余1.
: 现在有几种推理方法
: 6(I), 3和4矛盾, 矛盾的根源在于 假设1 是完全错误的, 于是 证毕,素数无穷 Q.E.D
: 或者走下列路线(l63路线)
| q*c
发帖数: 9453 | 70 ?
14%2=0
【在 b*********z 的大作中提到】
: 3是错误的。3的前提是任意大于pn的整数都能被已知素数整除，这是错误的。
: 假设2，3，5是已知素数，14就不满足。
: 除非这个逻辑被补充，否则论证是不严谨的。我认为素数分解理论在这里不适用。
: 附3原文
: 3. N是合数,那么必然能够被一个素数整除, 根据1, 所有的素数是p1,..., pn, 所以必
: 然有其中之一, 比如pj, 能整除N, 特别的, N 除以pj余数为0
: 另，反正法要和初始假设矛盾。
| | | l*3
发帖数: 2279 | 71 你就别在这掰扯了.
我已经说了, 在某些 "吹毛求疵的标准" 下, 我的证明书写 "不够规范".
--------
你用你这种吹毛求疵的态度对待别人的时候, 先自省一下合数的朴素定义吧, loser.
吗?
2013,
_k
---
【在 l***o 的大作中提到】
: 发信人: luobo (菠萝), 信区: Mathematics 标 题: Re: 素数有无穷多个, 你会证吗?
: 给大家奉上几篇欢乐的帖子. 发信站: BBS 未名空间站 (Fri May 24 00:19:43 2013,
: 美东)
: 发信人: 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 可知:
: 对于任意i = 1,2,3,...,k, p_i 不能整除 N 由素数的定义: a是素数 <=> a是大于1的
: 自然数, 且a不被任何小于a的素数整除 可知: N是素数 这与素数只有p_1,p_2,...,p_k
: 矛盾. 故假设不成立. 所以素数有无穷多个. -------------------------------------
: 回你最后一贴。你再看一下你的这个证明，是严格意义上的反证法吗？说说你哪里用到
| C**********r
发帖数: 8189 | 72
吗?
2013,
这个好，完全避免了对N的分类，只要N不能被任何a_i整除，就可以得出另有新质数了
。定义N本身是合是质有点无谓，定得不好还要被捉班头。
【在 l***o 的大作中提到】
: 发信人: luobo (菠萝), 信区: Mathematics 标 题: Re: 素数有无穷多个, 你会证吗?
: 给大家奉上几篇欢乐的帖子. 发信站: BBS 未名空间站 (Fri May 24 00:19:43 2013,
: 美东)
: 发信人: 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 可知:
: 对于任意i = 1,2,3,...,k, p_i 不能整除 N 由素数的定义: a是素数 <=> a是大于1的
: 自然数, 且a不被任何小于a的素数整除 可知: N是素数 这与素数只有p_1,p_2,...,p_k
: 矛盾. 故假设不成立. 所以素数有无穷多个. -------------------------------------
: 回你最后一贴。你再看一下你的这个证明，是严格意义上的反证法吗？说说你哪里用到
| l*3
发帖数: 2279 | 73 你想看这种 "好" 的证明, 是吧?
我给你来一个:
假设: 素数只有有限个, 记为p_1,p_2,...,p_k
考察 N = p_1*p_2*...*p_k + 1
显然 N 不能被任意一个p_i整除. (1)
又因为 N是大于1的自然数, 所以N必有素因子, 根据假设, 素因子只可能在p_1,p_2,..
.,p_k中.
于是 必有p_i∈{p_1,p_2,...,p_k} 使得p_i能整除 N (2)
(1) 和 (2) 矛盾, 假设不成立.
-------
这个证明 "好" 不 "好" ?
"N为素数" 和 "N为合数" 都不屑于说了.
【在 C**********r 的大作中提到】
:
: 吗?
: 2013,
: 这个好，完全避免了对N的分类，只要N不能被任何a_i整除，就可以得出另有新质数了
: 。定义N本身是合是质有点无谓，定得不好还要被捉班头。
| C**********r
发帖数: 8189 | 74 我一开始就说你的证明没有大漏洞，框架是对的，就是论证用词需要严谨。这件事互骂
文科生的太多了，我看到的是双方的真实理解差异并不大，但是误会很大，所以归纳为
语文问题。支持你的一方，死认别人逻辑不通，数学差，还拼命科普反证法。反证法又
不难，又不是关键差异，差异在表述。
..
【在 l*3 的大作中提到】
: 你想看这种 "好" 的证明, 是吧?
: 我给你来一个:
: 假设: 素数只有有限个, 记为p_1,p_2,...,p_k
: 考察 N = p_1*p_2*...*p_k + 1
: 显然 N 不能被任意一个p_i整除. (1)
: 又因为 N是大于1的自然数, 所以N必有素因子, 根据假设, 素因子只可能在p_1,p_2,..
: .,p_k中.
: 于是 必有p_i∈{p_1,p_2,...,p_k} 使得p_i能整除 N (2)
: (1) 和 (2) 矛盾, 假设不成立.
: -------
| l***o
发帖数: 7937 | 75 烦请转交163。谢谢
--------------------------
合数必被某一素数整除
合数的定义：除了1和它本身之外还有别的divisor.
如果这个divisor是素数，done; 如果这个divisor还是合数，repeat. | l*3
发帖数: 2279 | 76 已收到.
如果是一种承认错误的方式, 那么我收下了, 谢谢.
---------
以及, 在你的命题的基础上:
如果a是大于1的自然数, 那么:
"a不是素数" <=> "a是合数" <=> "a有素因子"
又因为因子必小于a, 故
"a有素因子" <=> "a有小于a的素因子"
那么:
如果a是大于1的自然数, 那么 "a是素数" <=> "a没有小于a的素因子"
又知:
素数是大于1的自然数.
那么:
a是素数<=>a是大于1的自然数, 且a没有小于a的素因子
----------
you are right, it's too long, not trivial.
【在 l***o 的大作中提到】
: 烦请转交163。谢谢
: --------------------------
: 合数必被某一素数整除
: 合数的定义：除了1和它本身之外还有别的divisor.
: 如果这个divisor是素数，done; 如果这个divisor还是合数，repeat.
| C**********r
发帖数: 8189 | 77 okay, 结案。
【在 l*3 的大作中提到】
: 已收到.
: 如果是一种承认错误的方式, 那么我收下了, 谢谢.
: ---------
: 以及, 在你的命题的基础上:
: 如果a是大于1的自然数, 那么:
: "a不是素数" <=> "a是合数" <=> "a有素因子"
: 又因为因子必小于a, 故
: "a有素因子" <=> "a有小于a的素因子"
: 那么:
: 如果a是大于1的自然数, 那么 "a是素数" <=> "a没有小于a的素因子"
| l***o
发帖数: 7937 | 78 发信人: luobo (菠萝), 信区: Mathematics
标 题: Re: 素数有无穷多个, 你会证吗? 给大家奉上几篇欢乐的帖子.
发信站: BBS 未名空间站 (Thu May 23 11:59:32 2013, 美东)
（1）首先，题目很小。引用素数的非常规“定义”（叫引理更合适），杀猪用牛刀。
只会是证明复杂化。没证明这个引理你已经省了好多篇幅了。
（2）其次，你这个非常规“定义”本身并不自动暗示N是素数（注意这个定义里：用的
是a，不是N，应该泛指一般情形）。N满足定义才能说N是素数。你对素数的定义：不被
任何小于它的素数整除且大于1的自然数。这里你漏掉了N是如何满足你这个定义的这个
关键环节而直接得出N是素数。这个属于逻辑跳跃。这里需要清楚写明：
（A）N为大于1的自然数，这个trivial，不必多言。
（B）根据原始假设，p_i （i=1,2，。。。，k）是小于N的所有素数。这个很关键。
（C）N不能被所有p_i整除。这个前面已有结论。
基于（A)(B)(C)三点，才可得出N是素数的结论，与原始假设矛盾。实际上反证法不必
要求与原始假设矛盾，出来的任何矛盾都可否定原始假设。 | l***o
发帖数: 7937 | 79 嗯，结案。
【在 C**********r 的大作中提到】
: okay, 结案。
| l***o
发帖数: 7937 | 80 DING
吗?
2013,
【在 l***o 的大作中提到】
: 发信人: luobo (菠萝), 信区: Mathematics
: 标 题: Re: 素数有无穷多个, 你会证吗? 给大家奉上几篇欢乐的帖子.
: 发信站: BBS 未名空间站 (Thu May 23 11:59:32 2013, 美东)
: （1）首先，题目很小。引用素数的非常规“定义”（叫引理更合适），杀猪用牛刀。
: 只会是证明复杂化。没证明这个引理你已经省了好多篇幅了。
: （2）其次，你这个非常规“定义”本身并不自动暗示N是素数（注意这个定义里：用的
: 是a，不是N，应该泛指一般情形）。N满足定义才能说N是素数。你对素数的定义：不被
: 任何小于它的素数整除且大于1的自然数。这里你漏掉了N是如何满足你这个定义的这个
: 关键环节而直接得出N是素数。这个属于逻辑跳跃。这里需要清楚写明：
: （A）N为大于1的自然数，这个trivial，不必多言。
| | | C**********r
发帖数: 8189 | 81 支持
【在 l***o 的大作中提到】
: DING
:
: 吗?
: 2013,
|
|
