数论研究什么？

拿一把棋子摆正方形，能摆出来的数量很熟悉：$1$ 颗、$4$ 颗、$9$ 颗、$16$ 颗、$25$ 颗……现在把每一种数量都改成每组 $4$ 颗来分，看看会剩下几颗。

$1$ 颗剩 $1$，$4$ 颗剩 $0$，$9$ 颗剩 $1$，$16$ 颗剩 $0$，$25$ 颗又剩 $1$。怎么来来回回只有 $0$ 和 $1$？剩 $2$ 颗或 $3$ 颗的正方形，难道一个也没有？

你当然可以接着算 $36$、$49$、$64$。但即使算到一百万，也还有没算过的数。数论想追问的，正是计算后面这一步：这个现象究竟是巧合，还是任何整数都逃不开的规律？如果是规律，凭什么？

数论研究整数，以及整数之间的关系。 能不能分得刚好、哪些数能拆成乘积、余数为什么出现某种规律，都是它关心的问题。这些问题用小学算术就能说清楚，解释起来却常常需要换个角度。我们先把整数的几个基本特点摸清，再回来处理刚才的正方形。

整数的特别之处，是中间没有半格

数一盒棋子有多少颗，可能得到 $0,1,2,3,\ldots$。本课程把这些数叫作自然数，并约定自然数包括 $0$：

如果记账时要表达欠款，或者记录气温降到零度以下，我们还需要负数。正整数、零、负整数合起来，构成整数集合：

“正整数”专指 $1,2,3,\ldots$；$0$ 既不是正数，也不是负数。以后命题中写“自然数”还是“正整数”，往往决定着是否需要额外处理 $0$，不能随手略过。

把整数放在数轴上，相邻的两个整数之间恰好隔一格。$3$ 和 $4$ 之间有实数 $3.5$，却没有另一个整数。于是，一个非负整数只要不是 $0$，就至少是 $1$；两个整数如果 $a>b$，那么就有 $a\geq b+1$。别小看这个“一格”的限制，许多证明会靠它把一种可能性彻底排除。

数轴向右，数变大。所以 $-2>-7$，虽然 $7>2$。若把它理解成气温，零下 $2$ 度比零下 $7$ 度高，就不容易把方向弄反。绝对值则暂时忽略方向，只记录这个数到 $0$ 的距离：

因此 $|-7|=7$，$|7|=7$，$|0|=0$。对非零整数 $a$，一定有 $|a|\geq1$；而 和 互为相反数，它们到零的距离相同。

数轴也解释了不等式的两条运算规则。在两边加同一个数，相当于一起平移，左右顺序不变；乘以正数，顺序也不变。乘以负数时，除了距离伸缩，还把方向翻转，因此不等号必须反向。例如由 $-3<2$，两边乘以 $-2$ 得到 $6>-4$。后面估计余数大小时，我们会频繁用到这些规则。

加减乘很自由，除法却常常出界

两个整数相加、相减或相乘，结果仍是整数。这叫作整数对加、减、乘运算的封闭性。“封闭”在这里没有神秘含义，只是说按这些规则计算，不会跑出整数集合。例如 $7-12=-5$，$(-3)\times8=-24$，结果依旧落在数轴的整数刻度上。

除法就不同了。$12\div3=4$ 仍是整数，$12\div5=2.4$ 却出界了。做普通计算时，写成小数已经回答了问题；如果问题是把 $12$ 个人分成每组 $5$ 人、每组都满员，小数就不能直接交差。整数的限制迫使我们关心：能分成几整组，还剩多少？这会把我们带到带余除法。

先把后面证明要用的运算规则放在一起。整数的加法和乘法都有交换律、结合律，乘法对加法有分配律：

它们允许我们换顺序、合并括号和提取公因子。减法则要先理解成加上相反数，即 $a-b=a+(-b)$，不能照搬加法的交换律。比如 $8-3=5$，$3-8=-5$，顺序一换，结果就变了。

负负得正，是怎样被运算规则要求出来的

“减去一个负数等于加上正数”，可以从相反数来理解：$-(-b)=b$，所以 $a-(-b)=a+b$。例如账户原来是 $-7$ 元，撤销一笔 $12$ 元的欠款，就是 元。

乘法中的符号规则也要和分配律相容。先看 $(-a)b$。因为

所以 $(-a)b$ 必须是 $ab$ 的相反数，即 $(-a)b=-ab$。再看

