Sierpiński 的初等数论问题

2015-08-01 18:35:39 暂无评论阳光倾城应用数学 5,991

是否存在四个连续正整数，使得它们都是乘方数？这里，“乘方数”的意思和上题一样，即形如 n^k 的数，其中 n 、 k 都是正整数，且 k > 1 。

不存在。在任意四个连续正整数中，必然有一个数是形如 4k + 2 的数。这样的数能被 2 整除，却不能被 4 整除，因而永远不可能是一个乘方数。

那么，是否存在三个连续正整数，使得每一个数都是乘方数呢？ 1962 年， A. Mąkowski 证明了，这也是不可能的，不过证明过程就没那么简单了。那么，是否存在两个相邻的正整数，使得它们都是乘方数呢？这次就有了，例如 8 = 2³, 9 = 3² 。1844 年， Eugène Catalan 猜想，除了 8 和 9 以外，没有别的相邻乘方数了。 2002 年，这个猜想终于被 Preda Mihăilescu 证明。

31, 331, 3331, 33331 都是质数。难道数列 31, 331, 3331, 33331, … 中的所有数都是质数吗？其实并不是这样。证明：数列 31, 331, 3331, 33331, … 中含有无穷多个合数。

数列的通项公式是 (10^{n + 1} – 7) / 3 。容易验证， 10¹, 10², …, 10¹⁷ 除以 17 的余数分别是

10, 15, 14, 4, 6, 9, 5, 16, 7, 2, 3, 13, 11, 8, 12, 1, 10

其中 10¹⁷ 和 10¹ 除以 17 的余数相同，因此再往后， 10 的乘方除以 17 的余数便会开始循环，循环节的长度为 16 。由于 10⁹ 除以 17 余 7 ，这就说明所有的 10^{16k + 9} 除以 17 都余 7 。因此，所有的 (10^{16k + 9} – 7) / 3 都是 17 的倍数。

事实上， 31, 331, 3331, 33331, 333331, 3333331, 33333331 都是质数，首次出现的合数为 333333331 = 17 × 19607843 ，这正是 k = 0 时 (10^{16k + 9} – 7) / 3 的值。我们自然会问，除了所有的 (10^{16k + 9} – 7) / 3 以外，数列 31, 331, 3331, 33331, … 当中还有别的合数吗？答案是，确实还有。用和刚才类似的方法可以推出，所有的 (10^{18k + 12} – 7) / 3 都能被 19 整除，例如 (10¹² – 7) / 3 = 333333333331 = 19 × 83 × 211371803 。其实，数列 31, 331, 3331, 33331, … 里的质数没那么多。在前 100 项中，只有第 1, 2, 3, 4, 5, 6, 7, 17, 39, 49, 59, 77, 100 项是质数。

247 的各位数字之和是 13 ，正好 247 也是 13 的倍数。 399 的各位数字之和是 21 ，正好 399 也是 21 的倍数。是否对于任意正整数 s ，我们都能找到一个正整数 N ，使得 N 的各位数字之和为 s ，并且它也正好是 s 的整倍数？

答案是肯定的。把 s 表示成 2^α · 5^β · t 的形式，其中 t 里面不再含有因数 2 和 5 。根据 Euler 定理， 10^φ(t) 除以 t 余 1 。现在，令 N = 10^{α + β} · (10^φ(t) + 10^{2 · φ(t)} + … + 10^{s · φ(t)}) ，则 N 就是一个满足要求的数。首先， N 的十进制表达中含有 s 个数字 1 ，其余的数字全是 0 ，因而它的各位数字之和确实是 s 。另外，上式括号里一共有 s 项，其中每一项除以 t 都余 1 ，因此它们的和除以 t 就余 s ；而 s 是 t 的整倍数，除以 t 余 s 也就相当于是除以 t 余 0 了。这说明，上式括号的计算结果是 t 的整倍数。再加上 10^{α + β} 显然是 2^α · 5^β 的整倍数，于是便得到了 N 是 s 的整倍数。

证明：当 n 趋于无穷时， 2ⁿ 的各位数字之和也将随之趋于无穷。

下面这个证明是由 Andrzej Schinzel 给出的。我们先来定义一个数列 a₀, a₁, a₂, … ，其中 a₀ = 0 ，并且 a_{i + 1} 为最小的使得 2^{a_{i + 1}} 大于 10^a_i 的正整数。在所有 2 的乘方中，最小的比 10⁰ 更大的是 2 的 1 次方，因此 a₁ = 1 ；在所有 2 的乘方中，最小的比 10¹ 更大的是 2 的 4 次方，因此 a₂ = 4 ；在所有 2 的乘方中，最小的比 10⁴ 更大的是 2 的 14 次方，因此 a₃ = 14 ……容易看出， a₀₁₂

下面我们来证明，如果 n 大于等于某个 a_k ，那么 2ⁿ 的右起第 a_{k – 1} + 1 到第 a_k 位里至少有一个非 0 数字。不妨让我们以 k = 3 为例来说明这一点，你会发现下面的推理过程适用于一切其他的 k 。当 k = 3 时，我们要证明的就是，如果 n ≥ a₃ = 14 ，那么 2ⁿ 的右起第 a₂ + 1 = 5 位到第 a₃ = 14 位里至少有一个非 0 数字。反证，假设 2ⁿ 等于 abc0000000000defg ，其中 a 、 b 、 c 、 d 、 e 、 f 、 g 都是一位数字。注意到 2 的任何乘方的个位都不可能是 0 ，这说明 g 肯定不为 0 。由于 2¹⁴ 可以整除 10¹⁴ ，因而 2¹⁴ 可以整除 abc00000000000000 ；由于 n 大于等于 14 ，因而 2¹⁴ 也可以整除 2ⁿ = abc0000000000defg 。所以， 2¹⁴ 必然能整除 abc0000000000defg – abc00000000000000 = defg 。虽然 d 、 e 、 f 都可能为 0 ，但我们刚才说过， g 是肯定不为 0 的，因而 defg 是一个最多 4 位的正整数。但是，2¹⁴ 能整除一个最多 4 位的正整数，这是不可能的，因为根据数列 a_i 的定义， 2¹⁴ > 10⁴ ，也就是说 2¹⁴ 至少有 5 位数，它不可能整除一个比自己小的正整数。

所以，如果 n 大于等于某个 a_k ，那么 2ⁿ 的右起第 a_{k – 1} + 1 到第 a_k 位里至少有一个非 0 数字。事实上，如果 n 大于等于某个 a_k ，那它也大于 a₁, a₂, …, a_{k – 1} ，因而对于所有不超过 k 的正整数 i 来说， 2ⁿ 的右起第 a_{i – 1} + 1 到第 a_i 位里都含有至少一个非 0 数字。可见， 2ⁿ 里至少有 k 个非 0 数字，即它的各位数字之和至少为 k 。这表明，随着 n 的增加， 2ⁿ 的各位数字之和可以达到任意大。我们的结论也就证到了。