最后说一下这个反证法# WaterWorld - 未名水世界
c*n
1 楼
最后一贴,做个总结。
欧几里德关于质数无限的证明方法是反证法一个著名的例子。三七二十八扯了一晚上,
不妨在多说几句,就当是锻炼自己了。
老欧说,让我们假设质数是有限的,那所有的(除了1)质数在一个集合P中,P1=2,P2=
3……………….Pn=n. 根据这个假设,所有的自然数(除了1)都可以用这个集合的某
种连乘形式表示,例如a=P1*P1*P7, b=P2*P3*P5*P11,没有例外。
可是,如果我们现在构造一个新数N=P1*P2*P3……………..*Pn+1, 为什么加1,因为加
其他任何数,根据我们的假设,都可以写成集合P中的一个连续乘积,从而可以和前面
的P1*P2*P3……………..*Pn 合并同类项。为什么一个都不能少,因为如果少一个Pm的
话,这个新数N不能被证否不含Pm因子。当然多乘几次没问题,我们就选最简单的一次
了。为什么不是减1,不好意思,我没看出什么显然的地方能给证明我的结论。
Anyway, 我们构造了一个新数N,它显然在自然数范围内,它也很显然不能用集合P里的
任何连乘形式来表达,所以原假设质数是有限是不成立的。到这一步,我们的证明已经
结束了。好了,这里我们并不需要说明这个新数N,是质数还是合数,它是什么其实不重
要,只要知道这么个数存在就够了,我们的证明已经结束了。我们的假设已经证明是错
误的,不能通过它对新数N进行判断。
可是数学证明都是要给大家一个交代的,这个N到底是啥,有无可能影响前面的证明,
好在这个交代并不复杂,因为这个数N,要么是质数,要么是合数,两个情况都讨论一下
,这个证明就完整了。N竟然不是质数,竟然是质数?这个反证法的假设不能做出判断
,因为数N构造成功的时候,原假设已经不成立了,后面N是什么已经和它无关了。
如果还不清楚的话,好在这个证明的例子很多,再说一个变形。先谈点背景。首先是质
数公式的存在性,可以google费马数。简单说就是能不能找到一个解析式,它表达的自
然数都是质数。费马说我发现了一个2^2^n-1就是,他演算了n=0,1,2,3,4都是,那后面
的也一定就是了。一百年后,费马数被超级大牛欧拉暴力否决了。欧拉发现F5 = 232 +
1 = 4294967297 = 641 × 6700417, 这个结果在现在很容易用计算机验证,不过400
年前的欧拉是一个个算过来的。这样的素数公式现在还没有找到。所以,计算机年代,
人们又搞了一个新的游戏,寻找最大的质数。为什么不加上一个(已知),因为我们假
设还没有看到上面那个无限的证明。
那么假设存在一个最大的质数,这个假设和上面那个质数是有限的完全等价,连证明方
法都一样。反证法的结论是无论多大的质数Pn, 总存在一个数N= P1*P2*P3…………….
.*Pn+1包含了比Pn还大的质数。 那Pn自己到底是不是质数呢,我们还是不知道。 如果
P1*P2*P3……………..*Pn+1肯定是质数,那么我们就发现了一个质数公式,计算机也
不需要需找最大质数了,拿公式乘就可以了。目前证明的已知最大质数是2^57,885,161
− 1 ,如果这个证明的N肯定是质数,那从2*3*………..2^57885161+1就是一个
新的更大的质数。可惜,我们不知道它是还是不是,我们只知道,在它和我们已经发现
的最大质数之间,肯定至少有两个更达的质数,到底是那个,谁也不知道。要证明一个
数是否是质数,现在还是要靠暴力,不过是从铅笔换成了计算机。
欧几里德关于质数无限的证明方法是反证法一个著名的例子。三七二十八扯了一晚上,
不妨在多说几句,就当是锻炼自己了。
老欧说,让我们假设质数是有限的,那所有的(除了1)质数在一个集合P中,P1=2,P2=
3……………….Pn=n. 根据这个假设,所有的自然数(除了1)都可以用这个集合的某
种连乘形式表示,例如a=P1*P1*P7, b=P2*P3*P5*P11,没有例外。
可是,如果我们现在构造一个新数N=P1*P2*P3……………..*Pn+1, 为什么加1,因为加
其他任何数,根据我们的假设,都可以写成集合P中的一个连续乘积,从而可以和前面
的P1*P2*P3……………..*Pn 合并同类项。为什么一个都不能少,因为如果少一个Pm的
话,这个新数N不能被证否不含Pm因子。当然多乘几次没问题,我们就选最简单的一次
了。为什么不是减1,不好意思,我没看出什么显然的地方能给证明我的结论。
Anyway, 我们构造了一个新数N,它显然在自然数范围内,它也很显然不能用集合P里的
任何连乘形式来表达,所以原假设质数是有限是不成立的。到这一步,我们的证明已经
结束了。好了,这里我们并不需要说明这个新数N,是质数还是合数,它是什么其实不重
要,只要知道这么个数存在就够了,我们的证明已经结束了。我们的假设已经证明是错
误的,不能通过它对新数N进行判断。
可是数学证明都是要给大家一个交代的,这个N到底是啥,有无可能影响前面的证明,
好在这个交代并不复杂,因为这个数N,要么是质数,要么是合数,两个情况都讨论一下
,这个证明就完整了。N竟然不是质数,竟然是质数?这个反证法的假设不能做出判断
,因为数N构造成功的时候,原假设已经不成立了,后面N是什么已经和它无关了。
如果还不清楚的话,好在这个证明的例子很多,再说一个变形。先谈点背景。首先是质
数公式的存在性,可以google费马数。简单说就是能不能找到一个解析式,它表达的自
然数都是质数。费马说我发现了一个2^2^n-1就是,他演算了n=0,1,2,3,4都是,那后面
的也一定就是了。一百年后,费马数被超级大牛欧拉暴力否决了。欧拉发现F5 = 232 +
1 = 4294967297 = 641 × 6700417, 这个结果在现在很容易用计算机验证,不过400
年前的欧拉是一个个算过来的。这样的素数公式现在还没有找到。所以,计算机年代,
人们又搞了一个新的游戏,寻找最大的质数。为什么不加上一个(已知),因为我们假
设还没有看到上面那个无限的证明。
那么假设存在一个最大的质数,这个假设和上面那个质数是有限的完全等价,连证明方
法都一样。反证法的结论是无论多大的质数Pn, 总存在一个数N= P1*P2*P3…………….
.*Pn+1包含了比Pn还大的质数。 那Pn自己到底是不是质数呢,我们还是不知道。 如果
P1*P2*P3……………..*Pn+1肯定是质数,那么我们就发现了一个质数公式,计算机也
不需要需找最大质数了,拿公式乘就可以了。目前证明的已知最大质数是2^57,885,161
− 1 ,如果这个证明的N肯定是质数,那从2*3*………..2^57885161+1就是一个
新的更大的质数。可惜,我们不知道它是还是不是,我们只知道,在它和我们已经发现
的最大质数之间,肯定至少有两个更达的质数,到底是那个,谁也不知道。要证明一个
数是否是质数,现在还是要靠暴力,不过是从铅笔换成了计算机。