前一项已经是 $-ab$，后一项就必须是 $ab$。于是得到

这里没有另添一条任性的规定；一旦要求相反数和分配律同时成立，负负得正就跟着成立。实际计算时，$(-3)(-4)-5\times2=12-10=2$，先算乘法，再处理减法，符号便有了清楚的去处。

乘积等于零，能告诉我们什么

假如两个非零整数相乘，它们的绝对值都至少是 $1$，因此

乘积不可能等于 $0$。反过来说，如果 $ab=0$，就一定有 $a=0$ 或 $b=0$。我们把它叫作零乘积性质；它说的是“至少一个为零”，允许两个都为零。

由此还能得到消去规则：当 $c\neq0$ 时，若 $ca=cb$，移项后有 $c(a-b)=0$，所以 $a$，即 。条件 不能删，因为 并不意味着 。带余除法的唯一性证明最后也会用到这一步。

为什么总能挑出最小的那个

接下来我们需要一个看似普通、却很有用的事实。想象把某些自然数写在纸上：可能只有 $4,9,20$，也可能是所有不小于 $100$ 的自然数。只要确实写了至少一个数，总能指出其中最小的那个。

良序原理说：自然数集合的每一个非空子集，都有最小元素。 如果只讨论正整数，也同样成立。本课程把它作为整数的一项基本性质来使用。

“非空”保证集合里有东西可选；“自然数”保证不能无限向下走。比如集合 $\{100,101,102,\ldots\}$ 虽然无限，最小元素仍是 $100$。所以，无限不等于没有最小值。

但全体整数没有最小元素，因为任取整数 $a$，$a-1$ 还要小。正实数也没有最小元素，因为任取正实数 $x$，$x/2$ 仍然是正的，而且更小。这里的区别正是整数有一格一格的间隔；正实数则可以一直向零靠近。

更一般地，一个非空整数集合如果有整数下界 $L$，把每个元素都减去 $L$，就得到一个非空自然数集合。先找到后者的最小元素，再加回 $L$，就找到了原集合的最小元素。因此我们有时也会对“有下界的整数集合”使用良序思想。

良序原理为什么值得专门说？因为它给了我们一种证明办法：假如某件事有反例，就从反例中挑最小的那个；再设法推出还有更小的反例，于是产生矛盾。另一种用法则是先从所有候选结果里挑出最小值，再证明它必然满足要求。马上要讲的余数，就是第二种用法。

带余除法：剩下的必须不到一整组

把 $17$ 颗糖按每组 $5$ 颗来装，能装满 $3$ 组，剩 $2$ 颗。数量关系是

你也可以说“装了 $2$ 组，剩 $7$ 颗”，因为 $17=5\times2+7$ 也对。但这 $7$ 颗还能装一整组，所以它不是我们约定的最终余数。余数的要求，是不能再凑出一整组。

用字母表达：给定任意整数 $a$ 和正整数 $b$，存在唯一的一对整数 $q,r$，满足

这就是带余除法定理。$a$ 是被除数，$b$ 是除数，$q$ 是商，$r$ 是余数。因为 $r$ 是整数，它只能从 $0,1,\ldots,b-1$ 中选。除数 也允许，此时唯一可能的余数是 ；除数为 则不在定理范围内。

定理其实承诺了两件不同的事。“存在”保证无论给什么整数 $a$，都能找到合格的商和余数；“唯一”保证不会找到两组不同而又都合格的答案。先弄清楚负数怎么算，再分别证明这两个承诺。

负数的商，要把余数留在零的右边

$-13$ 除以 $5$，很容易写出

等式成立，余数 $-3$ 却不合格。我们把商从 $-2$ 减到 $-3$，乘积就减少了 $5$；为了维持等式，余数应增加 $5$，从 $-3$ 变为 $2$。于是

这次满足 $0\leq2<5$，因此商是 $-3$，余数是 $2$。数轴上，$-13$ 位于相邻的两个 $5$ 的倍数 $-15$ 和 $$ 之间；从左侧的 向右走 格，正好到达 。一般来说，商 确定的是这样一段区间：

再例如 $-23=7\times(-4)+5$，而 $-21=7\times(-3)+0$。负的被除数并不要求负的余数，能恰好除尽的负数余数也一样是 $0$。

