著 陈 开
责任编辑 李 宁
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书主要面向学有余力的小学高年级学生、中学生以及其他数学爱好者，通过有趣的数学故事探究数学之美。书中的多篇故事涵盖了中小学数学教育课程的主要分支，同时也是数学竞赛中常见的4个主要类别：数论、代数、几何和组合数学。一方面，本书再现了多个与数学原理相关的历史、文化、科学和艺术场景，展现了数学之美以及数学和人文科学的统一；另一方面，本书也可以帮助读者加深对课内知识点的理解，提供的例题及讲解可以帮助正在准备数学竞赛的读者，使他们能举一反三、开拓思维。
本书可以作为中小学生的课外读物，也可作为数学爱好者进行数学思维训练和补充数学知识的资料。
你没看错，这是那本《课堂上来不及思考的数学》的姊妹篇。
和上一本图书一样，本书既不是教材，也不是竞赛专用书。本书内容的取材和灵感多来源于我和女儿关于数学问题的讨论，也可以算是我写给女儿的课堂之外的数学书。因此，让数学变得生动有趣，让大家在课外仍然能对数学保持持续的兴趣，仍然是本书写作的目的。你依然可以在本书中看到生动的故事、活泼的文字、通俗的比喻和现实中的示例，由此你的思维可以从课内知识点延伸到课外的应用，乃至其他学科之中，从而做到举一反三和融会贯通。
不过作为姊妹篇，本书涉及了一些更深的内容，有更多的公式和推导，以及更有挑战性的例题。你需要做的，是在下午茶时间里，准备一颗愿意挑战的心、一支笔、若干张草稿纸，从在课本中学到的内容出发，慢慢延伸到一些进阶的知识点，理解公式及其推导过程中的原理和逻辑，再努力去战胜书中的这些挑战。
在本书中，你仍将读到一些有趣的故事，有对数字有着癖好的特斯拉，有传说中可以心算出士兵人数的韩信，有电视剧《老友记》中的路痴乔伊，还有曾经纵横驰骋在欧洲大陆上的拿破仑。在故事中，你还可以了解到日本人常用来许愿的绘马，麻省理工学院学生们进行的叠纸挑战，韦达定理的发现者也是一个破译专家，19世纪出版的时尚杂志居然定期刊登数学问题，等等。这些故事将带领你去品味中国古代数学中的巧妙算法，去感受中西方文化中蕴含的数学思想，以及数学向自然、生物、文学、社会等其他学科领域的渗透和它们之间的交融。
本书分为“数学的源泉”“书写的几何”“图形的代数”和“严格的完美”4章。这4章的内容大致涵盖了中小学数学教育课程内容的主要分支，同时也是数学竞赛中的4个主要类别。在第1章中，你将了解到关于整数的一些进阶性质。包括数的整除、同余运算、质因数的分布以及整系数不定方程。在第2章中，你会接触到二项式展开、函数的不动点、不等式的性质等内容，其中不等式的齐次化和归一化对你来说可能具有一定的挑战性。在第3章中，你将了解到相似三角形和全等三角形、托勒密定理、圆幂定理、黄金分割，以及分形和分形的维度等，其中，几何的复数表示形式属于进阶内容。第4章是一个“大杂烩”，在这里你将学习到数学归纳法、贝叶斯概率、平衡不完全区组设计等方面的知识，后者需要你花更多的时间来推算和理解。
本书可以作为课外阅读、数学思维训练和数学知识科普的补充读物，主要面向学有余力的小学高年级学生、中学生以及其他数学爱好者。对于阅读目的为扩大知识面的读者，你们可以更多地关注本书中涉及的数学的历史性和多元性，即数学背后深厚的人文历史、数学家们鲜明的人格特点，以及数学原理向其他学科的延伸和应用等方面。对于阅读目的为加深理解课内知识点的读者，你们可以侧重于本书中关于知识点的讲解和延伸内容，在加深理解的基础上做到有所拓展。对于正在准备数学竞赛的读者来说，你们可以把重点放在本书中的例题上，尤其是一些进阶的、本身就来自于竞赛的例题，做到理解到位和举一反三。读者朋友们也可以通过邮箱wiskclub.be@gmail.com与我联系。
在上一本书中，我曾在前言中介绍过我未满16岁的女儿在第一次参加国际数学奥林匹克竞赛时获得了一块宝贵的铜牌。2021年12月初，我的女儿又接受了剑桥大学数学专业的入学面试。在近3小时的面试中，她尝试解答了若干数学问题，并在和面试官的互动中讲解且拓展了自己的解题思路。这些问题部分基于中学学过的内容，部分涉及微积分、统计等进阶内容。对我而言，我很高兴自己平日对女儿的数学思维训练可以帮助她自如地应付专业人士的面试提问；而对她来说，这是她实现自己梦想所必须经历的一个挑战。
相信本书的大小读者朋友们都有着自己的梦想，不论是增加知识、拓展思路，是提高成绩、顺利升学，还是突破自我、竞赛成功，要实现这些梦想，都离不开自身的不断努力和付出。希望你们都能做到开卷有益，提升自己的能力，战胜一个又一个的挑战，最终实现自己的梦想！
书名：课堂上来不及思考的数学2:挑战思维极限
ISBN：978-7-115-58737-4
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
闵可夫斯基说，整数是所有数学的源泉。发明家特斯拉为什么一辈子都钟情于 3 的整倍数？在吉尼斯世界纪录中，一张足够长的厕纸最多被成功对折了多少次？悬赏一百万美元大奖的问题为什么无人能解决？传说中“韩信点兵、多多益善”的故事蕴含了什么数学原理？通过这些小故事，你将接触到数论中更深一层的内容：数的整除、同余运算、完全平方数的性质、整数中质因数的分布、整系数不定方程的有解条件，以及线性同余方程组的求解方法。
“2020年3月20日，是这一年的春分，也是这个世纪的第一个超级整除日。20200320可以同时被1、2、3、4、5、6、7、8、9、10整除。”
在纽约曼哈顿的纽约客酒店，一个瘦高个男人正坐在餐厅的一角，他有着黝黑、中分的头发，宽宽的额头下面是一双深邃的眼睛，此时他正盯着自己手边的一叠餐巾纸。
“没错，特斯拉先生，18条，我仔细数过了。”侍者站在一旁赔着笑脸。
这个被称作“特斯拉先生”的男人仔细地擦拭着他的盘子，这应该是晚餐前的最后一个盘子了。没错，他已经擦拭完3副刀叉和两个盘子，只需做完这最后的“功课”，侍者就可以开始上头盘了。
尼古拉·特斯拉（Nikola Tesla）在这家酒店的3327号房间已经住了快10年（图1.1.1），餐厅里的每一个侍者都深知这个老头的怪毛病，他总是要摆上3套餐具，饭前用18张餐巾纸把所有餐具都擦拭一遍。不过，他们不知道这个怪老头是一个伟大的发明家，他改进了交流电发电机、电动机和远程控制系统的设计。特斯拉后来被人们认为是电力商业化的先驱，他的名字在2003年被埃隆·马斯克（Elon Musk）用来命名其电动汽车及能源公司。
图1.1.1 特斯拉住过的房间的展示板
因为卓越的发明以及在现代电气行业中的先驱地位，特斯拉对数字3的偏爱被后来的很多人神化。传说特斯拉曾经说过，“如果你了解数字3、6和9的美妙之处，你就拥有通往宇宙真相的钥匙”；传说他曾经通过计算，得出行星的运行轨迹和交汇点与数字3、6和9有关。不过如果进行认真考证，人们很难在任何传记或者文献中发现支持上述传说的证据。
特斯拉先生，这位电机工程学的先驱，也许只是单纯地对数字3及其倍数有着“强迫症”。比如他去一个陌生的所在，可能会在进门前先绕着建筑物转3圈；他在纽约客酒店选择33层的27号房间；他在餐前用18条餐巾纸擦拭3套餐具……人们试图把这个天才的强迫症归于玄学——他在用3、6和9去研究宇宙的本质。
和玄学相比，数学似乎更加接近宇宙的本质。6、9、18、27和33都是3的倍数，6、9、18、27和33都能被3整除，就这么简单。
整除，是自然数乃至整数的一个基本特性。当整数a除以非零整数b，商为整数、余数为0时，我们就说a能被b整除（或者说b能整除a），记作b|a。同时，a被称为b的倍数，b被称为a的约数或因数（因子）。
整除有以下基本性质。
（1）若a | b，a | c，则a | （b±c）。
（2）若a | b，则对任意整数c，a | （bc）。
（3）若a | b，b | a，则|a| = |b|。
（4）若a能同时被b与c整除，并且b与c互质，那么a一定能被积bc整除。反过来也成立，若a能被积bc整除，并且b与c互质，那么a同时能被b与c整除。
先看一道简单的例题：一个三位自然数正好等于它各数位数字之和的18倍，则这个三位自然数是（A）999；（B）476；（C）387；（D）162。
答案为D。这个三位自然数能够被18整除，因为2和9互质，所以这个三位自然数分别能够被2和9整除，A和C是奇数，B不能被9整除，所以答案是D。
在上题中，除了运用整除的基本性质，还需要快速判断出哪个数可以被9整除。对于常见的除数，我们可以总结出一些规律。
对于除数为2或5的情况，因为十位数及以上的部分可以被10整除，也肯定可以被2或5整除，所以只需要考虑个位数，如果个位数为偶数则可以被2整除，个位数为0或者5则可以被5整除。
类似地，这个规律可以用于除数为4或25、8或125的情况。因为百位数及以上的部分可以被100整除，所以对于除数为4或25的情况，只需考虑截去百位数及以上部分所剩余的那个两位数是否可以被4或者25整除。对于除数为8或125的情况，只需考虑截去千位数及以上部分所剩余的那个三位数是否可以被8或者125整除。
对于除数为3或9的情况，若有an…ai…a2a1这样一个n位数，右起第i位上的数字为ai，这个n位数可以写成
，即
，其中(10i−1−1)为连续i −1个9组成的整数，一定可以被3或9整除，所以我们只需考虑
，即组成n位数的所有数字之和，如果它可以被3或9整除，那么这个n位数就可以被3或9整除。
对于除数为11的情况，可以把这个整数的奇数位和偶数位上的数字分别加起来，然后将两个和相减，考虑得出的这个差是否能被11整除。我们用a2i+1表示右起奇数位的数字，b2i+2表示右起偶数位的数字，i是大于等于0的整数，那么这个整数可以写成
因为第1项是11的倍数，所以只需考虑第2项
能否被11整除。再由(99 + 1)i的二项展开式可知，前i项都是99的倍数，也是11的倍数，所以只需考虑第i + 1项
能否被11整除即可。
类似地，对于除数x，利用某个接近10的幂的x的倍数进行截取补余的方法叫作截余法。这种方法可以用于除数为7、13、17、19等的情况。
比如除数为17，因为51可以被17整除，所以可以截掉个位数，将剩下的数减去原个位数的5倍，考虑这个差是否可以被17整除。设原数为10a + b，变形为10 (a − 5b) + 51b，显然，如果a − 5b是17的倍数，那么原数即17的倍数。例如，374去掉个位数得37，减去4的5倍，得到17，可以被17整除，因此374是17的倍数。
又因为102也可以被17整除，所以也可以截掉末两位数，将剩下的数的2倍减去原末两位数，考虑这个差是否可以被17整除。设原数为100a + b，变形为102a + (b − 2a)，显然，如果b − 2a （或者2a − b）是17的倍数，那么原数即17的倍数。还是以374为例，去掉末两位数得3，其2倍减去74，得到−68，−68是17的倍数，所以374是17的倍数。
对于除数为7、11或13的情况，还有一种方法。将整数在末三位和末四位之间分开，考虑新得到的两个数之差是否可以被7、11或13整除。设该n位整数为1000a + b，其中b为末三位数，a为将该整数分开后得到的前n − 3位数，易知1000a + b =1001a + (b − a)，因为1001=7×11×13，所以只需考虑b − a是否能被7、11或13整除即可。以4693为例，a等于4，b等于693，所以b − a等于689，689是13的倍数，不是7或者11的倍数，因此4693是13的倍数，而不是7或者11的倍数。
数学博主“Matrix67”曾经提到过一个判断是否能被7整除的简易方法，其实就是上述方法的变形。以86415为例，首先将这个数从右到左以每两个数字为一组划分开，86415就变成了8 （64） （15）；接着，从左到右，每一组数字对7取余，对奇数组取负余数，对偶数组取正余数；最后，忽略正负号后将余数从右到左组成一个新的数字616（图1.1.2）。
图1.1.2 判断86415是否为7的倍数
对616继续进行以上操作，得到21。显然21可以被7整除，因此86415也可以被7整除。“Matrix67”提到的这种方法同样也可以用于除数是11或13的情况，本质上同样利用了7、11和13可以整除1001这个事实。
我们来看一道复杂一些的例题：设a、b、c为3个互不相等的正整数，试证明a3b − ab3、b3c − bc3、c3a − ca3这3个数中至少有一个数可以被10整除。
因为2×5=10，所以我们只需证明3个数中至少有一个数能够同时被2和5整除。将3个数进行因式分解，得到
a3b − ab3 = ab(a2 − b2) = ab(a + b)(a − b)
同理有
b3c − bc3 = bc(b + c)(b − c)
c3a − ca3 = ca(c+a)(c − a)
考虑a和b的奇偶性。如果a和b其中有一个偶数，那么a3b − ab3显然是偶数；如果a和b都是奇数，那么a + b是偶数，a3b − ab3仍然是偶数。依此类推，这3个数都是偶数。
再考虑a、b和c是否能被5整除。如果a、b和c中至少有1个是5的倍数，那么3个数中至少有一个能被5整除，原题得证。如果a、b和c都不是5的倍数，那么a2、b2和c2的个位数必然是1、4、6和9其中的一个，从这4个数中任取3个（取的3个数可重复），必有2个个位数的和或者差为0或者5，因此a2 − b2、b2 − c2、c2 − a2之中至少有一个能够被5整除，原题得证。
我们回到整除的判断，截余法也好，数学博主“Matrix67”提出的方法也好，都是将原数对除数及其倍数进行加减操作，再考虑得到的新数是否能够被除数整除。这种用除数及其倍数进行加减的操作，也被称为同余运算。对除数来说，同余运算得到的结果和原数的余数相同，或者说和原数同余。
我们用a mod m表示a对除数m取余数，用a≡b(mod m)表示a和b对除数m同余。同余也有一些基本性质。
（1）若a≡b(mod m)，b≡c(mod m)，则有a≡c(mod m)。
（2）若a≡b(mod m)，则有(a + km)≡b(mod m)，k为整数。
（3）若a≡b(mod m)，则有ka≡kb(mod m)，k为正整数。
（4）若a≡b(mod m)，c≡d(mod m)，则有a±c≡b±d(mod m)。
（5）(a + b)mod m=(a mod m + b mod m)mod m。
（6）(ab)mod m=(a mod m×b mod m)mod m。
（7）若a≡b(mod m)，c≡d(mod m)，则有ac≡bd(mod m)。
（8）ab mod m = (a mod m)b mod m。
灵活地运用上述定理，我们可以简化求余数的过程。
以求437×309×1993被7除的余数为例，437≡3(mod 7)，309≡1(mod 7)，1993≡5(mod 7)，所以437×309×1993≡3×1×5≡15≡1(mod 7)。
还可以注意到，如果两个数a和b对m同余，那么它们的差就可以被m整除。
以下题为例：设n是大于1的整数，它除210、286和381的余数相同，问n是多少。
因为3个数对n同余，所以这3个数两两相减的差都可以被n整除，286 − 210 = 76，381 − 286 = 95，可知76和95都可以被n整除，76和95的公因数为19，所以n = 19。
再来看一道复杂一些的题：试证明991991 + 993993能被1984整除。
注意到991 + 993 = 1984，所以将993993进行如下变化：
993993≡ (−991)993(mod 1984) = (−991)991×9912(mod 1984)
而9912 = 982081 = 495×1984 + 1，所以9912≡1(mod 1984)。
991991 + 993993≡991991 + (−991)991×9912(mod 1984)≡991991 + (−991)991×1(mod 1984)≡0(mod 1984)，因此991991 + 993993可以被1984整除。
最后，我们来看看如果除数为因数较多的整数时，如何利用上述整除和同余的性质求解。
例：设n为自然数，且24 | (n + 1)，试证明n的所有正整数因数（包括1和n本身）之和也能被24整除。
首先，我们定义“正整数因数对”的概念：设n = pq，p和q为正整数，则称p和q为n的一对正整数因数对。
因为正整数因数包括1和n本身，所以n总是可以表示成至少一对正整数因数p和q的乘积，即n = pq。
因为24 | (n + 1)，所以n是奇数，易知p和q也都是奇数。
又因为24 | (n + 1)，考虑3 | 24，所以有3 | (n + 1)，因此p和q都不是3的倍数。
再考虑到6 | 24，所以有6 | (n + 1)，因此pq = n ≡−1(mod 6)。
考虑p、q对6的余数。因为p和q都是奇数，所以p mod 6和q mod 6都不可能是0、2或者4；同时，因为p和q都不是3的倍数，所以p mod 6和q mod 6也不可能是3。因此p mod 6和q mod 6只能是1或者−1（即5）。
又因为pq≡−1(mod 6)，且pq mod 6 = (p mod 6)×(q mod 6)，所以p mod 6和q mod 6分别等于1和−1中的一个，即不能同时等于1或者−1。
不失一般性，设p = 6x − 1，q = 6y + 1，其中x和y为整数，x > 0，y≥0。
n + 1 = pq + 1 = 36xy + 6x − 6y = 24xy + 6(2xy + x − y)可以被24整除，所以(2xy + x − y)可以被4整除，x − y是偶数，即x和y奇偶性相同。
(p + 1)(q + 1) = 6x (6y + 2) = 12x(3y + 1)。显然，x、y同为偶数或者同为奇数时，x (3y + 1)都是偶数，即24 | (p + 1)(q + 1)。
同时， (p + 1)(q + 1) = pq + p + q + 1 = (n + 1) + (p + q)，因为n + 1和 (p + 1)(q + 1)都能被24整除，所以24 | (p + q)。
n的所有正整数因数之和，等于它所有的正整数因数对之和，上述过程证明了它的任一正整数因数对p和q之和都能被24整除，所以n的所有正整数因数之和可以被24整除。
彩蛋问题
如果某个日期组成的数字可同时被1、2、3、4、5、6、7、8、9、10整除，我们叫它超级整除日。例如2020年3月20日（20200320）就是21世纪第一个超级整除日。那么请问，21世纪的第二个超级整除日是哪年哪月哪日？
本节术语
截余法：对于除数x，利用某个接近10的幂的x的倍数，对被除数y进行截取补余从而求得x能否整除y的方法。
同余：当两个整数除以同一个正整数m时，如果得到的余数相同，则称这两个整数对模m同余。
“That's me. And that's three people. And I'm going to help them... and they do it for three other people.That's nine. And I give three more.That's 27. I'm not really good at math but it gets big very fast .”
— Pay it forward
“这是我。这是3个人，我去帮助他们……然后他们去帮助另外3个人，这就是9个人。我再画3个，这就成了27个。我数学并不是很好，但它增长得很快。”
——《让爱传出去》
在美国麻省理工学院，有一条长长的走廊。这条走廊将学院的主要建筑物连接了起来。虽然取名叫作“无限走廊”（infinite corridor），但实际上它的长度大约为251米。
2011年12月的一天，二十几个学生在数学老师詹姆斯·坦顿（James Tanton）的带领下在无限走廊中做了一个有趣的实验。他们每个人手中都捧着一叠厕纸，哦不，准确地说是捧着一张长长的、连续的、叠在一起的厕纸的一部分，大家小心翼翼地移动着，将厕纸一次次地对折起来（图1.2.1）。坦顿和他的学生之所以选择麻省理工学院的无限走廊，是因为这里是室内，不会受风的干扰，而且场地足够长，长到可以玩转总长度为54000英尺（约16459米）的厕纸。
图1.2.1 折叠厕纸挑战示意
如果他们能够将这长度约为16459米的厕纸成功地对折13次，那么他们将打破叠厕纸这一游戏的世界纪录。
坦顿和他的学生们并不是第一个尝试这个游戏的团队。2009年，科普电视节目《流言终结者》摄制组的成员准备了一张足球场大小的纸，节目嘉宾们往不同的方向反复将其折叠，在压路机的帮助下成功地将其对折了11次，最后得到一堆面积不到2平方米、厚度有2048层的叠纸。
很显然，这个游戏不仅仅是对数字的计算。理论上，只要纸张足够大，我们可以将一张纸近乎无限地对折，得到足够多的对折次数；不过在实际中，每一次对折不仅叠纸的层数加倍、面积减半，而且在折叠处还损失了部分纸张——更重要的是，折叠在物理上还带来了额外的张力，这些张力给纸张的韧性带来了很大的挑战。
所以，挑战者们选择了厕纸，因为它足够薄且折叠过程带来的额外张力足够小——如果你下次在超市里看到推着一车厕纸的人，就要想到他不一定是为了囤积，而也许是为了参与折叠厕纸挑战。
在小心翼翼地移动和折叠之后，坦顿和他的学生们成功地实现了13次对折，将厕纸折叠成大约1.5米长的物体，当然，这个物体共有8192层。这个结果打破了高中生布里特妮·加利文（Britney Gallivan）在2001年创造的11次对折的纪录，布里特妮的父母在购物中心花了85美元和7小时买来了长约1200米的厕纸，他们的女儿成功地将厕纸对折成了不到1米长的叠纸。
这，就是幂的力量。
大多数人对以2为底数的幂或者指数的增长的认识，可能来自传说中那个发明了国际象棋的老人和印度国王的故事，它有着看似以卑微开始、实则以贪心结束的反转剧情。按照1粒麦子重0.08克计算，摆满64个格子所需的麦子的质量（质量俗称重量）将超过15000亿吨。
除了这个传说，人们还可以通过细菌繁殖的例子来体会指数增长速度的恐怖。在适宜的条件下，大多数细菌只需要20分钟就可以繁殖一代，即由1个细菌分裂成2个细菌。由此计算，细菌一天内可以繁殖72代，两天内可以繁殖144代。如果一开始只有1个细菌，经过2天，这个菌落就可以变成22300745198530623141535718272648000000000000个细菌。别看细菌很小，这些细菌相当于几千个地球那么重！不过在现实中，细菌的繁殖受到营养物质的消耗、毒性产物的累积等很多因素的影响，它的繁殖不可能始终保持以指数的方式增长，所以我们不用担心细菌在两天内就“吃光”整个地球。
和2n相比，如果我们把底数和指数交换一下，得到n2，它的增长速度就要慢很多。对自然数n来说，n2也被称为完全平方数。完全平方数有很多有意思的性质，比如n2是前n个奇数之和，1 + 3 + 5 + … + (2n−1) = n2。有意思的是，这个公式除了用高斯算法——首尾相加求和进行推导以外，还可以用图示直观地表达出来（图1.2.2）。
图1.2.2 完全平方数的图示解法
每个用灰度表示的反“L”形正好占据奇数个小方格，它和它左上角方向的所有反“L”形加起来的正方形正好占据n2个小方格。
用类似的图示解法（图1.2.3），我们还能得到一个更加复杂的完全立方数的求和公式：
。
图1.2.3 完全立方数求和公式的图示解法
类似地，红色区域为13，绿色加红色区域为23 + 13，蓝色、绿色加红色区域为33 + 23 + 13，黄色、蓝色、绿色加红色区域为43 + 33 + 23 + 13……而相应正方形的边长为1、1 + 2、1 + 2 + 3、1 + 2+ 3 + 4……所以，以上公式显而易见，同时说明前n个完全立方数之和一定是完全平方数。
完全平方数其他的一些性质如下。
（1）完全平方数的末位数只能是0、 1、 4、 5、 6、 9其中之一。这个很容易通过1～9这9个个位数的平方进行验证。
（2）奇数的平方的个位数为奇数，十位数为偶数。这可以从(10n + k)2的展开式以及k = 1、 3、 5、 7、 9时的k2的结果得到证明。
（3）如果完全平方数的十位数是奇数，则它的个位数一定是6；反之，如果完全平方数的个位数是6，则它的十位数一定是奇数。平方后的个位数要得到6，那么原数的个位数只能是4或者6，将(10n + 4)2或者(10n + 6)2展开后可知十位数一定是奇数。类似地，可以证明个位数为0、 2、 8的数，其平方式展开后十位数一定是偶数，结合性质2，可知平方数十位数为奇数时，原数的个位数只能是4或者6。
（4）奇数的平方除以8余1，偶数的平方除以8余0或者4。设n = 2k + 1，n2 = 4k (k + 1) + 1，k和k + 1为连续自然数，其中必有一个偶数，所以n2除以8余1。对于n为偶数的情况，可以设n = 4k或者n = 4k + 2，类似地，可以得到证明。
（5）完全平方数除以3余0或者余1。设n = 3k或者n = 3k±1，类似地，可以得到证明。换句话说，如果一个数除以3余2，那么它一定不是完全平方数。
（6）完全平方数除以5不可能余2或者余3。设n = 5k、n = 5k±1或者n = 5k±2，类似地，可以得到证明。
（7）如果素数p能整除n，但p的平方不能整除n，则n不是完全平方数。完全平方数分解质因数后，每个质因数的个数必然是偶数，所以如果p是质因数之一，则其个数必然大于等于2。
（8）一个大于1的正整数n是完全平方数的充分必要条件是n有奇数个因数（包括1和n本身）。设n分解质因数后得到k个不同的质因数，每个质因数pi分别有ai个（i表示质因数的序号），如果n为完全平方数，则ai都为偶数，同时n的因数的总个数为
，所以它一定是奇数。
我们已经知道，由自然数构成的勾股数有无限多组，但连续3个自然数构成的勾股数有多少组呢？答案很简单，只有1组。
简单地设3个连续自然数为a − 1、a和a + 1，根据(a − 1)2 + a2 = (a + 1)2，可以得到a2 = 4a，即在自然数中，只有3、 4、 5这一组连续勾股数。
如果把这个问题扩大到5个连续自然数的平方数，其中前3个数的平方和等于后2个数的平方和，即(a − 2)2 + (a − 1)2 + a2 = (a + 1)2 + (a + 2)2，有解吗？
因为它仍然是一个一元二次方程，我们可以简单求解得到a2 = 12a，即在自然数中，只有10、 11、 12、 13和14这一组解，102 + 112 + 122 = 132 + 142。
如果再扩大到7个连续自然数的平方数呢？相应地，我们可以得到212 + 222 + 232 + 242 = 252 + 262 + 272。
因此，可以自然地联想到，对于2k + 1个连续自然数，如果前k + 1个自然数的平方和等于后k个自然数的平方和，那么有且只有一个解，即2k2 + k , 2k2 + k + 1, 2k2 + k + 2 , … , 2k2 + 3k一组连续自然数。具体的证明过程就交给有兴趣的读者朋友吧。
下面考虑一个有趣的问题：n > 1，n!是否是一个完全平方数？我们可以实验性地列出前10个自然数的阶乘的质因数分解：
2! = 2
3! = 2×3
4! = 23×3
5! = 23×3×5
6! = 24×32×5
7! = 24×32×5×7
8! = 27×32×5×7
9! = 27×34×5×7
10! = 28×34×52×7
可以观察到最大质因数的个数始终等于1；而且进一步可以发现，所有满足条件
的质因数，其个数也是1。按照上述完全平方数的性质7，完全平方数的每一个质因数的个数应该都是偶数。因此，可以推测n!不可能是一个完全平方数。
事实上，根据素数定理，当n是偶数时，
和n之间至少有一个素数p；当n是奇数时，
和n + 1之间至少有一个素数p。因为p < n，所以p一定是n!的质因数；同时p≥2，p2≥2p > n，所以p2一定不是n!的质因数，由此可知n!中p的个数为1。所以对于n > 1，n!一定不是一个完全平方数。
别看这个问题简单，在2019年的国际数学奥林匹克竞赛（International Mathematical Olympiad, IMO）中就出现了它的身影，也就是那届比赛的第4题：求所有的正整数对(k , n)，满足k! = (2n − 1)(2n − 2)(2n − 4) … (2n − 2n−1)。
类似地，先实验性地写出n等于前几个正整数时的等式的右边。
n = 1时，等式的右边为1。
n = 2时，等式的右边为3×2。
n = 3时，等式的右边为7×6×4。
n = 4时，等式的右边为15×14×12×8。
n = 5时，等式的右边为31×30×28×24×16。
……
可以很容易发现1! = 1，3! = 3×2， (1,1)和(3,2)是两个符合题意的特定解。
还有没有其他的解呢？
先看等式左边。等式左边是k的阶乘，如果对它进行质因数分解，因数2的指数是多少呢？显然，在连续k个正整数中，每2个数就有一个偶数，每4个数就有一个4的倍数，每8个数就有一个8的倍数……同时，一个4的倍数带来2个因数2，一个8的倍数带来3个因数2……
所以，k!质因数分解后因数2的指数，即k!中因数2的个数
，其中l是使得2l≤k的最大正整数，符号
表示不大于x的最大整数，即向下取整。
同样，k!质因数分解后因数3的指数
，其中m是使得3m≤k的最大正整数。
这样的公式通常被用来计算自然数阶乘的质因数分解中某个素数的指数，它也被称为勒让德定理（又称勒让德尔定理）。
设Rk为等式左边因数2的指数与因数3的指数之比，即
。
根据向下取整符号的定义，一定有
，所以
（1.2.1）
再看看因数3的指数，
。当k ≥ 9时，式中
，所以
。又根据向下取整符号的定义，
，所以有
（1.2.2）
因此，对于k≥9，结合式（1.2.1）和式（1.2.2）可以得到
（1.2.3）
再手算看一下2 < k < 9时的情况，容易发现k = 8时Rk = 3.5， 取到最大值。因此结合式（1.2.3）可以得到，对于所有k > 2的情况，
（1.2.4）
现在来看等式的右边，我们将它变形一下：
类似地，设Fn,2和Fn,3分别为等式右边质因数分解后因数2和因数3的指数，设Rn为两者之比，即
。
这样，
（1.2.5）
因数3则全部来自于n个奇数的连乘。
把之前的实验性结果按照这个式子改写一下。
n = 1时，等式的右边为20×1。
n = 2时，等式的右边为21×3×1。
n = 3时，等式的右边为23×7×3×1。
n = 4时，等式的右边为26×15×7×3×1。
n = 5时，等式的右边为210×31×15×7×3×1。
……
观察以上连乘式中的奇数，可以发现当且仅当n为偶数时，连乘式中最大的一个奇数2n − 1是3的倍数。证明如下。
当n为奇数时，设 n = 2p − 1，p为正整数，那么
2n − 1 = 22p−1 − 1 = 2×22 ( p−1) − 1 = 2×4 p−1 −1 = 2× (3 + 1)p−1 − 1
根据二项展开式， (3 + 1)p−1≡1(mod 3)，所以2n − 1≡2 − 1 = 1(mod 3)， 这个奇数不能被3整除，对连乘公式中因数3的个数没有贡献。
当n为偶数时，设 n = 2p，p为正整数，那么
2n − 1 = 22p − 1 = 4p − 1 = (3 + 1)p − 1
二项式展开后可以得到
可见，3 | (2n − 1)。更进一步，当3 | p时，9 | (2n − 1)；当9 | p时，27 | (2n − 1)……当3q | p时，3q+1 | (2n − 1)。
因为n = 2p，所以在等式右边n个奇数的连乘式中，从1开始，每2个数就有一个3的倍数，每6个数就有一个9的倍数，每18个数就有一个27的倍数……
类似地，根据勒让德定理，该连乘式中因数3的个数
，其中q是使得2×3q≤n的最大正整数。
再一次根据向下取整符号的定义，
。根据等比数列求和公式，首项为
，公比为
，得到
结合式（1.2.5），得到
（1.2.6）
对于任意满足题意的(k,n)，等式两边因数2的指数和因数3的指数应该分别相等，那么等式两边两个因数指数之比也应该相等，即Rk = Rn。结合式（1.2.4）和式（1.2.6）得到，对于任意k > 2，
，
，即n≤ 5。
经验证，n = 3、4或5都不是解，所以(1,1)和(3,2)是符合题意的仅有的两组解。
彩蛋问题
因为2020年的诸多不如意，有人非常怀念2019年，他想找到两个自然数m和n，使得m3 + n3 = 20192019…2019（共2020个2019）。请问，他的愿望能够实现吗？
本节术语
完全平方数：可以写成某个整数的平方的数，或者其平方根为整数的数，被称为完全平方数。
勒让德定理：n为正整数，对其阶乘n!进行质因数分解，则素数p的指数
，k为正整数。
“God gave him his boyhood one-sixth of his life, One-twelfth more as youth while whiskers grew rife; And then yet one-seventh ere marriage begun; In five years there came a bouncing new son. Alas, the dear child of master and sage. After attaining half the measure of his father's life chill fate took him. After consoling his fate by the science of numbers for four years, he ended his life .”
—Diophantus' riddle
“上帝给予他的童年占了生命的六分之一。再过了生命的十二分之一，青年的胡须越来越浓密；然后又过了生命的七分之一，他结婚了。婚后五年，他迎来了一个健康的儿子。唉，大师和贤哲的宝贝孩子，仅仅过了他父亲生命一半的时间，凄苦的命运就带走了他。靠数字的科学慰藉着自己的命运，四年之后，丢番图的生命也到了尽头。”
——丢番图的谜题
美国布法罗大学的数学教授斯蒂芬·卡维奥尔（Stephen Cavior）是个风趣的老头，他曾经在课堂上讲过一个有趣的故事。
在一个美好的周日早晨，卡维奥尔像往常一样端起一杯新煮好的咖啡，准备开始读书。这个时候他接到一位朋友的电话，朋友请他帮忙解决一个数学问题，这个问题已经困扰她好几天了；更令人兴奋的是，第一个得出答案的人可以获得由麦当劳设立的价值100万美元的大奖。
这个大奖的题目是这样的：请给3, 48, 6, 21, 33, 18, 36, 12, 60乘整数系数，使得它们的和为100。
卡维奥尔看到最后一个数字时笑了。他告诉他的朋友，不要再枉费时间，因为这个题目无解。
这是一个在课堂上讲述的故事，其真实性当然不可考。作为题目来说，这个麦当劳“大骗局”并不难破解：我们注意到那一堆数字全都是3的倍数，所以无论使用哪些整数系数，它们的和仍然将是一个3的倍数，而100并不是3的倍数，所以两者不可能相等。
如果我们把其中的一个数换成不是3的倍数，比如把33换成32，那么这个“免费大汉堡”是不是可能从天而降呢？答案显然是存在的，而且不止一个，例如2×36 + 1×60 + (−1)×32 = 100，或者6×21 + 1×6 + (−1)×32 = 100。
当然，数学中类似的问题可比麦当劳的大奖要难得多,比如下面这道关于砝码的题目。
有13克和17克的砝码若干，使用这些砝码不能称得的最大整数质量是多少克？
我们先约定，砝码只能放在一侧，货物放在另一侧，即砝码之间只能相加不能相减，否则此题无解（理由在后面给出）。从直觉上来说，一些比较小的整数质量很显然是无法通过砝码的组合得到的，比如2克、15克等，这道题的目标就是找到这一类整数质量中最大的一个。
用数学语言来表述，就是对于非负整数x、y和n，试求出n的最大值，使得方程13x + 17y = n无解。
可以看出，砝码问题和麦当劳“大骗局”属于同一类问题，它们都是求解线性不定方程，即未知数的个数多于方程数（在这两个例子中，都只有1个方程），未知数的最高幂为1（即方程为线性）。一般来说，线性不定方程有无数多个解，但在系数和未知数都是整数的情况下，不定方程可能有确定的解，也可能无解。这一类未知数和系数都是整数的不定方程，在数学上又被称为丢番图方程（Diophantine equation）。
丢番图是古希腊时期的数学家，生活在约公元200—300年，大约相当于我国的三国时期。丢番图生卒年份不详，出生地不详，“国籍”也不详，古籍中称呼他是“亚历山大港的丢番图”，是因为他成年之后住在埃及的亚历山大港，他的研究工作主要是在那里完成的。丢番图被认为是“代数之父”，《算术》被认为是他的著作。
我们从最简单的情况来研究丢番图方程，考虑在只有两个未知数x和y以及1个线性方程的情况下，什么时候这个方程有解，什么时候没有解。以下，我们说方程有解和无解，都特指有无整数解。
从上述麦当劳的例子我们能看出来，当丢番图方程等号左边的系数中存在某个最大公因数，而方程另一边的常数不能被这个公因数整除时，这个方程无解。比如方程12x + 18y = 100，等号左边系数的最大公因数为6，而100不能被6整除，所以方程无解。
如果方程等号右边的常数都可以被这个公因数整除，那么我们将方程的两边分别除以这个公因数，比如
12x + 18y = 90
（1.3.1）
将方程两边同时除以6得到
2x + 3y = 15
（1.3.2）
显然，方程（1.3.2）和方程（1.3.1）是等价的。
再进一步，如果我们把方程右边的得数人为地改为1，即
2x + 3y = 1
（1.3.3）
如果方程（1.3.3）有某个解，比如(2,−1)，把这个解乘15，就可以得到方程（1.3.2）相应的一个解(30,−15)，这个解同样也是方程（1.3.1）的解。
因此，我们的问题就简化为：当系数a和b互质时，ax + by = 1有没有解？
在数论中，贝祖定理（Bézout's lemma，又称裴蜀定理）给出了这个问题的答案，即当且仅当整数a和b互质时，方程ax + by = 1有整数解。
下面，我们尝试证明这个定理。以方程（1.3.3）为例，进行一下变形：
2x + 3y = 1
2 (x + y) + y = 1
（1.3.4）
注意，变形后的方程（1.3.4）仍然是一个丢番图方程，只不过其未知数x + y和y是方程（1.3.3）的未知数x和y的线性组合，同时方程（1.3.4）的两个系数中有一个变成了1。
这时，我们令系数为1的未知数等于1，另一个系数的未知数等于0，即
（1.3.5）
那么不论另一个系数是多少，方程（1.3.4）都将恒等。
从方程组（1.3.5）解得x = −1，y = 1，易知(−1 , 1)确实是方程（1.3.3）的一个解，而且是一个不同于前面得到的(2 ,−1)的解。
我们再看一个复杂一些的例子，6x + 35y = 1，其中6和35互质，变形如下：
6x + 35y = 1
6 (x + 5y) + 5y = 1
(x + 5y) + 5 [ y + (x + 5y)] = 1
（1.3.6）
方程（1.3.6）的两个线性组合后的未知数为x + 5y和y + (x + 5y)，其系数分别为1和5。令
，解方程组得到x = 6，y = −1，易知(6 , −1)是原方程的一个解。
这个变形过程是不是有些眼熟？如果只写出系数，这个变形过程就是两个整数辗转相除求公因数的过程。而我们知道，互质整数的公因数是1，所以在变形过程的最后，我们一定能得到一个未知数的系数为1，令这个线性组合后的未知数等于1，另一个线性组合后的未知数等于0，方程就能恒等。
一般来说，二元一次方程组一定有解，除非两个方程的斜率相同而截距不同，相当于两条直线在二维平面上平行不相交。
在我们这个问题中，这两个方程的斜率必定不同。如果斜率相同，假设变形后的方程为(k·c·x + c·y) + m(k·d·x + d·y) = 1，其中第一个未知数的系数为1，第二个未知数的系数为m；c和d都为整数，两个线性组合中x、y的斜率同为k。现在把圆括号拆开，分别合并x和y的同类项，将得到k(c + md ) x + (c + md )y = 1，即原方程的两个系数都有整数因子(c + md )，这与两个系数互质的前提条件相矛盾。
综上所述，贝祖定理得证。
再进一步，如果ax + by = 1有一个解(x0 , y0)，那么
ax0 + by0 = 1
ax0 + ab + by0 − ab = 1
a(x0 + b) + b(y0 − a) = 1
即(x0 + b, y0 − a)也是方程的一个解。同理可得：
对于任一整数m，(x0 + mb , y0 − ma)都是方程的解。 （定理1.3.1）
如果a和b互质，那么方程ax + by = 1一定有解，对任一整数n来说，方程ax + by = n也一定有解。换句话说，可以使用不同的整数组合(x , y)，使得ax + by的值域覆盖整个整数集合。
现在，让我们回到砝码问题。
因为13和17互质，对任一整数n来说，方程13x + 17y = n都有整数解。所以，我们需要限定砝码只能放在天平的同一侧，即只考虑13x + 17y = n的非负整数解。换句话说，砝码问题中的线性方程是一种特殊的丢番图方程，它要求解为非负整数。
我们先找到13x + 17y = 1的一个可行的整数解（可正可负）。通过上述的辗转相除法变形，得到
13x + 17y = 1
13(x + y) + 4y = 1
(x + y) + 4 [ y + 3(x + y)] = 1
令
，解方程组得到x = 4，y = −3。
因此对于13x + 17y = n，(4n , −3n)是方程的一个解。根据定理1.3.1，对于任一整数m，(4n + 17m , −3n − 13m)都是方程13x + 17y = n的整数解。
现在我们对x和y加上非负的要求，即4n + 17m≥0，且−3n − 13m≥0，整理后得到
，或者m的取值闭区间为
。
我们看到，当n = 13×17时，m取值的闭区间为[−52 , −51]。所以当n足够大，且不小于13×17时，这个闭区间的长度大于等于1，区间中一定存在整数m。所以符合题意要求的n一定小于13×17。那么13×17 − 1= 220是不是砝码问题的正确答案呢？
当n < 13×17时，尽管闭区间长度小于1，但如果该区间跨越某个整数，此时仍可以取到整数m，例如n = 220时，闭区间大约为[−51.765 , −50.769]，此时m仍可以取−51，相应的x和y分别为13和3，即13×13 + 3×17 = 220。所以220不是砝码问题的正确答案，正确的n比13×17 − 1还要小。
那么，这个13×17是不是没有其他任何价值了呢？并不是。考虑
13x + 17y = 13×17
（1.3.7）
显然(0, 13)和(17, 0)是它的两组非负整数解。但它有没有严格的正整数解呢？不难发现，当y不为0时，x一定要能被17整除，能被17整除的最小正整数为17，而x≥17时，17y = 13×17 − 13x≤0，y已经不可能为正整数，因此方程（1.3.7）没有正整数解。
再来考虑这样一个方程：
13(x + 1) + 17(y + 1) = 13×17
（1.3.8）
因为方程（1.3.7）没有正整数解，所以方程（1.3.8）没有非负整数解。将方程（1.3.8）整理一下，得到13x + 17y = 13×17 − 13 − 17，所以当n = 13×17 − 13 − 17时，方程13x + 17y = n没有非负整数解。
对于任意13×17 > n > 13×17 − 13 − 17，如果有13x + 17y = n，显然x≤16，同时，17y = n − 13x > 13×17 − 13 − 17 − 13x≥13×17 − 13 − 17 − 13×16 = −17，即y > − 1，方程存在非负整数解。
因此，当n≥13×17 − 13 − 17 + 1 = (13 − 1)×(17 − 1)时，13x + 17y = n始终有非负整数解。当n = 13×17 − 13 − 17，即n = 191时，13x + 17y = n没有非负整数解。所以，使得方程13x + 17y = n无非负整数解的n的最大值为191。
如图1.3.1所示，在二维平面上画出代表13x + 17y = 191、13x + 17y = 192和13x + 17y = 193的3条直线。
图1.3.1 线性方程13x + 17y = 191(黑线)、13x + 17y = 192(红线)和13x + 17y = 193(蓝线)
局部放大后（图1.3.2）我们可以发现，红线穿过点(3,9)，即(3,9)是方程13x + 17y = 192的一个非负整数解。
图1.3.2 局部放大后的3条直线
在另一个局部（图1.3.3），蓝线穿过点(7,6)，即(7,6)是方程13x + 17y = 193的一个非负整数解。
图1.3.3 另一个局部放大后的3条直线
因此，191是使得方程13x + 17y = n无非负整数解的n的最大值。
如果丢番图方程中的未知数具有更高次的幂，那么我们就能得到非线性的整数方程。
当直角三角形的3条边都是整数时，得到的勾股数就是二次方程的一组整数解，比如，我们熟知的(3,4,5)、 (5,12,13)就是二次方程a2 + b2 = c2的两组整数解。一个有意思的问题是，除了那些有倍数关系的勾股数以外，比如(3,4,5)和(6,8,10)，勾股数是不是有无穷多组呢？
我们观察最初的几组勾股数(3,4,5)、 (5,12,13)、 (7,24,25)，可以发现，a是奇数，而b和c之间只相差1。如果把勾股定理的方程变动一下：
a2 + b2 = c2
a2 = c2 − b2 = (c + b)·(c − b)
可见，只要c比b大1，c和b的和是一个完全平方数，那么我们就能得到一组勾股数。这个条件实在是太容易满足了！不妨设奇数a = 2k + 1，其中k为任意正整数，那么
a2 = 4k2 + 4k + 1
令c + b = 4k2 + 4k + 1，同时c − b = 1，解得c = 2k2 + 2k + 1，b = 2k2 + 2k。
因此对于任意正整数k， (2k + 1, 2k2 + 2k, 2k2 + 2k + 1) 都是一组勾股数。所以，非倍数的勾股数有无穷多组，即二次方程 a2 + b2 = c2 有无数多个整数解。
我们会很自然地产生疑问，当整数方程未知数的幂n大于2时，方程 an + bn = cn 有没有正整数解呢？
这就是著名的费马大定理中的问题！
费马大定理由 17 世纪法国数学家皮埃尔·德·费马（Pierre de Fermat）提出，他猜想当整数 n > 2 时，上述关于 a、 b 和 c 的不定方程没有正整数解。1637 年，费马在阅读丢番图的《算术》一书时，在书的页边空白处写下了这个猜想，并表示自己已经找到了证明这个猜想的一种精妙的方法，可惜这里的空白处太小，无法写下。
费马没有留下证明，但是他的这个数学形式极其简洁的定理激发了许多数学家的兴趣，从17世纪到20世纪，无数人试图证明这个猜想。1900年，德国数学家达维德·希尔伯特（David Hilbert，又译为大卫·希尔伯特）在第二届国际数学家大会上总结了当时悬而未决的23个著名数学问题，在谈到他为什么不去尝试证明费马猜想时，希尔伯特说：“我没有那么多时间浪费在一件可能会失败的事情上。”由此可以证明费马猜想的解决难度。直到1995年，费马猜想才被英国数学家安德鲁·约翰·怀尔斯（Andrew John Wiles）得以完全证明，费马猜想正式转变为费马大定理。
在课本中有不少与非负线性丢番图方程相关的实例，比如我们去寄信，邮票面值有8分、1角5分两种，信件的邮资是7角，我们该如何支付足够的邮资又不浪费呢？（都什么年代了，现在哪有这么便宜的邮票和邮资？！）又比如警察叔叔手中有n个不同面值的硬币，一共价值m元，问各种硬币各有几个？（小朋友们知道拾金不昧就行啦，费这个劲儿干什么呢！）
这些实例看似应用价值不大，但丢番图方程在其他学科和现实生活中有着广泛而重要的应用。
比如，线性规划是运筹学的一个重要分支，它广泛地应用于工农业、商业、交通运输、军事、经济和管理决策领域，是现代科学管理的重要手段之一。线性规划中的数学模型一般都是可以表示为一组约束条件［即由变量组成的线性不等式（或者方程）组］，以及一个目标函数（即由各变量组成的一个线性函数）。在加入额外的松弛变量和剩余变量之后，线性不等式可以转化为线性方程。这些额外变量的加入使得变量的数量往往要多于不等式的数量，此时线性规划问题就转化为一个在线性不定方程组约束条件下对线性目标函数求最值的最优问题。使用丢番图方程和贝祖定理对线性不定方程组进行求解，是解决这类最优化问题的基础。
彩蛋问题
丢番图究竟活了多少岁呢？
本节术语
丢番图方程：系数和解都为整数的多项式方程（组），其方程数少于变量数，又被称为整系数不定方程（组）。
贝祖定理：关于变量x和y的线性丢番图方程ax + by = m，其存在整数解的充分必要条件为m是系数a和b的最大公约数d的倍数。特别地，当且仅当系数a和b互质时,方程ax + by = 1存在整数解。
勾股数：当直角三角形的直角边a、b和斜边c都是整数时，(a,b,c)被称为勾股数。勾股数即二次方程a2 + b2 = c2的整数解。
费马大定理：当整数n＞2时，方程an + bn = cn没有正整数解。
“三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知。”
——程大位，《算法统宗》
“汉初三杰”之一的韩信是淮阴人，最开始跟着项梁、项羽叔侄打江山，足智多谋的他曾多次向项羽献计却始终没有被采纳，郁郁不得志之下他转而投奔了刘邦。不过，“跳槽”到一个新“公司”重新开始职业生涯谈何容易？更何况刘邦信任的是他的“沛县帮”，那些在他当亭长时就在一起厮混的兄弟伙。所以尽管在多次交谈中，韩信逐渐为“沛县帮师爷”萧何所赏识，却一直没有得到刘邦的青睐和重用。
思来想去，韩信决定再次“跳槽”。萧何是个惜才的人，觉得韩信走了对刘邦来说是一个无法弥补的损失，所以他连夜追回了韩信。刘邦听说了这回事，不免责怪萧何：“公司每年都有高管离职，没见你追；一个业绩平平的小职员跑了，你倒是这么紧张！”萧何回答说：“老板你不知道啊，像韩信这样的人才，失去了一个，天下就不会再出现第二个了。”
在萧何的极力推荐下，刘邦勉强同意让韩信做一个将军。将军这个头衔并不高，手下满员也就1200名士兵。在一次作战中，作为接应的韩信部队在紧要关头顶住了敌军主力的反扑，以100多名士兵伤亡的微弱代价换取了最后的胜利。捷报传来，刘邦亲自在军营门口迎接韩信，并问起具体伤亡了多少人。
只见韩信令旗一挥，士兵们以3人一排列队，队尾多出2人；又以5人一排列队，队尾多出4人；再以7人一排列队，队尾多出3人。韩信沉吟片刻，回答说：“参与列队的共有1004名士兵，本次战斗伤亡196人。”刘邦很惊讶，派人细细数了一遍，队中果然尚有1004名士兵。
心中佩服之下，刘邦拉着韩信的手说：“我之前低估了你啊，区区1200人绝对是委屈了你的才干，你觉得我可以把多少士兵交给你？”韩信脱口而出：“自然是越多越好，多多益善嘛！”刘邦反问：“那你觉得我可以带多少兵？”韩信说：“最多10万吧。”刘邦不高兴地说：“这意思就是我的能力不如你？”韩信回答：“不，我最多是个善于带兵的将军，而老板你才是善于统帅将军的人啊。”
最终，韩信成了刘邦手下的名将，为西汉王朝立下了汗马功劳。最终帮助韩信取得刘邦信任的无疑是他的军事才能，而不是上述逸事中近乎奉承的回答或者超人的数学天赋。
假定在以上故事中的一类问题被称为一元线性同余方程组问题。用除数除未知数得到余数，如果除数和余数已知，求未知数，这类方程被称为线性同余方程；如果只有一个未知数，有多个已知除数和余数，那么这一组方程就被称为一元线性同余方程组。
在“韩信点兵”的故事中，士兵人数是未知数x，除数分别为3、5和7，余数分别为2、4和3，所以得到的方程组为
一般地，这类方程组有多个解。加入约束条件“原有士兵1200人，伤亡100多人”，即x的范围为1000～1100，那么可以得到确定解1004。
一元线性同余方程组其实很常见。在小学学习公倍数的时候，习题中就有一元线性同余方程组的影子。比如：有一堆糖，数量为50～100，5颗装一袋正好装完，7颗装一袋也正好装完，问一共有多少颗糖。这是比较简单的公倍数问题，5和7的最小公倍数为35，糖的数量为50～100，所以一共有70颗糖。
加上余数，这道题就成为一元线性同余方程组问题，比如：5颗装一袋最后剩2颗，7颗装一袋最后也剩2颗。当余数相同时，这个问题仍然比较简单，只需求得符合题意的5和7的公倍数，再加上余数即可，即5×7×2 + 2 = 72颗糖。
再加一个条件：如果4颗装一袋最后剩3颗，5颗装一袋最后剩4颗，6颗装一袋最后剩5颗，怎么解题？这时候余数不同了，但注意到这些余数都是相应的除数减1，等价于余−1，因此还是利用类似余数相等的方法，求得（最小）公倍数60，加上余数−1，得到正确答案59。
当余数不等时，类似于“韩信点兵”的情况，问题就复杂了。比如：有一堆糖，5颗装一袋剩3颗，7颗装一袋剩2颗，9颗装一袋剩7颗，问一共有多少颗糖。这时，我们无法简单地通过求取公倍数的方法得到答案。
其实，古人在很早的时候就注意到了这一类一元线性同余方程组的问题。在南北朝时期有一本数学专著——《孙子算经》，里面就记载了一个叫“物不知数”的问题。问题的表述是这样的：
今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
这段文言文很容易理解，用数学语言来说就是：整数x用3除余2，用5除余3，用7除余2，问x是多少。
古人对这个问题进行了研究，除了《孙子算经》里给出的解法以外，南宋数学家秦九韶和明代珠算家程大位都对这类问题进行了系统的研究，给出了详细的解答。这些解答要早于西方至少300多年，直到19世纪德国数学家高斯等人才提出类似的方法，《孙子算经》提出的解法也被西方称为“孙子剩余定理”（又称中国剩余定理）。
下面我们来看看，从简单的公倍数和同余性质入手，如何理解和解决一元线性同余方程组问题。
以“物不知数”问题为例，我们需要求得x，使得
我们从最简单的情况开始考虑，假设只有除数为3和5的两个方程。对于第一个方程，我们可以简单写出对3模2的数，它们分别是
2,5,8,11,14,17,20,23,26,29,32,35,38,41,44,47,50,53,…
相邻的两个数间隔3。再看看对5模3的数，它们分别是
3,8,13,18,23,28,33,38,43,48,53,…
相邻的两个数间隔5。如果比较一下这两个数列，我们可以找出它们共同拥有的数字8、 23、 38、 53……这些数字既满足第一个方程，又满足第二个方程，所以它们就是方程组的解。同时，很容易发现解中相邻的两个数字间隔15，是3和5的最小公倍数。
因此，这个方程组的解可以表示为x = 15k + 8，k是一个非负整数。在这种表示方法中，8是一个基本解，也是最小正整数解，15是3和5的最小公倍数，也是不同解之间的最小间隔。
现在考虑这个问题：如果把前两个方程组的解表示为一个余数方程，那么应该怎么写？x = 15k + 8可以理解成用15除x余8，写出余数方程的话就是x≡8(mod 15)。因此，原有3个方程的方程组就等价于以下两个方程的方程组。
类似地，我们分别写出符合两个余数方程的数列：
8,23,38,53,68,83,98,113,128,143,…
2,9,16,23,30,37,44,51,58,65,72,79,86,93,100,107,114,121,128,135,142,…
两个数列中都有的数字为23、128……相邻的两个数字间隔105，即15和7的最小公倍数。因此，“物不知数”问题的解可以表示为x = 105k + 23，k是一个非负整数。
在这个通解公式中，105很好理解，也很容易求得，它是3个除数（3、5和7）的最小公倍数。那么除了列出所有的数字，有没有更加简单的方法求得最小正整数解23呢？
程大位在《算法统宗》中使用了歌诀“三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知”，其中每一句提到了一个数字，分别为70、21、15和105。按照《孙子算经》和程大位给出的解法：分别用70、21和15乘3个方程的余数2、3和2，加起来得到233，233就是方程组的一个基本解，方程组的通解也可以表示为x = 105k + 233，k为整数。我们寻找的最小正整数解23实际上就是k = −2时的解。
现在问题就变成了：如何找到70、21和15这3个数？21和15很好理解，分别是其他两个方程中除数的最小公倍数3×7和3×5，如果按照这个规律，用在第一个方程上的数应该是5×7 = 35，可是为什么这里是70呢？
我们先将21和15分别用剩余的方程的除数取余，21≡1(mod 5)，15≡1 (mod 7)。再将5和7的最小公倍数35用第一个方程的除数3取余，35≡2(mod 3)；如果用70除以3取余，70≡1(mod 3)。因此，孙子剩余定理的关键，就是要使得3个方程乘的系数对各自的除数取余都为1，这也是秦九韶把这一算法称作“大衍求一术”的原因。
我们以不同余糖果分袋问题中的那组数字为例，解释孙子剩余定理的上述解题过程。
第一个方程的系数应该是7和9的公倍数，因为63≡3(mod 5)，所以使用63×2 = 126≡1(mod 5)。
第二个方程的系数应该是5和9的公倍数，因为45≡3(mod 7)，所以使用45×5 = 225≡1(mod 7)。
第三个方程的系数应该是5和7的公倍数，因为35≡8(mod 9)，所以使用35×8 = 280≡1(mod 9)。
然后进行计算，126×3 + 225×2 + 280×7 = 2788，5、7和9的最小公倍数为315，2788≡268(mod 315)，所以方程组解的通式为x = 315k + 268，k为一个非负整数，最小正整数解为268。
对孙子剩余定理解法的证明也不难。在通式中，因为各个除数的最小公倍数能够被每个除数整除，所以x加上或者减去这个最小公倍数并不会影响单个余数方程的成立，因此只需证明通过系数相乘后相加得到的值是方程组的一个基本解即可。
设方程组为x≡ri(mod di)，其中di为第i个方程的除数，ri为对应的余数。按照孙子剩余定理的方法，设系数ci是除di以外其他除数的公倍数，且ci≡ 1(mod di)，将每个方程的余数乘系数后相加得到
将x0对第j个除数dj取余，因为cj与dj互质，而其他的ci可以被dj整除，可知，
所以x0是第j个余数方程x≡rj(mod dj)的一个解。因为这个结论对于任意一个j都成立，所以x0也是整个方程组的一个基本解。
注意，我们在证明过程中用到了cj与dj互质，在以上提到的例子中，除数之间也确实两两互质。那么，如果除数之间存在公因数，这样的一元线性同余方程组又该如何求解呢？
同样，我们从最简单的情况开始分析。
设x≡r1(mod d1)和x≡r2(mod d2)，且d1和d2的最大公约数gcd(d1,d2) = d > 1，设d1 = dp1，d2 = dp2，显然p1和p2互质。
令x = d1x1 + r1，x = d2x2 + r2，可以得到
dp1x1 + r1 = dp2x2 + r2
即
d( p1 x1 − p2 x2) = r2 − r1
因为方程左边是d的倍数，所以右边r2 − r1必须能够被d整除，否则方程无解。
因此，一般地，如果一元线性同余方程组的各个除数互质，那么同余方程组有解；如果存在不互质的除数对，且它们的余数之差能够被除数对的最大公约数整除，那么仍然有解，否则方程组无解。
比如，x≡2(mod 4)，x≡3(mod 6)，因为3 − 2不能被4和6的最大公约数2整除，所以方程组无解。换一个角度，x≡2(mod 4)说明x是偶数；而x≡3 (mod 6)说明x是奇数，相互矛盾，所以方程组无解。
那么，如果r2 − r1能够被d整除，该怎么求解呢？
设d1和d2的最小公倍数lcm (d1, d2) = m = dp1 p2 。同时，设x = k1d1 + r1 + k2m，显然x满足余数方程x≡r1(mod d1)。
如果x也要满足余数方程x≡r2(mod d2)，只需k1d1 + r1≡r2(mod d2)。换句话说，只要我们能够找到某个整数k1，使得k1d1 + r1≡r2(mod d2)，那么就可以在同余方程组中用x≡k1d1 + r1(mod m)取代原来的两个同余方程，继续求解。
出于对称性，如果能够找到某个整数k2，使得k2 d2 + r2≡r1(mod d1)，那么也可以在同余方程组中用x≡k2 d2 + r2(mod m)取代原来的两个同余方程，两个方程是等价的。
我们以余数为−1的糖果分袋题目为例，看看如何通过上述方法求解。原方程组为
第一个方程的除数4和第三个方程的除数6不互质，4和6的最小公倍数m为12。
我们求解k1d1 + r1≡r2(mod d2)，即4k1 + 3≡5(mod 6)，4k1≡2(mod 6)，易知k1 = 2是一个解，所以构造出来的新的同余方程为x≡4×2 + 3 = 11(mod 12)。
或者，求解k2d2 + r2≡r1(mod d1)，即6k2 + 5≡3(mod 4)， 6k2≡2(mod 4)，易知k2 = 1是一个解，新的同余方程为x≡6×1 + 5 = 11(mod 12)。得到的同余方程完全相同。
接下来，再按照互质条件下的方法求取新方程组的解。
因为5×5 = 25≡1(mod 12)，所以第一个方程系数取25；因为12×3 = 36≡1(mod 5)，所以第二个方程系数取36；基本解为11×25 + 4×36 = 419，对12和5的最小公倍数60取余，得最小正整数解为59，所以方程组的通解公式为x = 60k + 59，k为一个非负整数。
由此可见，对于一般形式的一元线性同余方程组问题，孙子剩余定理给出了其有解的条件以及求解的方法；对于特殊形式的一元线性同余方程组问题，则可能存在更为简便的解法，比如上述余数都为−1的情况，就可以使用补足余数求最小公倍数的方法求解。
本节术语
线性同余方程：形如ax≡c(mod b)的方程被称为线性同余方程，它表示线性表达式ax与c对模b同余。
一元线性同余方程组：只有一个未知数，有多个已知除数和余数的线性同余方程被称为一元线性同余方程组。
孙子剩余定理：又称中国剩余定理、中国余数定理，是数论中一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的规则以及求解方法。
