《什么是数学》读书笔记(一):反证法、数学归纳法与唯一分解定理

《什么是数学》读书笔记(一):反证法、数学归纳法与唯一分解定理

    期中告一段落。除了下下星期要交的现文史论文以外,最近似乎又清闲了不少,又有功夫在这里写点东西了。当然,我宝贵的时间也没有荒废在论文、作业和考试上。几乎每一堂古汉课和现文史课我都在读《什么是数学》,进度算是相当快了。这可能是我近几年读的所有书中给我带来的收获最大的一本。最近好几个人问我,有什么牛B一点的数学书没。我毫不犹豫地脱口而出,《什么是数学》。如果我要去一个荒岛上,只能带三本书,我会选择《算法导论》、《组合数学》和《什么是数学》。如果叫我舍弃一样,我估计会扔掉《组合数学》。如果还得再丢弃一本,我只好忍痛丢下《算法导论》了。
    读《什么是数学》的收获太多了。在这里,我只更新一些我原来不知道,又很有趣的东西。如果你希望迅速对此书有一个全面的了解,千万不要错过dd牛的《什么是数学》笔记。

    阅读《什么是数学》的前面几章时,你经常会跟随着书中的文字重新看待一个显而易见的结论,然后对这个结论有了一个全新的认识。比如,书中曾提到,为什么数学归纳法是合理的?我已经知道n=1时结论成立,也知道若n=k成立则n=k+1结论也成立,那么对于任意一个给定的正整数t,n=t时的结论是成立的,因为经过有限次迭代后最终我们总可以到达n=t的情况。但是,为什么我们敢断言对所有这无穷多个n,结论都是成立的?显然,你不能说“我们可以迭代无穷多次”,一个有限的证明过程当然不允许有无限多个步骤。因此,为了说明对于所有正整数n结论都成立,我们不得不使用反证法把“无穷”变成“有穷”。我们假设对于某些n,这个结论是不成立的。那么,这里面一定存在一个最小的数p,它使得结论不成立。由于我们已知n=1时结论成立,因此p一定是大于1的。但n=p是“最早”使结论不成立的情形,因此n=p-1时结论一定为真。这就与我们已知的第二个条件“若n=k成立则n=k+1结论也成立”矛盾了。因此我们说,对于所有正整数n,结论都是成立的。
    这个推理过程中用到了另一个显而易见的结论:对于一个非空的正整数集C,C中一定存在一个最小的元素。这又是为什么呢?你可能会说,废话,把所有元素拿出来两个两个的比,一定能比出一个最小的数来。这种说法是错误的。注意到集合C有可能有无穷多个元素,你是比不完的。为了更清晰地认识这个结论,我们只需要注意到,如果把条件换成“有理数集C”或者“实数集C”,结论就不再成立了,因为集合{1, 1/2, 1/3, 1/4, …}显然不存在一个最小的数。可以看到,上述结论是否成立是和数的稠密性紧紧相关的。事实上,为了说明正整数集C中存在最小元素,我们任意从集合中取出一个元素n,那么1, 2, …, n这有限多个数当中一定存在一个最小的数,它在这个集合C中。它就是整个集合的最小数。对于稠密的有理数点和实数点,这个证明显然不再适用。

    下面将提到的一个定理也是看上去非常显然的。算术基本定理是说,任意一个大于1的正整数都能表示成若干个质数的乘积,且表示的方法是唯一的。换句话说,一个数能被唯一地分解成质因数的乘积。因此这个定理又叫做唯一分解定理。唯一分解定理是数论中最最基本的定理之一,如果连这个定理都错了,那整个算术也就不存在了。很多结论的证明过程都用到了这一事实,例如我们可以用这个定理来证明根号2是无理数

    假设(p/q)^2=2,那么p^2=2q^2。我们将要证明,一个数的平方等于另一个数的平方的两倍是根本不可能的。如果对一个平方数分解质因数,它必然有偶数个因子(x^2的所有质因子就是把x的质因子复制成两份)。于是,p^2有偶数个质因子,q^2有偶数个质因子,2q^2有奇数个质因子。等号左边的数有偶数个质因子,等号右边的数有奇数个质因子,大家都知道这是不可能的,因为同一个数只有一种分解质因数的方法(唯一分解定理)。

    好,现在的问题是,为什么质因数分解的方法是唯一的。这个结论是如此的显然和易于接受,以致于有人会脱口而出:这当然是唯一的,不断使用越来越大的质数去试除,最后得到的肯定是唯一的质因数分解。不可否认,这个算法本身是没有任何问题的。根据合数的定义,试除与分解是一定能不断进行下去的,除非被除数本身变成了一个质数,而此时也标志着算法的结束。问题的关键就在于,这并不能说明原数能唯一地表示成质数的乘积:换一种试除的顺序会不会得出不同的分解方法?万一还有什么别的牛B大法也能用来分解质因数,而且结果与上面得到的完全不一样咋办?上面给出的算法只能说明我们能找出至少一种分解质因数的方法,用这种方法得到的结果是唯一的,但到底还有没有其它偏方秘籍能导出另外的分解方法来,我们就不得而知了。为了真正地证明,分解质因数的方法是唯一的,我们将再次用到反证法。假设存在某些数,它们有至少两种分解方法。那么根据上文提到的“非空正整数集里存在最小的元素”,一定有一个最小的数M,它能用至少两种方法表示成质数的乘积:
   M = P1 * P2 * … * Pr = Q1 * Q2 * … * Qs
    下面我们将看到,这种假设会推出一个多么荒谬的结果来。不妨设P1 <= P2 <= ... <= Pr, Q1 <= Q2 <= ... <= Qs。显然,P1是不等于Q1的,不然两边同时约掉它,我们就得到一个更小的有两种分解方法的数。不妨设P1 < Q1,那么我们用P1替换掉等式最右边中的Q1,得到一个比M更小的数T = P1 * Q2 * Q3 * ... * Qs。令M' = M - T,我们得到M'的两种表达:    M' = (P1 * P2 * ... * Pr) - (P1 * Q2 * ... * Qs) = P1 * (P2 * .. * Pr - Q2 * ... * Qs)  ……  (1)    M' = (Q1 * Q2 * ... * Qs) - (P1 * Q2 * ... * Qs) = (Q1 - P1) * Q2 * ... * Qs  ………………  (2)     由于T比M小,因此M'是正整数。从(1)式中我们立即看到,P1是M'的一个质因子。注意到M'比M小,因此它的质因数分解方式应该是唯一的,可知P1也应该出现在表达式(2)中。既然P1比所有的Q都要小,因此它不可能恰好是(2)式中的某个Q,于是只可能被包含在因子(Q1-P1)里。但这就意味着,(Q1-P1)/P1除得尽,也就是说Q1/P1-1是一个整数,这样Q1/P1也必须得是整数。我们立即看出,P1必须也是Q1的一个因子,这与Q1是质数矛盾了。这说明,我们最初的假设是错误的。     唯一分解定理的一个重要的推论是,如果质数p是ab的因子,那么p或者是a的因子,或者是b的因子。我们刚才在证明过程中也不自觉地用到了这个推论。证明方法很简单,假如a和b里面都不含p,把a和b各自分解开来再乘到一起,我们就得到了数ab的一个没有因子p的分解方式;而按照前面提到的试除法,ab是可以表示成p与另一些质数的乘积的,这违背了唯一分解定理。连续多次使用该推论,我们可以很快将推论推广到多个数的情形。     事实上,假设这个推论成立,我们也能很快反过来推出唯一分解定理:写出N的两种质因数分解,在前一种分解中任取一个因子,它必然会在后一种分解方法中出现;把它们约掉之后结论继续适用,不断进行该操作直到最终两边都只余下一个1。这一系列操作说明了,两种分解方法实际上是相同的。我们看到,唯一分解定理和它的推论实际上是等价的。如果我们能够绕过唯一分解定理,用另一种方法证出这个推论,我们也就相当于找到了唯一分解定理的另一个证明。而事实上,运用扩展的辗转相除算法,我们可以飞快地完成推论的证明。我们将说明,如果质数p能整除ab,但不整除a,那它一定是b的约数。     质数p不能整除a,告诉我们a和p互质,于是存在整数k和l使得ka + lp = 1。等式两边同时乘以b,我们有kab + lpb = b。而ab能被p整除,也即存在整数r使得ab=pr。那么,kpr + lpb = p(kr + lb) = b,我们立即看出p是b的一个约数。

上一篇:Linux常用命令


下一篇:如何应用性能测试常用计算公式