这里先把除数限定为正整数，是为了让“每组多少个”的解释和余数范围保持一致。如果遇到负除数，也可以先对它的绝对值做带余除法，再改变商的符号。例如 $17=5\times3+2$ 对应 $17=(-5)\times(-3)+2$，余数仍是 $2$。一般写法是 、，但仍须要求 。之后没有特别说明时，我们继续使用正除数的版本。

为什么一定存在

固定整数 $a$ 和正整数 $b$，把所有形如 $a-bk$ 的非负整数收集起来，其中 $k$ 可以取任意整数：

这些是“减掉若干个 $b$ 后，尚未走到零左侧”的候选余量。先确认 $S$ 非空。如果 $a\geq0$，取 $k=0$ 就得到 $a\in S$。如果 $a<0$，取 ，由于 ，有

所以负数情形也至少有一个候选余量。现在 $S$ 是非空自然数集合，良序原理保证它有最小元素，记作 $r$。按集合的定义，某个整数 $q$ 使得 $r=a-bq$，也就是 $a=bq+r$。

剩下只需要证明 $r<b$。假如 $r\geq b$，我们就还能再减去一个 $b$：

这个数仍在 $S$ 中，却比 $r$ 小，与 $r$ 是最小元素矛盾。因此假设不成立，必有 $0\leq r<b$。存在性得证，而且整个过程已经包含了负数和零。

为什么答案只能有一组

假设同一个 $a,b$ 有两种合格写法：

两式相减，得到

两个余数都在 $0$ 到 $b-1$ 之间，所以 $|r'-r|<b$。如果 $q\neq q'$，整数 的绝对值就至少是 ，从而

等号左边绝对值至少是 $b$，右边却小于 $b$，不可能相等。因此 $q=q'$，再代回便有 $r=r'$。唯一性也证完了。

回头看，余数上界 $r<b$ 恰好排除了“少装一组、多剩一整组”的可能；下界 $r\geq0$ 则排除了“多装一组、欠几颗”的可能。定理把分组的直觉变成了对所有整数都可靠的规则。

回到开头：正方形为什么不会剩两颗

把任意整数 $n$ 除以 $2$，余数只能是 $0$ 或 $1$。所以它必然且只能属于下面两类之一：

第一类叫偶数，第二类叫奇数。存在性保证两类已经包括所有整数，唯一性保证一个数不能同时是两类。$0=2\times0$ 是偶数，负数也能分类，比如 $-5=2\times(-3)+1$ 是奇数。

现在考察平方。如果 $n=2k$，则

所以除以 $4$ 的余数是 $0$。如果 $n=2k+1$，则

所以除以 $4$ 的余数是 $1$。所有整数只有偶数和奇数两种情况，两种已经检查完，结论便对每一个整数成立：整数平方除以 $4$，余数只能是 $0$ 或 $1$。

这就是开头棋子问题的答案。我们没有计算更大的正方形，而是找到一个能把所有整数分完的办法。顺便还能判断：$102$ 不可能是整数的平方，因为 $102=4\times25+2$，余数为 $2$；无须挨个平方试算。

但反过来要小心。$21=4\times5+1$，它的余数符合要求，却不是平方，因为 $4^2<21<5^2$。“平方一定符合这个余数要求”不等于“符合这个要求的一定是平方”。在数论里，一条条件常常能帮我们排除不可能，却未必能保证剩下的都可能。

数学归纳法：怎样把有限的推理送到无限远

刚才的证明靠两类情况覆盖所有整数。另一些规律会随着 $n$ 一步步增长，例如前 $n$ 个正整数的和。算出前几个结果，可以猜到

要证明所有正整数都满足它，我们可以找到相邻两种情况的联系：前 $k+1$ 个数的和，就是前 $k$ 个数的和再加上 $k+1$。这意味着，假如知道第 $k$ 步成立，就有机会把它传递到第 $k+1$ 步。

数学归纳法正是把这种传递组织成证明。用 $P(n)$ 表示一个关于整数 $n$ 的命题。若要证明从某个整数 $n_0$ 开始的所有 $P(n)$，需要完成两件事：先证明起点 $P(n_0)$ 成立；再对任意 ，证明“如果 成立，那么 也成立”。两者合起来，才能推出所有 的结论。

骨牌的比喻很贴切：第一张确实倒下，而且任意一张倒下都会推倒下一张，连锁就会继续。但比喻不能替代证明。我们用良序原理，把“不会有遗漏”说清楚。

