紫牛、俄罗斯方块与数学定理的证明
数学的一大乐趣，也是数学不同于其他科学的显著标志，就是它可以通过证明的方式帮助我们拨云见日，消除疑虑。在其他科学领域，我们之所以接受某些法则，是因为这些法则与现实世界一致，但一旦有新的证据出现，这些法则就有可能被推翻或者修改。在数学领域，如果某个命题被证明为真，那么它将永远是真实的。例如，欧几里得早在两千多年前就证明了质数有无数个，对于这个命题的真实性，我们无须怀疑。技术诞生之后还会退出历史舞台，但数学定理亘古不变。伟大的数学家高德菲·哈罗德·哈代（G. H. Hardy）说过：“同画家和诗人一样，数学家也是规律的创造者。数学家创造的规律之所以更加持久，原因就在于这些规律中蕴藏着思想。”我常常想，要想在学术方面取得不朽的成绩，最好的办法就是证明一条新的数学定理。
数学家不仅可以证明某些事情的确定性，还可以证明某些事情是不可能的。人们有时说：“你无法证伪。”这句话的意思是，你无法证明紫色奶牛不存在，因为说不定哪天就会出现一头这样的奶牛。但在数学领域，你可以证伪。例如，无论你怎么努力，都找不到和为奇数的两个偶数，也找不到比其他质数都大的质数。第一次接触时，证明可能会让我们望而生畏（也许第二次、第三次时我们还会感到害怕），需要不断练习才能逐渐适应。但是，一旦你精于此道，就会觉得其乐无穷，无论是你自己动手证明，还是看别人的证明过程。好的证明就像一个精彩的故事，让你满心愉悦。
接下来，我和大家分享我第一次证明某件事是不可能的经历。小时候，我喜欢玩游戏、做智力测试题。一天，一位朋友给我出了一道难题，让我兴致盎然。他拿出一个空的8×8棋盘和32个普通的1×2双方块，然后问我：“你可以用这些双方块，把整个棋盘都盖住吗？”我说：“当然可以，只要每行放4个双方块就行了。”
用1×2的双方块覆盖8×8的棋盘
他说：“非常好！现在，我们把右下角和左上角的这两个方格去掉。”说完，他在这两个方格上各放了一枚硬币，表示这两个区域不存在。“你可以用31个双方块覆盖棋盘上剩下的62个方格吗？”
去掉右下角和左上角的两个方格之后，双方块可以盖住整个棋盘吗？
“也许可以吧。”我答道。但是，无论我怎么摆放，双方块都无法盖住整个棋盘。于是我想，这个任务是不是不可能完成呢？
“如果你觉得这个任务无法完成，你如何证明？”朋友问道。但是，摆放双方块的方法有无数种，如果我不一一尝试，怎么能证明这是一个不可能完成的任务呢？这时候，他给了我一点儿提示：“观察一下棋盘上的颜色。”
颜色？这与颜色有什么关系？我突然想明白了。由于去掉的两个方格都是浅色的，因此棋盘上还剩下32个深色方格和30个浅色方格。每个双方块正好覆盖一个浅色方格和一个深色方格，所以用31个双方块不可能盖住整个棋盘。太棒了！
延伸阅读
如果你喜欢上面的证明过程，那么你肯定也会喜欢下面这个证明过程。俄罗斯方块游戏中有7种形状各异的板块，有时候它们分别被称为I、J、L、O、Z、T、S。
这7个板块可以拼成一个4×7的长方形吗？
由于每个板块都包含4个1×1方块，因此我们自然想知道7个板块是不是可以拼成一个4×7的长方形，拼装的时候可以翻转或旋转这些板块。事实证明，这个任务是无法完成的。如何证明它是不可能的呢？如下图所示，把4×7长方形涂成14个浅色方格和14个深色方格。
请注意，除了T以外，其他的板块无论摆放到哪个位置上，都会覆盖两个深色方格和两个浅色方格。而在T覆盖的4个方格中，有三个方格的颜色一样。因此，无论其余6个板块怎么摆放，它们都会覆盖12个浅色方格和12个深色方格。剩余的2个浅色方格和2个深色方格只能用板块T来覆盖，而这是不可能的。
如果我们认为某个数学命题是真实的，怎样才能证明它的确是真实的呢？通常，先要对我们所研究的数学对象进行描述。例如，我们说整数集合
…，–2，–1，0，1，2，3，…
包含所有整数：正数、负数和零。
之后，我们要对这些对象做出一些显而易见的假设。例如，“两个整数的和或积一定是整数”。（下一章将讨论几何学，届时我们会做出这样的假设：“对于任意两点，都可以画出一条经过这两点的直线”。）这些显而易见的命题叫作“公理”（axioms）。在这些公理的基础上，通过逻辑推理和代数运算，我们经常可以推导出一些正确的命题，叫作“定理”（theorems）。定理有时候并不是显而易见的。阅读本章，你可以学会证明数学命题的基本方法。
我们先来证明一些很容易取信于人的定理。第一次听到“两个偶数的和是偶数”、“两个奇数的乘积是奇数”等命题时，我们通常会默默地举出几个实例，检验之后才会断定这个命题是真实的或者有道理的。你有时甚至会想，这个命题太显而易见了，都可以当作公理使用了。但是，我们没必要把它作为公理，因为利用已知的公理，可以证明这个命题为真。在证明偶数和奇数的某些属性时，我们需要先弄明白它们的含义。
“偶数”是2的倍数。用代数语言来表述的话，就是如果n = 2k，k是整数，那么我们说n是偶数。0是不是偶数呢？是偶数，因为0 = 2×0。现在，我们可以证明“两个偶数的和是偶数”这个命题了。
定理：如果m和n是偶数，那么m + n也是偶数。
这是一个典型的“如果—那么”定理。在证明这种命题时，我们通常会对“如果”部分做出假设，然后通过逻辑和代数运算，证明可以根据假设得出“那么”部分。在本例中，我们假设m和n是偶数，希望得出m + n也是偶数的结论。
证明：假设m和n是偶数，因此m = 2j，n = 2k，其中j和k都是整数，进而可以得出：
m + n = 2j + 2k = 2 (j + k)
由于j + k是整数，因此m + n是2的倍数，从而证明m + n必然是偶数。
注意，上述证明的依据是，两个整数的和（即本例中的j + k）也必然是整数这条公理。在证明复杂的命题时，我们不仅需要依赖一些基本公理，还可能需要利用已经被证明的定理。数学界的一个常见做法就是在证明结束之后，在最后一行的右侧页边添加一个标识，例如□、■或者Q. E .D。Q. E. D是拉丁语“quod erat demonstrandum”的缩写，意思是“证明完毕”。（如果你愿意，你也可以把它看作英语“quite easily done”的缩写，意思是“太简单了”。）如果我认为某个证明过程特别美妙，我就会在结尾处画一个笑脸符号（）。
在证明了“如果—那么”定理之后，数学家们开始考虑逆命题的真实性。逆命题就是把原命题的“如果”和“那么”这两个部分对调之后得到的命题。上例的逆命题是：“如果m + n是偶数，那么m和n都是偶数”。只需举出一个“反例”（counterexample），就能很容易地证明这是一个假命题。对于这个命题而言，我们可以举一个非常简单的反例：
1 + 1 = 2
这个例子表明，即使两个数不是偶数，它们的和也可以是偶数。
下面讨论一条关于“奇数”的定理。奇数是指不是2的倍数的数字。如果用2除以一个奇数，余数一定是1。用代数语言来表述，就是如果n = 2k + 1，k是整数，那么n是奇数。有了这个定义之后，我们只需通过简单的代数运算，就能证明“两个奇数的乘积是奇数”这个命题。
定理：如果m和n是奇数，那么mn也是奇数。
证明：假设m和n是奇数。那么m = 2j + 1，n = 2k + 1，j、k是整数。根据FOIL法则：
mn = (2j + 1) (2k + 1) = 4jk + 2j + 2k + 1 = 2 (2jk + j + k) + 1
由于2jk + j + k是整数，因此mn是“某个整数的2倍 + 1”，从而证明mn是奇数。 □
它的逆命题“如果mn是奇数，那么m和n都是奇数”是否为真呢？这个命题也是真命题，我们可以利用“反证法”（proof by contradiction）来证明。反证法是指，如果我们否定结论（“m、n都是奇数”），我们之前做出的假设就不成立。因此，从逻辑上讲，结论必定是成立的。
定理：如果mn是奇数，那么m和n都是奇数。
证明：与结论相反，我们假设m或n是偶数（或同为偶数）。这两个数字中到底哪一个是偶数无关紧要，我们假定m是偶数，也就是说，m = 2j，j为整数。那么，乘积mn = 2jn也是偶数，这与我们之前假设mn是奇数的前提相悖。
如果某个命题和它的逆命题都是真命题，数学界就称之为“当且仅当定理”（if and only if theorem）。我们前面已经完成了下述定理的证明工作。
定理：当且仅当mn是奇数时，m和n都是奇数。
有理数和无理数
上述定理不会让你感到吃惊，它们的证明过程也非常直接。只在证明某些不太直观的定理时，我们才可以体会到其中的乐趣。到目前为止，我们接触的都是整数，现在可以进阶到分数的相关定理的证明了。“有理数”（rational number）是指可以表示为分数形式的数字。更准确的说法是，如果r = a / b，其中a和b是整数（且b ≠ 0），那么我们说r是有理数。不能表示为分数形式的数字叫作“无理数”（irrational number）。（你或许听说过，数字π= 3.141 59…就是无理数，我们将在本书第8章对它进行详细介绍。）
在介绍下一个定理之前，我们有必要回顾一下分数的加法。如果分数的分母相同，进行加法运算时就极为简单。例如：
否则，我们必须先把它们化成分母相同的形式，再进行加法运算。例如：
一般而言，在计算两个分数 a / b和c / d的和时，我们可以为它们赋予一个公分母，例如：
接下来，我们就可以证明有理数的一些简单属性了。
定理：两个有理数的平均数仍然是有理数。
证明：令x和y为有理数，必然存在a、b、c、d，满足x = a / b，y = c / d。所以，x和y的平均数为：
由此可见，该平均数是一个分数，且分子、分母均为整数。因此，有理数x和y的平均数也是有理数。
我们想一想，这个定理有什么含义？它的意思是，对于任意两个有理数，即使它们非常接近，我们也总能找出一个位于它们之间的有理数。也许你忍不住会想，所有的数字都是有理数（古希腊人也曾有这样的想法）。但是，令人吃惊的是，这个想法是错误的。我们以为例，这个数字的小数形式是1.414 2…。现在，我们有很多方法，用分数来近似地表示。例如，近似等于10 / 7或者1 414 /1 000，但是这些分数的平方都不会正好等于2。是不是因为我们找得还不够仔细呢？下面这个定理告诉我们，无论我们怎么努力，都会无功而返。该定理的证明采用了反证法，关于无理数的定理通常都会采用这种证明方法。我们知道，所有分数都可化简至最简分数，即分子和分母没有大于1的公因数。下面的证明过程就将利用分数的这个特点。
定理：是无理数。
证明：我们假设是有理数，则必然存在正整数a和b，满足：
= a / b
其中，a / b是最简分数。等式两边同时进行平方运算，就有：
2 = a2 / b2
也就是说，a2 = 2b2。由此可知，a2必然是偶数。如果a2是偶数，那么a也必然是偶数（前文中已经证明，如果a是奇数，那么其自乘的结果也必然是奇数）。因此，a = 2k，k是整数。将它代入上面的等式，就有：
(2k)2 = 2b2
4k2 = 2b2
b2 = 2k2
因此，b2是偶数。既然b2是偶数，b也必然是偶数。但是，a和b都是偶数，这与a / b是最简分数的前提相矛盾。因此，是有理数这个假设不成立，这证明是无理数。
单凭逻辑的力量，就证明了一个非常令人吃惊的结果，所以我十分喜欢这个证明过程（画了个笑脸）。本书第12章将告诉我们，无理数非常多。事实上，从严格意义上讲，绝大多数的实数都是无理数，尽管我们在日常生活中接触的大多是有理数。
上面这条定理有一个有趣的“推论”（corollary），推论是指由某条定理推导得出的定理。这个推论的推导过程利用了“指数定律”（law of exponentiation），即对于任意整数a、b、c：
（ab）c = abc
例如，（53）2 = 56，这是有道理的，因为：
（53）2 = (5 × 5 × 5) × (5 × 5 × 5) = 56
推论：存在无理数a和b，使得ab是有理数。
尽管现在我们只知道一个无理数，即，但足以证明这条定理，这真是太棒了！下面的证明过程可以告诉你符合条件的a和b是存在的，但不能告诉你它们的值分别是多少。我们把这种证明称为“存在性证明”（existence proof）。
证明：我们知道是无理数，我们来看这个数字，它是不是有理数呢？如果是，那么令a =，b =，命题就得到了证明。如果答案是否定的，就说明我们知道的无理数又多了一个，即。令a =，b =，根据指数定律，就可以得到：
答案是一个有理数。因此，无论是有理数还是无理数，我们都可以找到a、b，使得ab是有理数。
存在性证明这种证明方法通常很巧妙，但它有时也存在不尽如人意的地方，无法告诉你想要了解的所有信息。（如果你感到好奇，我可以告诉你是无理数，但这不属于本章讨论的范围。）
更能让人心满意足的证明方法是“构造性证明”（constructive proof），因为它告诉你的信息正好是你想要了解的信息。例如，我们可以证明所有的有理数a / b都是有尽或者循环小数（这是因为，随着除法运算的进行，b除过的数字必然会再次出现，并被b除）。但是，它的反命题是否正确？有尽小数必然是有理数，例如，0.123 58 =12 358 / 100 000。循环小数呢？例如，0.123 123 123…一定是有理数吗？答案是肯定的。下面这种巧妙的方法可以告诉我们有理数到底是什么。我们把这个神秘数字设为w，于是：
w = 0.123 123 123…
两边同时乘以1 000，上式就会变成：
1 000w = 123.123 123 123…
用第二个等式减去第一个等式，就会得到：
999w = 123
w = =
我们换另一个循环小数再试一试。这一次的循环小数并不是从小数点后第一位就开始循环，比如，如何将小数0.833 33…表示成分数形式呢？先令：
x = 0.833 33…
两边同时乘以100：
100x = 83.333 3…
再同时除以10：
10x = 8.333 3…
从100x中减去10x，小数点后面的所有项都抵消了：
90x = (83.333 3…) – (8.333 3…) = 75
x = =
运用构造性证明这种证明方法，我们可以证明当且仅当某个数字的小数形式是有尽或者循环小数时，该数才是有理数。如果某数的小数形式是不循环的无尽小数，例如：
v = 0.123 456 789 101 112 131 415…
这个数字就是无理数。
棋盘覆盖问题与归纳性证明
我们再回过头去，证明与正整数相关的一些定理。在本书第1章，通过观察：
我们先提出前n个奇数的和是n2的命题，然后着手证明这个命题。当时，我们使用的是巧妙的“组合性证明”（combinatorial proof）法，即通过两种方法统计棋盘的方格数，证明了这个命题的真实性。接下来，我们用一种无须巧妙构思的方法来证明这个命题。假设我告诉你（也许你本就深信不疑）前10个奇数的和1 + 3 + … + 19是102，即100，如果你表示同意，那么再加上第11个奇数（21），和毫无疑问是121，也就是112。换句话说，如果针对前10个奇数该命题为真，那么针对前11个奇数该命题同样为真。这就是“归纳证性明”（proof by induction）法的指导思想。在涉及n的证明时，我们通常会先证明命题在一开始的时候（通常是n = 1时）是正确的，然后证明如果n = k时命题成立，那么n = k + 1时它也成立。由此可证，在n取所有值时命题都成立。归纳性证明就像爬梯子：先证明你可以踏上梯子，然后证明如果你已经爬上了一级，就可以再向上爬一级。稍稍思考其中的道理，你就会相信自己可以爬上梯子的任意一级。
例如，对于前n个奇数的和这个命题，我们的目标是证明对于所有的n≥1，都有：
1 + 3 + 5 + … + (2n – 1) = n2
我们发现，第一个奇数1的和的确是12，因此当n = 1时，这个命题肯定是正确的。接下来，我们注意到，如果前k个奇数的和是k2，即：
1 + 3 + 5 + … + (2k – 1) = k2
再加上下一个奇数（2k + 1），就有：
1 + 3 + 5 + … + (2k – 1) + (2k + 1) = k2 + (2k + 1)
= (k + 1)2
也就是说，如果前k个奇数的和是k2，那么前k + 1个奇数的和一定是(k + 1)2。既然n = 1时命题成立，由上述证明过程可知，n取所有值时该命题也成立。
归纳性证明法是一个功能强大的证明方法。本书讨论的第一个问题是前n个数字的和：
1 + 2 + 3 + … + n =
当n = 1时，该命题肯定是正确的，因为1 = （1×2） / 2。如果我们假设对于某个数字k，命题
1 + 2 + 3 + … + k =
是正确的，在上式基础上再加上 (k + 1)，就会得到：
1 + 2 + 3 + … + k + (k + 1) = + (k + 1)
= (k + 1) (+ 1)
=
这是用 k + 1代替n时的求和公式。因此，如果n = k（k是任意正数）时公式成立，那么当n = k + 1时，该公式同样成立。由此可证，当n取所有正值时，公式都成立。
在本章以及后续章节中，我们将见到更多的归纳性证明实例。为了帮助大家加深印象，我在这里为大家送上“数学音乐家”戴恩·坎普（Dane Camp）和拉里·莱塞（Larry Lesser）创作的一首歌，这首歌采用了美国民谣歌手鲍勃·迪伦（Bob Dylan）的作品《答案在风中飘荡》（Blowing in the Wind）的旋律。
如何才能证明n取所有值时
命题都成立？
既然无法一一验证
盲目尝试又有何益！
面临如此困境，
能否找到锦囊妙计？
答案啊，我的朋友，是要学会归纳性证明，
答案是要学会归纳性证明！
首先研究开始时的情况
证明命题没有问题，
然后假设n = k时命题为真
并证明n = k + 1时仍然成立！
至此问题迎刃而解
告诉我你是否感到满意？
既然已经说了n次，说n + 1次又何妨
答案是要学会归纳性证明！
延伸阅读
我们在本书第5章讨论了斐波那契数列数字间的几种相互关系。下面，我们就用归纳性证明法验证其中几个等式。
定理：对于n≥1，
F1 + F2 + … + Fn = Fn+2–1
证明：当n = 1时，上式为 F1 = F3–1，即1 = 2–1，这显然是成立的。假设当n = k时，命题也成立，那么：
F1 + F2 + … + Fk = Fk+2–1
在等式两边同时加上下一个数字Fk+1，就会得到
F1 + F2 + … + Fk + Fk+1 = Fk+1 + Fk+2 – 1
= Fk+3 – 1
证明完毕。 □
斐波那契数列的平方和等式的证明同样简单。
定理：对于n≥1，
证明：当n = 1时，上式为 = F1 F2，这显然是成立的，因为F2 = F1 =1。假设当n = k时定理也成立，那么：
在等式两边同时加上，就会得到：
证明完毕。 □
我们在本书第1章发现，“三次方的和就是和的二次方”，例如：
13 = 12
13 + 23 = (1 + 2)2
13 + 23 + 33 = (1 + 2 + 3)2
13 + 23 + 33 + 43 = (1 + 2 + 3 + 4)2
但是，我们当时无法证明。有了归纳性证明法之后，就可以轻松完成证明工作了。这个一般性规律是：对于n ≥1，
13 + 23 + 33 + … + n3 = (1 + 2 + 3 + … + n)2
由于我们已经知道1 + 2 + … + n =，因此我们可以证明下面这条等价定理。
定理：对于n≥1，
13 + 23 + 33 + … + n3 =
证明：当n = 1时，命题13 = (12×22) /4成立。如果n = k时定理也成立，就有：
13 + 23 + 33 + … + k3 =
两边同时加上 (k + 1)3，就会得到：
证明完毕。 □
延伸阅读
下面是立方和公式的几何证明。
我们用两种方法计算上图的面积，然后进行比较。一方面，这是一个正方形，它的边长是1 + 2 + 3 + 4 + 5，因此它的面积是 (1 + 2 + 3 + 4 + 5)2。
另一方面，我们从左上角开始，沿对角线方向观察，就会发现这个正方形是由1个1×1的正方形，2个2×2的正方形（其中一个正方形被分割成两半），3个3×3的正方形，4个4×4的正方形（其中一个正方形被分割成两半）和5个5×5的正方形构成的，因此它的面积等于：
(1×12) + (2×22) + (3×32) + (4×42) + (5×52)
= 13 + 23 + 33 + 43 + 53
由于计算的面积相等，所以：
13 + 23 + 33 + 43 + 53 = (1 + 2 + 3 + 4 + 5)2
利用相同的方法可以画出边长为1 + 2 + … + n的正方形，并证明下面这个等式成立：
13 + 23 + 33 + … + n3 = (1 + 2 + 3 + … + n)2
归纳性证明法不仅限于证明求和问题。只要我们可以用“较小”问题（n = k时）的答案来推导出“较大”问题（n = k + 1时）的答案，归纳性证明法往往就有用武之地。下面向大家介绍一个让我深感满意的归纳性证明实例。问题与本章开头讨论的棋盘覆盖问题有关，但不是证明不可能性，而是证明某种可能性。而且，我们使用的不是双方块，而是L形的三方块。
因为64不是3的倍数，全部使用三方块的话是无法覆盖8×8棋盘的。但是，如果在棋盘上放一个1×1方块，那么无论这个1×1方块放在棋盘的什么位置，我们都可以用三方块覆盖棋盘的剩余面积。而且，这个命题不仅在棋盘的规格是8×8时为真，对于2×2、4×4、16×16的棋盘，该命题同样成立。
定理：对于所有的n≥1，都可以用三方块和一个1×1方块完全覆盖规格为2n×2n的棋盘，而且1×1方块可以放置在棋盘的任何位置上。
证明：当n = 1时，定理成立，因为任何一个2×2的棋盘都可以用一个三方块和一个1×1方块来覆盖，而且1×1方块可以摆放在棋盘的任何位置上。接下来，假设当n = k时（即棋盘大小为2k×2k时）定理也成立。我们需要完成的任务是证明在棋盘大小为2k+1×2k+1时，该定理仍然成立。如下图所示，将1×1方块摆放在棋盘的任意位置上，然后将棋盘分成四等分。
用三方块覆盖棋盘
由于放有1×1方块的那一等分的大小为2k×2k，因此，它可以被三方块完全覆盖（根据假设，当n = k时，定理成立）。接下来，我们在棋盘的中心位置放一个三方块，让它与其余三个等分相交。这三个等分的大小分别为2k×2k，且其中有一个1×1方格已经被覆盖了，所以用三方块可以完全覆盖住它们。因此，在棋盘大小为2k+1×2k+1时，定理仍然成立。
本节最后证明的等式有很多重要应用，我们将用归纳证明法和其他几种不同方法予以证明。这个令人感兴趣的问题是：如果从20 = 1开始，将2的前n次方相加，和是多少？下面是排在前几位的2的幂次方：
1，2，4，8，16，32，64，128，256，512，1 024…
将它们加到一起，就会得到：
大家看出其中的规律了吗？所有的和都比2的更高次幂小1。
定理：对于n≥1，
1 + 2 + 4 + 8 +… + 2n–1 = 2n – 1
证明：如上所述，当n = 1时（以及n = 2，3，4或5时）定理成立。假设当n = k时定理成立，就有：
1 + 2 + 4 + 8 +… + 2k–1 = 2k–1
在等式两边同时加上更高一阶的2次幂，即2k，就会得到：
1 + 2 + 4 + 8 +… + 2k–1 + 2k = (2k – 1) + 2k
= 2×2k–1
= 2k+1–1 □
在第4章和第5章，我们通过运用不同方法回答同一个计数问题，证明了多种相互关系。看了下面的内容，你也许会认为组合性证明法真的非常重要！
问题：从n名曲棍球球员（球衣号码为1~n）中选择若干名球员加入体育联合会代表团，要求代表团中至少包含1名球员，一共有多少种选择方案？
第一种解法：每名球员都有参加或者不参加代表团这两个选择，因此选择方案应该是2n种。但所有球员均不参加的情况是不允许的，还需要减去1。所以，一共有2n–1种选择方案。
第二种解法：考虑参加者的球衣号码最大的情况。如果1是最大号码，选择方案只有1种；如果2是最大号码，选择方案有2种（2号球员可能独自参加，也可能和1号球员一起参加）；3是最大号码时，选择方案有4种（3号球员必须参加，1号和2号球员各有两个选择）。以此类推，n是最大球衣号码时，选择方案有2n–1种，因为n号球员必须参加，1号至n – 1号球员各有两个选择（参加和不参加）。加到一起，一共有1 + 2 + 4 + … + 2n–1种选择方案。
由于这两种解法都是正确的，因此必然会得出相同的答案。也就是说，1 + 2 + 4 + … + 2n–1 = 2n – 1。
不过，最简单的证明方法可能是单纯的代数运算，这让我们不禁回想起把循环小数表示成分数形式的那个方法。
代数证明：
令S = 1 + 2 + 4 + 8 + … + 2n–1
两边同时乘以2，就会得到：
2S = 2 + 4 + 8 + … + 2n–1 + 2n
用第二个等式减去第一个等式，除了第一个等式的第一项和第二个等式的最后一项外，其余各项都被消掉了，因此：
S = 2S–S = 2n – 1 □
我们刚刚证明的定理其实是二进制表示方法的关键内容。二进制表示方法非常重要，计算机就是利用它来存储和处理数字的。二进制表示方法的理论依据是，所有数字都可以表示成2的不同次幂相加的唯一形式。例如：
83 = 64 + 16 + 2 + 1
在把十进制转化成二进制时，每个2的幂次方用数字1表示，缺位的幂次方用数字0表示。在这个例子中，83 = (1×64) + (0×32) + (1×16) + (0×8) + (0×4) + (1×2) + (1×1)。因此，83的二进制表示就是：
83 = (1010011)2
我们怎么知道所有正数都可以这样表示呢？假设从1到99的所有数字都可以表示成2的不同次幂相加的唯一形式，我们怎么知道100是否可以表示成这种唯一形式呢？首先，我们在100以内找到2的最高次幂，这个数字应该是64。（64是必不可少的吗？是的，因为即使我们把1、2、4、8、16、32全部选上，它们的和也只有63。）选好64之后，我们还需要用2的不同次幂相加得到36，才能凑成100。根据假设，我们可以用2的不同次幂相加的唯一形式表示36，因此，100也必然有唯一的二进制表示。［我们怎么表示36呢？先找到2的最高次幂，然后得到36 = 32 + 4。因此，100 = 64 + 32 + 4的二进制表示就是 (1100100)2。］我们可以将这个过程推而广之，从而证明所有的正数都有唯一的二进制表示。
谜一般的质数
上文中我们证明了所有的正整数都可以表示成2的不同次幂相加的唯一形式。从某种意义上讲，你可以把2的幂次方看作建筑材料，通过加法运算，搭建起正整数这座大厦。接下来，我们将会看到质数通过乘法运算扮演了一个类似的角色：所有正整数都可以表示成质数乘积的唯一形式。2的幂次方很容易确认，不会给数学界带来多少意外发现。质数则不同，它们复杂得多，还有很多未解之谜。
质数是只有1和它本身这两个正约数的正整数。排在前几位的质数是：
2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53…
1只有一个约数，就是它本身，因此1不是质数。（人们认为1不是质数，还有一个更重要的原因，稍后揭晓。）请注意，2是唯一一个既是偶数又是质数的数字。因此，有人可能会认为2是最奇怪的质数。
有3个或3个以上约数的正整数叫作“合数”，因为它们可以被分解成多个因数相乘的形式。排在前几位的合数是：
4，6，8，9，10，12，14，15，16，18，20，21，22，24，25，26，27，28，30…
例如，4有3个约数：1，2和4。6有4个约数：1，2，3和6。注意，1既不是质数，也不是合数。数学界把1称为“计数单位”（unit），它是所有整数的约数。
所有合数都可以表示成质数乘积的形式。比如，120 = 6×20，由于6和20是合数，可以表示成质数乘积的形式，即6 = 2×3，20 = 2×2×5。因此：
120 = 2×2×2×3×5 = 23×31×51
有意思的是，无论我们以何种方式开始，质因数分解的最后结果都是一样的。这就是“唯一分解定理”（unique factorization theorem）得出的结论。唯一分解定理亦称“算术基本定理”（fundamental theorem of arithmetic），指任何一个大于1的正整数都能分解成有限个质数的乘积的唯一形式。
顺便告诉大家，我们认为1不是质数的真正原因就在于这条定理。例如，12可以分解成2×2×3，也可以分解成1×1×2×2×3，如果把1视为质数，那么质因数分解就无法得出唯一的结果。
一旦知道某个数字如何分解，就可以了解到关于这个数字的很多信息。小时候，我最喜欢的数字是9，但在成长的过程中，我最喜欢的数字也在不断“成长”，而且越来越复杂（例如，π = 3.141 59…，φ= 1.618…，e= 2.718 28…，以及没有小数表达式的i，等等。我们将在本书第10章讨论这些数字。）在接触无理数之前，我一度非常喜欢2 520这个数字，因为在可以被从1到10的所有数字整除的数中，它是最小的一个。它的质因数分解表达式是：
2 520 = 23×32×51×71
只要知道某个数字的质因数分解结果，就可以立刻说出它有多少个正约数。例如，2 520的约数必然是2a×3b×5c×7d 的形式，其中a是0、1、2、3（4种可能），b是0、1、2（3种可能），c是0、1（2种可能），d是0、1（2种可能）。因此，根据乘法法则，2 520有4×3×2×2 = 48个正约数。
延伸阅读
算术基本定理的证明需要利用质数的某个属性（所有数论教科书都会在第1章证明这个属性）：如果p是质数，而且是两个或两个以上数字乘积的一个约数，那么p至少是其中一个乘数的约数。例如，
999 999 = 333×3 003
999 999是11的倍数，因此11必然是333或者3 003的约数。（的确如此，因为3 003 = 11×273。）然而，有的合数并不具有这个属性。例如，60 = 6×10是4的倍数，但4既不是6的约数，也不是10的约数。
为了证明质因数分解的唯一性，我们先做一个相反的假设：某个数字的质因数分解结果不止一个。假设N是有两个质因数分解结果的最小数字，例如：
p1p2…pr = N = q1q2…qs
其中，所有的pi和qj项都是质数。因为N肯定是p1的倍数，所以p1肯定是某个qj项的约数。为了方便起见，我们假定p1是q1的约数。由于q1是质数，因此肯定有q1 = p1。把上面的等式除以p1，就会得到：
p2…pr = = q2…qs
这说明也有两个质因数分解结果，但我们假设N才是有两个质因数分解结果的最小数字，因此两者是矛盾的。 □
延伸阅读
在有的数字系统中，并不是所有的数字都有唯一的质因数分解结果。例如，火星人长了两个脑袋，因此他们只使用偶数：
2，4，6，8，10，12，14，16，18，20，22，24，26，28，30…
在火星人的数字系统中，6和10被视为质数，因为它们不能分解成更小的偶数。在这种数字系统中，质数和合数严格地交替出现。4的所有倍数都是合数（因为4k = 2×2k），其他的所有偶数（包括6、10、14、18等）都是质数，因为它们无法分解成两个更小的偶数。但是，我们来看180这个数字：
6×30 = 180 = 10×18
在火星人的数字系统中，180有两种不同的质因数分解结果，这证明火星数字系统中的质因数分解不具有唯一性。
1~100中有25个质数，101~200中有21个质数，210~300中有16个质数。随着数字越来越大，质数出现的频率越来越低。（但是，这种减少的趋势无法预测。例如，在301~400和401~500中，分别有16和17个质数，而1 000 001~1 000 100中只有6个质数。）这是有道理的，因为大数有多个约数的可能性更大。
我们可以证明，有时候连续100个数字之中也没有一个质数。如果愿意花时间寻找，你甚至可以发现连续1 000或者100万个数字中也没有一个质数。你不相信的话，我可以立刻为你提供连续99个合数（尽管在这之前就已经出现过同类现象了）。观察下面这99个连续数字。
100! + 2，100! + 3，100! + 4，…，100! + 100
因为100! = 100×99×98×…×3×2×1，所以它肯定可以被2~100的所有数字整除。接下来，我们以100! + 53为例。由于53是100!的约数，因此它肯定也是100! + 53的约数。同理可证，对于所有的2 ≤ k ≤ 100，100! + k都必然是k的倍数，也就是说，它们都是合数。
延伸阅读
注意，我们在上述证明过程中根本没有提到100! + 1是不是质数的问题，但我们其实是可以做出判断的。在这里，我们要应用一个非常棒的定理——“威尔逊定理”（Wilson’s theorem）。这条定理指出，当且仅当 (n－1)! + 1是n的倍数时，n为质数。用几个比较小的数字加以检验，就会发现确实如此。1! + 1 = 2是2的倍数，2! + 1 = 3是3的倍数，3! + 1 = 7不是4的倍数，4! + 1 = 25是5的倍数，5! + 1 = 121不是6的倍数，6! + 1 = 721是7的倍数，等等。由于101是质数，根据威尔逊定理，100! + 1是101的倍数，因此它是合数。也就是说，从100!至100! + 100的101个连续数字都是合数。
既然随着数字越来越大，质数的出现频率越来越低，人们自然会想，当数字大到一定程度时，会不会就没有质数了呢？两千多年前，欧几里得告诉我们并非如此。但不能因为他是欧几里得我们就相信他的话，我们还是尽情享受证明的乐趣吧。
定理：质数有无穷多个。
证明：我们反过来假设质数的个数是有限的。既然质数的个数有限，就必然存在最大的质数，我们将这个数字记作P。现在，观察P! + 1这个数字。由于从2到P的所有数字都可以整除P!，因此它们都不可能整除P! + 1。这样一来，P! + 1就必然有一个大于P的约数为质数，而我们假设P是最大的质数，两者是矛盾的！ □
尽管我们永远也无法找到一个最大的质数，但这并不能阻止数学家和计算机科学家寻找更大质数的努力。在我创作本书的时候，已知的最大质数有17 425 170位数。把这个数字写下来，可以写成大约100本跟本书大小、厚度差不多的书。不过，我们也可以把它表示为：
257 885 161– 1
我们之所以能把它以如此简单的形式表达出来，是因为我们可以准确地判断出2n – 1或2n + 1是不是质数。
延伸阅读
根据伟大的数学家皮埃尔·德·费马（Pierre de Fermat）的证明，如果p是奇质数，那么2p – 1 – 1必然是p的倍数。我们用前几个奇质数来验证一下。取质数3、5、7、11，我们发现： 22 – 1 = 3是3的倍数，24 – 1 = 15是5的倍数，26 – 1 = 63是7的倍数，210–1 = 1 023是11的倍数。对于合数，我们知道，如果n是偶数，那么2n–1–1必然是奇数，不可能是n的倍数。我们再用前几个奇合数9、15和21验证一下，结果发现：28 – 1 = 255不是9的倍数，214 – 1 = 16 383不是15的倍数，220–1 = 1 048 575不是21的倍数（就连3的倍数都不是）。根据费马的这条定理，如果知道2N–1 – 1不是数字N的倍数，那么我们甚至不需要找出N的约数，就可以根据这个属性确定N不是质数！但是，这条定理反过来却不成立。确实有些合数从某些方面来看像质数（这类数字被称为“伪质数”）。最小的伪质数是341 = 11×31，它就具备2340 – 1是341的倍数这个属性。伪质数有无穷多个，尽管它们出现的频率比较低，但好在我们已经找到了甄别办法。
质数有很多应用，尤其在计算机科学领域。在几乎所有加密算法（包括为互联网金融交易保驾护航的公钥加密系统）中，质数都发挥了核心作用。很多加密算法都利用了这样一个事实：我们可以很快地判断出某个数字是否为质数，但我们还没有找到快速分解大数字的方法。例如，如果我随机选取两个1 000位的质数相乘，答案是一个2 000位数，任何人、任何计算机（除非量子计算机被人们成功地制造出来）几乎都不可能根据这个乘积找出原来的两个质数。人们认为，基于人类无法分解大数字这个特点编制而成的密码（例如公钥加密系统）具有很高的安全性。
几千年来，质数之美一直让人类魂牵梦绕。古希腊人说，如果某个数字等于所有真约数（除自身以外的约数）之和，这个数字就是“完全数”（perfect number）。例如，6的真约数是1、2、3，它们的和正好是6，因此6是一个完全数。第二个完全数是28，它的真约数1、2、4、7、14的和正好是28。接下来的两个完全数是496和8 128。完全数有什么规律呢？不妨考察它们的质因数分解结果。
6 = 2×3
28 = 4×7
496 = 16×31
8 128 = 64×127
看出其中的规律了吗？被乘数是2的幂次方，乘数是比被乘数的2倍小1的质数。（因此，在上述算式中我们没有看到8×15或者32×63，因为15和63都不是质数。）我们可以用下面这条定理对这个规律加以概括。
定理：如果2n–1是质数，那么2n–1×(2n–1)是完全数。
延伸阅读
证明：令p = 2n–1，p是质数，我们的目标是证明2n–1p是完全数。2n–1p的真约数有哪些呢？不含p的约数只有1，2，4，8，…，2n–1，它们的和为2n – 1 = p。其他约数（不包括2n–1p）则都包含p，这些约数的和为 p(1 + 2 + 4 + 8 + … + 2n–2) = p (2n–1 – 1)。因此，所有真约数的和为:
p + p(2n–1 – 1) = p［1 + (2n–1 – 1)］ = 2n–1p
证明完毕。 □
伟大的数学家莱昂哈德·欧拉（Leonhard Euler，1707—1783）证明了所有完全数都是偶数。在我创作本书的时候，人们已经发现了48个完全数，而且全部是偶数。是否存在完全奇数呢？目前，还没有人知道这个问题的答案。有人认为，如果完全奇数真的存在，它们的位数将超过300。不过，还没有人证明完全奇数肯定不存在。
关于质数，有很多表述简单但却悬而未决的问题。前面已经说过，关于斐波那契数列中的质数是否有无穷多个的问题，现在还没有答案。［已经有人证明斐波那契数列中只有两个完全平方数（1和144）和两个完全立方数（1和8）。］还有一个未解难题被称为“哥德巴赫猜想”（Goldbach’s conjecture），即所有大于2的偶数都是两个质数之和。目前没有人可以证明这个猜想，但是有人证明，如果有反例存在，那么这个数字至少是19位数。［不久前，人们在一个比较相似的问题上取得了突破。2013年，法国数学家哈罗德·贺夫高特（Harald Helfgott）证明了所有大于7的奇数都至多是三个奇质数之和。］最后再介绍一个未解难题。我们把差为2的两个质数定义为“孪生质数”（twin primes）。排在前面的几对孪生质数分别是3和5，5和7，11和13，17和19，29和31，等等。你知道为什么3、5、7是唯一的“质数三胞胎”吗？尽管已经有人证明末位数是1（或者3、7、9）的质数有无穷多个［古斯塔夫·狄利克雷（Gustav Dirichlet）提出的一个命题的特例］，但孪生质数是否有无穷多对的问题仍未找到答案。
在结束本章之前，我们来看一个有点儿可疑的证明，但是我希望大家能相信这个命题。
命题：所有正整数都值得关注！
证明：人们一致认为前几个正整数值得关注。例如，1是第一个正整数，2是第一个偶数，3是第一个奇数，4是唯一一个名副其实的数字（它的英文单词“FOUR”正好有4个字母）。我们反过来假设有的正整数不值得关注，那么必然有第一个不值得关注的正整数，我们把它记作N。但是，作为第一个不值得关注的正整数，N必然因此引起关注！因此，不值得我们关注的正整数是不存在的！