说几个数论中的经典问题

luyuanhong

说几个数论中的经典问题

作者 | 刘瑞祥

来源 | 说短论长

编辑 | 遇见数学

本文原创性很低，但是我希望大家读了以后能“真的”读懂，切实理解其中道理，而不是囫囵吞枣。本文涉及初等数论的三个非常重要的定理（算法），均出自《几何原本》。

一、预备知识



如果两个数都能被第三个数整除，则这两个数的和、差一定能被第三个数整除；如果两个数有且只有一个能被第三数整除，则这两个数的和、差一定不能被第三个数整除。

二、辗转相除法的原理

设有两个数 a 、b ，欲求其最大公约数，可以用大数除以小数，取其余数（肯定小于一开始的较小数，我们不妨称这一步得到的余数是第一余数），再以开始所给的较小数除以第一余数，再取余数（即第二余数），以后以第一余数除以第二余数达到第三余数，第二余数除以第三余数得到第四余数……直至余数为 0 时，上一次的余数即为初始两个数的最大公约数。



例：设初始的两个数为 96 和 27 ，以 96 除以 27 得到第一余数为 15 ，再以 27 除以 15 得到第二余数为 12 ，以 12 除以 12 得到第三余数为 3 ，因为 12 能被 3 整除，所以 3 是最大公约数。

→ 96 和 27 的最大公约数是 3 。

道理很简单：a÷b 取余数，其实可以看做从 a 里连续减去 b 直到减不开为止。而公约数 c（姑且不管是不是最大）是 a 和 b 共同的约数，即 a 、b 都是 c 的倍数，所以从 a 中连续减去 b ，两个同为 c 倍数的数做减法，得到的余数（这里是第一余数）当然还是 c 的倍数，此即前面提到的预备知识。以后辗转进行下去，每一次得到的余数当然也还是 c 的倍数。直到得到这个 c ，也就是整除了。

那为什么是最大公约数呢？因为如果不是最大的，换句话说就是还有更大的，比如是 c' 。那么这个 c' 就在前面的过程中被“跳过去”了。那么显然就违背了预备知识。因为本来任何一步里两个数的全部约数都满足预备知识，结果这么一来肯定有的不满足了。

以上就是著名的欧几里得算法，只不过当年欧几里得用词远比这严谨。这个算法有什么用呢？它比起小学学的短除法，最大的好处是不用一个个的尝试某个数是不是公约数。短除法对于大数很麻烦，比如求 1001 和 234 的最大公约数需要一个个尝试，如果给的两个数更大，特别是两个数的公共质因数很大，就更麻烦（最近一位老师让学生计算 38 和 57 的最大公约数，许多学生就算不出来）。另外用辗转相除法还可以立刻得出一个结论：相差为 1 的两个正整数互质。

三、最大公约数和最小公倍数的关系

这个关系很简单：两个数的最大公约数和最小公倍数，二者的乘积等于原来两个数的乘积。



首先我们看两个互质数的情况：互质数的最大公约数就是 1 ，最小公倍数就是这两个数的乘积，显然符合这个关系，但是任意两个正整数呢？

要理解这个关系也不难，假设两个数 a、b 的最大公约数是 c ，即 a=ca' ，b=cb' ，则显然 ab=ca'cb'=c(ca'b') ，而括号里的 ca'b' 恰好就是最小公倍数。如果还有人觉得不放心，可以回忆一下短除法的计算过程：对于两个数的情况，“侧面的”乘在一起就是最大公约数 c ，侧面的和“底下的”乘在一起（无论计算最大公约数还是最小公倍数，侧面的只取一次）就是最小公倍数 ca'b' 。

四、质数有无穷多个的证明

这个定理有很多证明方法，但最简单的是这个：假设质数是有限的，将全部各个质数乘起来再加 ，则这个新得到的数肯定和全部质数的乘积互质，即不能被已有的各个质数整除，所以是一个新的质数。这就和前面矛盾了。



大家要注意，这里并不是说若干质数乘起来再加 1 一定会得到新的质数，实际上也可能得到一个能被其它质数整除的合数。比如 2×3+1 、2×3×5+1 都是质数，而 2×3×5×7×11×13+1 却不是，它是 59 的倍数，注意 59 不是 2 、3 、5 、7 、11 、13 中的任何一个。你可能认为得到合数的情况非常罕见，其实不然，你可以按照上面的规律继续算几个，只不过即使得到的是合数，其约数往往也比较大。

用连续相乘的方法还可以求任意长度的连续合数数列。比如我要生成连续 5 个合数，就可以先计算出 1×2×3×4×5×6 ，然后用这个结果加 2 、加 3 、加 4 一直到加 6 ，因为 1×2×3×4×5×6 含有 2～6 的每个因子，所以加 2 就是 2 的倍数，加 3 就是 3 的倍数，如此等等。可以想见，用这样的方法得到连续的千百万个合数也是没有问题的。但是这样得到的数列肯定不会是最小的，即以此题为例，实际上在这之前我们就有 90～96 连续七个合数，而更前面还有 24～28 、32～36 、48～52 、54～58 、62～66 、74～78 、84～88 等多个连续的五合数数列。另外不但从 1 乘到 6 加 2 直至加 6（122～126）是合数，而且 122 前面还有 114～121 也都是合数，也就是说 114～126 连续十三个数都是合数。

一方面质数是无穷无尽的，另一方面连续的合数数列可以要多长有多长，多么神奇的数学。

另外我要说一点：初等数论在小学数学中是非常特别的内容，它的计算和小学数学其它部分明显不同，主要是对逻辑的要求比较高，如果只让学生机械地记忆和应用这些内容，那就太可惜了。虽然谁出的卷子都不要求学生写算理，但是算理最重要。至于有的老师总觉得学生不一定能理解其中的道理，那我只能说：如果你不去发展学生的思考能力，那学生就永远也无法发展思考能力，思考能力的发展是长期而艰巨的，但不可缺少。为什么五年级学生理解不了被 3 整除数的特性？因为他四年级的时候没有发展相应能力，四年级时为什么没有发展起来？因为他三年级时……老师总是告诉学生最后的结论，如同厨子总是把菜做好了再端上来，顾客是不会学会做菜的。