几个精彩的数论问题.doc

几个精彩的数论问题从同事那里借来了一本单墫教授主编的初等数论奥数书，看到很多精彩的问题，在这里做个笔记，与大家一同分享。不少问题和答案都有过重新叙述，个别问题有所改动。问题：找出所有使得 2n - 1 能被 7 整除的正整数 n 。答案：由于 2n 的二进制表达为 100000 （n 个 0），因此 2n - 1 的二进制表达为 11111 （n 个 1）。而 7 的二进制表达是 111 ，要想让它整除 n 个 1 ，显然 n 必须是也只能是 3 的倍数。问题：是否存在 100 个数，使得它们的和等于它们的最小公倍数？答案：是的。考虑 3, 2 3, 2 32 , 2 33, , 2 398, 399 ，它们的和为：3 + 2 3 + 2 32 + 2 33 + + 2 398 + 399= 3 (1 + 2) + 2 32 + 2 33 + + 2 398 + 399= 32 + 2 32 + 2 33 + + 2 398 + 399= 32 (1 + 2) + 2 33 + + 2 398 + 399= 33 + 2 33 + + 2 398 + 399= . .= 399 + 399= 2 399而这 100 个数的最小公倍数正是 2 399 。问题：能否找出 100 个不同的正整数，使得其中任意 2 k 100 个数的算术平均数都恰为整数。答案：能。这个问题非常唬人，它的答案异常简单： 1 100!, 2 100!, 3 100!, , 100 100! 显然满足要求。问题：求证，存在任意长的连续正整数，使得其中任何一个数都不是质数的幂（当然更不能是质数）。答案。有一个经典的问题是，求证存在任意长的连续正整数，它里面不包含任何质数。换句话说，相邻质数的间隔可以达到任意大。构造的方法堪称经典。显然 n! + 2 是 2 的倍数（因为我们可以提出一个 2 来）， n! + 3 是 3 的倍数，等等。因此， n! + 2, n! + 3, n! + 4, , n! + n 就是 n - 1 个连续的正整数，其中任意一个数都不是质数。由于 n 可以任意大，因此这个数列可以任意长。现在，我们要证明的是一个更强的结论。我们可以把刚才的构造方案简单地修改一下。只需要考虑 (n!)2 + 2, (n!)2 + 3, (n!)2 + 4, , (n!)2 + n ，则其中每一个数都不是质数的幂。比如说 (n!)2 + 5 ，显然它是 5 的倍数，因为我们可以提出一个 5 来；然而提出一个 5 之后将会得到 5 (12 22 32 42 5 62 n2 + 1) ，括号里的数显然不再是 5 的倍数，它除以 5 余 1 。利用中国剩余定理，我们还能给出另一种非常巧妙的构造方案，它能找出 n 个不含质数幂的连续正整数数列，其中 n 可以任意大。我们只需要保证，每个数都含有至少两个不同的质因数即可。取 2n 个不同的质数 p1, p2, , pn, q1, q2, , qn ，显然 p1 q1, p2 q2, , pn qn 是两两互质的 n 个数。由中国剩余定理，我们能找到一个正整数 M ，使得 M 除以 p1 q1 余 1 ，并且 M 除以 p2 q2 余 2 ，并且 M 除以 p3 q3 余 3 ，一直到 M 除以 pn qn 余 n 。于是， M - 1, M - 2, M - 3, , M - n 就是 n 个连续的正整数，其中每一个都含有两个不同的质因数。问题：求证，对于任意大的 n ，我们都能够找出 n 个两两互质的数，使得任意 2 k n 个数之和都不是质数答案：如果只要求任意多个数之和都不是质数，这很好办：让所有数都是某个数的倍数即可。但是，如果这些数必须两两互质，同样的要求还能办到吗？可以的。考虑 n! + 1, 2 (n!) + 1, 3 (n!) + 1, , n (n!) + 1 这 n 个数，显然任意 k 个数之和都是 k 的倍数，因而不是质数。下面说明这 n 个数两两互质。假设 i (n!) + 1 和 j (n!) + 1 有公共的质因数 p ，其中 1 i j n ，那么它们的差 (j - i) (n!) 也能被 p 整除，说明 p 只能是不超过 n 的质数。这与 p 能整除 i (n!) + 1 矛盾。问题：证明，对于任意正整数 n ，方程 x2 + y2 = zn 都有无穷多组正整数解。答案：考虑 x + yi = (a + bi)n ，其中 i 为虚数单位。对于每一个固定的 n ，只要 a 和 b 都是整数，那么展开后得到的 x 和 y 也都一定是整数。我们选取充分大的 a ，让 a + bi 的辐角非常小非常小（小于 /2 的 n 分之一），从而让 (a + bi)n 不会与坐标轴重合，因而保证 x 和 y 都是非零整数。等式两边同时取模，便有 x2 + y2 = (a2 + b2)n问题：我们把平面直角坐标系上所有横纵坐标互质的整格点（也就是和原点的连线不经过其他点的整格点）叫做“既约格点”。证明，对于任意大的正整数 n ，总存在一个整格点，它到任意既约格点的距离都大于 n （换句话说，既约格点集的“空洞”可以达到任意大）。答案：列一张 (2n + 1) (2n + 1) 的表，每个格子里面填写一个不同的质数（由于质数无穷多，这是总可以办到的）。现在，找出这样的一个 a ，它除以第 i 行的质数总是余 i （其中 - n i n ）。找出这样的一个 b ，它除以第 j 列的质数总是余 j （其中 -n j n）。中国剩余定理保证了这样的 a 和 b 是存在的。下面说明，点 (a, b) 满足要求。假如 (a, b) 到 (x, y) 的距离不超过 n ，则 (a - x)2 + (b - y)2 n2 。因而， a - x 和 b - y 都必须在 - n 到 n 的范围内。把 a - x 的值记作 i ，把 b - y 的值记作 j ，那么 x 就等于 a - i ， y 就等于 b - j ，由 a 、 b 的构造可知， x 和 y 都是表格中第 i 行第 j 列的那个质数的倍数，故 (x, y) 不是既约格点。问题：找出所有这样的正整数序列 (a1, a2, , an) ，它们的和为 2n ，但我们无法把它们分成和相等的两组。答案：考虑 a1, a2, a1 + a2, a1 + a2 + a3, , a1 + a2 + a3 + + an ，除了 a1 和 a2 以外，这些数除以 n 的余数不允许相等，否则它们的差就是 n 的倍数，我们就找到了和为 n 的子集。然而，上面一共有 n + 1 个数，它们除以 n 的余数必然有相等的，因而一定是 a1 和 a2 除以 n 的余数相等。类似地， a2 和 a3 除以 n 的余数也相等， a3 和 a4 除以 n 的余数也相等，因而事实上从 a1 到 an 所有的数除以 n 的余数都是相等的。但是这 n 个数加起来只有 2n ，可见所有的数除以 n 的余数只可能都是 1 或者都是 2 。于是我们得到了所有满足要求的数列： (1, 1, 1, , 1, n + 1) ，以及 (2, 2, 2, , 2) 。其中后者要求 n 为奇数。问题：证明，存在无穷多个正整数三元组 (a, b, c) ，使得 a2 + b2 、 b2 + c2 、 a2 + c2 都是完全平方数。答案：任取一组勾股数 (x, y, z) ，令 a = x|4y2 - z2| ， b = y|4x2 - z2|， c = 4xyz 。于是，a2 + b2 = x2(3y2 - x2)2 + y2(3x2 - y2)2= x6 + 3x2y4 + 3x4y2 + y6=(x2 + y2)3 = (z3)2a2 + c2 = x2(4y2 + z2)2b2 + c2 = y2(4x2 + z2)2从而 a 、 b 、 c 满足要求。由于勾股数有无穷多组，因此满足要求的 (a, b, c) 也有无穷多组。这相当于给出了 Euler 砖块（所有棱长和所有面对角线都是整数的长方体）的一种构造解。当 (x, y, z) = (3, 4, 5) 时，我们将得到棱长分别为 117 、 44 、 240 的 Euler 砖块，这就是最小的 Euler 砖块，它是由 Paul Halcke 在 1719 年发现的。大家或许会想，有没有什么长方体，不但所有棱长和所有面对角线都是整数，连体对角线也是整数呢？这样的长方体就叫做完美长方体。有趣的是，虽然 Euler 砖块有无穷多种，但是人们目前还没有找到哪怕一个完美长方体。完美长方体究竟是否存在，目前仍然是一个未解之谜。问题：证明，若正整数 a 和 b 互质，则 b / a + 2b / a + 3b / a + + (a - 1) b / a = (a - 1)(b - 1) / 2 。其中， n 是 n 的整数部分，即对 n 取下整。答案：我们先举一个例子来说明这个问题的复杂性。数列 b / a, 2b / a, 3b / a, , (a - 1) b / a 的规律并不一定非常明确。例如，当 a = 17 且 b = 12 时， 12 / 17, 2 12 / 17, 3 12 / 17, 16 12 / 17 分别为 0, 1, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 9, 10, 11 ，但这 16 个数之和为 88 ，正好是 16 和 11 乘积的一半。结论的证明很有意思。在平面直角坐标系的第一象限摆放一个宽为 a ，高为 b 的矩形。则 k b / a 就是图中第 k 条红色竖直线上的整格点数目，所有 k b / a 之和也就是阴影三角形内的整格点总数。然而由于 a 和 b 互质，矩形的对角线不会经过矩形内部的任何格点，因此阴影三角形内的整格点数就应该是矩形内的整格点数的一半，即 (a - 1)(b - 1) / 2。问题：若正无理数 和 满足 1 / + 1 / = 1 ，求证数列 1 , 2 , 3 , 和 1 , 2 , 3 , 既无重复又无遗漏地包含了所有的正整数。这里 同样是取下整的意思。答案：让我们先来看一个例子吧。考虑黄金比例 = (5 + 1) / 2 1.618 ，我们有 1 / + 1 / ( + 1) = 1 。数列 1 , 2 , 3 , 为 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, ，而数列 1 ( + 1), 2 ( + 1), 3 ( + 1), 则为 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 。你会发现，前一个数列里没有的数，正好都在后一个数列里，而后一个数列里没有的数，前一个数列里正好都有。两个数列合在一起，就是整个正整数序列。这个定理叫做 Beatty-Rayleigh 定理，它有很多种证明，其中两种证明参见 Wikipedia 。这里给出一种我非常喜欢的证明，它出自 Using your Head is Permitted 。首先注意到，如果 x 和 y 都不是整数，那么 x 严格地小于 x ，y 严格地小于 y ，从而 x + y 1 ，后两个数列里恰好有一个数是 n 位数。这是为什么？答案：这是 Beatty-Rayleigh 定理的一个非常漂亮的直接推论。 10k 的二进制表达恰好有 log210k + 1 位，即 k log210 + 1 位。10k 的五进制表达恰好