假如结论没有覆盖所有 $n\geq n_0$，反例组成的非空整数集合有下界 $n_0$，因而存在最小反例 $m$。由于起点成立，$m$ 不可能等于 $$，所以 。它比最小反例还小，故 成立；归纳步骤随即推出 成立，与 是反例矛盾。因此反例不存在，归纳法是可靠的。

把求和公式完整地证明一次

先看起点 $n=1$：左边是 $1$，右边 $1\times2/2=1$，公式成立。

接着任取正整数 $k$，假设

这里的假设仅用于证明一个条件关系，并不是直接宣布所有情况都正确。我们要做的，是在这个前提下走通下一步。前 $k+1$ 项的和满足

最后的式子正是把原公式里的 $n$ 换成 $k+1$ 后应得到的结果。起点和传递都已证明，由数学归纳法，公式对所有正整数 $n$ 成立。例如前 $80$ 个正整数的和就是 $80\times81/2=3240$。

起点和传递，各自堵住一种漏洞

如果漏掉起点，只证明“这一项成立就能推出下一项”，可能整条链根本没有开始。例如错误命题 $1+2+\cdots+n=n(n+1)/2+1$，也能通过两边加 $n+1$ 的方式传递到下一项，但它在 $$ 时就是错的。

如果只验证起点和前几十项，又没有证明对任意 $k$ 的传递，则仍然只是有限次检查。比如 $n^2-n+11$ 在 $n=1,2,3$ 时分别得到 $11,13,17$，这几个数不能拆成两个大于 的正整数相乘；可到 ，结果却是 。再整齐的开头也不能代替证明。

有时下一步需要用到前面好几步，而不只是紧挨着的一步。这时可以采用强归纳法：证明起点后，在归纳步骤中假设从起点到 $k$ 的命题全部成立，再推出 $P(k+1)$。它仍然由同一个最小反例论证保证正确，因为最小反例之前的所有情况都成立。后面讨论整数能否不断拆成更小因数时，这种写法会更顺手。

留几道题，自己走完推理

练习一：整数运算的条件。 计算 $(-8)\times5+(-3)\times(-6)$，并说明为什么从 $c(a-b)=0$ 推出 $a=b$ 时必须要求 。

练习二：商和余数要一起验算。 写出 $47$、$-47$、$0$ 分别除以 $6$ 的商和非负余数。再解释为什么 $-47=6\times(-7)-5$ 不能算作合格答案。

练习三：用分类代替试算。 证明任意整数 $n$ 的平方除以 $3$，余数只能是 $0$ 或 $1$；据此判断 $2027$ 是否可能是整数的平方。

练习四：平方和公式。 用数学归纳法证明，对每个正整数 $n$ 都有

练习五：归纳法也能证明不等式。 证明对所有自然数 $n$，都有 $2^n\geq n+1$。这里从 $n=0$ 开始。

练习六：最小值和下界不是同一回事。 所有不小于 $-8$ 的偶数组成的集合有没有最小元素？所有正实数组成的集合呢？说明良序原理能否用于这两个集合。

现在再看 $a=bq+r$，你应该能同时读出分组的直觉、余数的限制，以及存在性和唯一性各自需要什么理由。接下来的问题自然落在 $r=0$ 上：如果一颗也不剩，$a$ 和 $b$ 之间会有什么特殊关系？这种“分得干干净净”的关系就是整除。下一章将从这里出发，研究因数如何组合，以及怎样不做完整除法就判断一个数能否被另一个数整除。

对应的商、余数是 $(7,5)$、$(-8,1)$、$(0,0)$。等式逐一成立，余数也都在 $0$ 到 $5$ 之间。题目最后的等式虽然数值正确，但余数为 $-5$，不满足非负条件；把商减少 $1$，余数增加 $6$，就变成正确的 $(-8,1)$。

三式已经写成合法的带余除法形式，余数分别是 $0,1,1$。因此平方不会余 $2$。由于 $2027=3\times675+2$，它不可能是整数的平方。

最后一步使用 $2k^2+7k+6=(k+2)(2k+3)$。结果正是 $n=k+1$ 时的公式，归纳步骤成立。因此由数学归纳法，公式对所有正整数 $n$ 成立。

最后一个不等式来自 $k\geq0$。而 $k+2=(k+1)+1$，恰好是下一步所需的右边。起点和归纳步骤都成立，故结论对所有自然数成立。