你在这里

Sierpiński 的初等数论问题

波兰数学家 Wacław Sierpiński 对数论有很多研究。在他一生出版的 50 多本书里, 250 Problems of Elementary Number Theory 一书显得格外有趣。这里面不但有各种出人意料的数学事实,还有很多精妙的证明和大胆的构造,让人大呼过瘾。我从中选择了一些问题,在这里和大家一块儿分享。下面的文字没有完全照搬书中的内容,而是做了大量的改动和扩展;若有出错的地方,还请大家指正。个别题目会涉及一些初等数论中的著名定理,它们都可以在这篇文章里找到。
 
找出所有的正整数 n ,使得 n2 + 1 能被 n + 1 整除。
满足要求的解只有一个: n = 1 。原因很简单:如果 n2 + 1 = n(n + 1) – (n – 1) 是 n + 1 的整倍数,那么 n – 1 也必须是 n + 1 的整倍数,这只有一种可能性,即 n – 1 = 0 。
 
证明:对于任意大于 6 的偶数 n ,我们都能找到两个质数 p 和 q ,使得 n – p 和 n – q 互质。
不管 n 是多少,令 p = 3, q = 5 即可。这样一来, n – p 和 n – q 就是两个相邻的奇数,它们必然互质。
 
找出所有公差为 100 的等差数列,使得里面的所有项都是质数。
满足要求的等差数列不存在。这是因为,在 p, p + 100, p + 200 这三个数当中,至少有一个数能被 3 整除,因而 p 只能等于 3 。此时, p + 200 = 3 + 200 = 203 = 7 × 29 ,这就说明满足要求的等差数列不存在。
 
找出所有这样的质数,它既能表示成两个质数之和,也能表示成两个质数之差。
满足要求的数只有 5 ,它可以表示成 3 + 2 和 7 – 2 。下面我们证明,这个问题没有别的解了。如果质数 r 能表示成两个质数之和,那么显然 r > 2 ,因而 r 只能是奇数。两个质数之和是一个奇数,则其中一个质数一定是 2 ;两个质数之差是一个奇数,则其中一个质数也一定是 2 。因此, r 只有可能被表示成 p + 2 和 q – 2 ,其中 p 和 q 都是质数。这说明, p, r, q 是三个连续奇数。三个连续奇数当中,必然有一个能被 3 整除。如果它们都是质数,那么一定有一个数就是 3 。因此, (p, r, q) = (3, 5, 7) 是唯一的可能。
 
33 = 3 × 11 , 34 = 2 × 17 , 35 = 5 × 7 。它们组成了三个连续的正整数,其中每个数都是两个不同的质数之积。是否存在四个连续的正整数,使得每个数都是两个不同的质数之积?
不存在。任意四个连续的正整数中,一定有一个能被 4 整除,它显然不是两个不同的质数之积。
 
证明:方程 xy + x + y = 232 存在正整数解。
原方程相当于 xy + x + y + 1 = 232 + 1 ,即 (x + 1) · (y + 1) = 225 + 1 ,而后者是 n = 5 时的 Fermat 数,众所周知,它是能被分解成两个大于 1 的整数之积的。
 
证明:方程 x2 + y2 + 1 = z2 有无穷多组正整数解。
对于任意正整数 n , (2n)2 + (2n2)2 + 1 = (2n2 + 1)2 都成立。
 
证明:对于任意一个无限小数(不一定是无限循环小数),我们都能找到一个任意长的数字串,使得它会在这个无限小数的小数展开当中出现无穷多次。
令 m 为任意大的正整数。把小数点后的数字每 m 位分成一组,从而得到无穷多个 m 位数字串。由于不同的 m 位数字串只有 10m 种,因而必然有一种数字串会出现无穷多次。
 
证明:对于任意正整数 m ,总存在一个关于 x 和 y 的整系数方程 ax + by = c ,使得方程恰好有 m 个正整数解。
不管 m 是多少,令 c = m + 1 ,则方程 x + y = c 满足要求。这个方程显然有且仅有 m 个解,它们分别是 (1, m), (2, m – 1), …, (m, 1) 。
 
证明:对于任意正整数 m 、 n ,总存在一个关于 x 和 y 的整系数方程 ax + by = c ,使得 x = m, y = n 是方程的唯一正整数解。
令 a 和 b 为两个不同的大于 m + n 的质数,令 c = am + bn ,则方程 ax + by = c 满足要求。为什么呢?不管是 x ≥ m, y > n ,还是 x > m, y ≥ n ,都会使得 ax + by > am + bn = c 。所以,如果方程有不同的正整数解,则要么 x < m ,要么 y < n 。如果 x < m 的话,那么 m – x 就是一个小于 m 的正整数。注意到 by = c – ax = am + bn – ax = a(m – x) + bn ,其中 by 是 b 的倍数, bn 是 b 的倍数,因而 a(m – x) 也是 b 的倍数;但 a 和 b 是两个不同的质数,于是 a(m – x) 是 b 的倍数就意味着 m – x 是 b 的倍数。但这是不可能的,因为 m – x < m < b 。用类似的方法可以说明, y < n 也是不可能的。
 
给出一个多项式 f(x) ,它可以被分解成两个因式的乘积,但却存在 100 个不同的正整数,使得每一个数代入 f(x) 后,得到的值都是一个质数。
假设 p1, p2, …, p100 是 100 个不同的质数,则多项式
f(x) = [(x – p1)(x – p2)…(x – p100) + 1] · x
显然满足要求。当 x 取 p1, p2, …, p100 时, f(x) 的值分别为 p1, p2, …, p100 ,它们都是质数。
 
如果 f(x) 是一个整系数多项式,那么 f(x) = 0 有整数解,就意味着对于所有的质数 p , f(x) = 0 (mod p) 也都有整数解。这个命题反过来成立吗?如果某个整系数多项式 f(x) 满足,对于所有的质数 p , f(x) = 0 (mod p) 都有整数解,那么 f(x) = 0 也一定有整数解吗?这里, f(x) = 0 (mod p) 的意思是,如果只看 f(x) 除以 p 的余数,则在这个意义下它等于 0 。
4x + 2 = 0 显然没有整数解,但对于任意质数 p ,4x + 2 = 0 (mod p) 都有整数解。当 p = 2 时,任何 x 都是一个解;当 p 为其他质数时, p 必然具有 2k + 1 的形式,此时 x = k 即为一个解。
 
有人宣称,任意给定一个正整数,如果它不是质数,那么最多改动其中一个数字,就能把它变成质数。这个说法对吗?
这个说法是错误的。 200 不是一个质数。为了让它变成一个质数,你必须要把末位的 0 改成某个奇数。然而, 201, 203, 205, 207, 209 都不是质数。事实上,我们可以证明,像这样的反例有无穷多个,例如所有形如 2310k – 210 的数都可以用作反例。为了让它变成一个质数,你必须要把末位的 0 改成某个奇数,然而:

  • 2310k – 210 + 1 = 2310k – 209 = 11 · (210k – 19)
  • 2310k – 210 + 3 = 2310k – 207 = 3 · (770k – 69)
  • 2310k – 210 + 5 = 2310k – 205 = 5 · (462k – 41)
  • 2310k – 210 + 7 = 2310k – 203 = 7 · (330k – 29)
  • 2310k – 210 + 9 = 2310k – 201 = 3 · (770k – 67)

 
证明:存在任意大的正整数 x 、 y ,使得 x 不能整除 y ,但 xx 能整除 yy 。
选取一个任意大的正整数 k ,再选取一个大于 k · 2k – 1 的质数 p 。令 x = 2k ,令 y = 2p ,则 x 和 y 满足要求。这是因为只要 k > 1 ,那么 x 显然都不能整除 y ;同时,我们有 xx = (2k)2k = 2k · 2k ,并且 yy = (2p)2p = 22p · p2p ,由于 2p > k · 2k ,因而 xx 能够整除 yy 。
 
证明:对于任意正整数 n ,我们都能找到一个适当的正整数 x ,使得序列 x + 1, xx + 1, xxx + 1, … 里的所有数都能被 n 整除。
很简单, x = 2n – 1 就满足要求。由于 x 是一个奇数,而奇数的奇数次方一定还是奇数,因而序列 x, xx, xxx, … 里的所有数都是奇数。另外再注意到,对于任意一个奇数 m 来说, am + 1 都能被 a + 1 整除。因此,序列 x + 1, xx + 1, xxx + 1, … 里的所有数都能被 2n = x + 1 整除,它们自然也就都能被 n 整除了。
为什么对于任意一个奇数 m 来说, am + 1 都能被 a + 1 整除呢?由于 a = -1 是方程 am + 1 = 0 的一个解,因而多项式 am + 1 一定能被分解成 (a + 1)( … … ) 的样子,这就说明了 am + 1 能被 a + 1 整除。在下一题中,我们还会用到这个结论。
类似地,对于任意一个正整数 m 来说, am – 1 都能被 a – 1 整除。由于 a = 1 是方程 am – 1 = 0 的一个解,因而多项式 am – 1 一定能被分解成 (a – 1)( … … ) 的样子,这就说明了 am – 1 能被 a – 1 整除。在再下一题中,我们会用到这个结论。
 
证明:存在无穷多个正整数 n ,使得 2n + 1 能被 n 整除。
首先, 23 + 1 能被 3 整除。另外,如果 2n + 1 能被 n 整除,那么 22n + 1 + 1 一定能被 2n + 1 整除。这是为什么呢?不妨假设 2n + 1 = n · k 。考虑到 2n + 1 是奇数,因而 k 也一定是奇数。根据上题使用过的结论, (2n)k + 1 就能被 2n + 1 整除,即 2n · k + 1 = 22n + 1 + 1 能被 2n + 1 整除。综合上面两条便可得到,存在无穷多个满足要求的 n 。
大家可能会想,那么,有多少个正整数 n ,使得 2n – 1 能被 n 整除呢?答案是,只有一个满足要求的解,即 n = 1 。证明比较复杂,这里略去。
 
人们已经知道了,质数有无穷多个。一个经典的结论是,相邻质数之间的间隔也可以达到任意大,或者说存在任意长的连续正整数,使得里面的所有数都是合数。例如, n! + 2, n! + 3, …, n! + n 就是连续 n – 1 个正整数,由于它们分别能被 2, 3, …, n 整除,因而它们都是合数。 Mersenne 质数是形如 2n – 1 的质数,例如 3, 7, 31, 127 等等。目前人们还不知道, Mersenne 质数是否有无穷多个。一个有意思的问题是,在所有形如 2n – 1 的数里面,相邻的 Mersenne 质数之间的间隔也能达到任意大吗?换句话说,在数列 1, 3, 7, 15, 31, … 中,是否存在任意长的连续项,使得里面的所有数都是合数?
我们首先证明,如果 b 能被 a 整除,那么 2b – 1 也一定能被 2a – 1 整除。不妨假设 b = a · k ,于是 2b – 1 = (2a)k – 1 ,根据上上题末尾引申的结论,它能被 2a – 1 整除。证明这件事情还有一个有趣的方法。 2b – 1 的二进制表达就是 b 个数字 1 相连, 2a – 1 的二进制表达就是 a 个数字 1 相连,如果 b 能被 a 整除的话,让这两个数在二进制的世界里做除法,显然能够除尽,比如 111111 除以 11 就等于 10101 。
因此, 2n! + 2 – 1, 2n! + 3 – 1, …, 2n! + n – 1 分别能被 22 – 1, 23 – 1, …, 2n – 1 整除,因而在所有形如 2n – 1 的数里面,相邻的 Mersenne 质数之间的间隔能达到任意大。
“存在任意长的并且全是合数的连续正整数”真的是一个很经典的结论,除了可以平行地扩展到其他的场合,其本身也还有很多加强版。下面这个可以算是我所见过的最终极的加强版了。证明:对于任意的正整数 n 和 s ,我们都能找到任意长的连续正整数,使得对于这里面的每一个数来说,它里面都含有至少 n 个不同的质因数,其中的每个质因数都出现了至少 s 次。
下面,我们就来构造一段满足要求的并且长度为 m 的连续正整数,其中 m 是任意大的正整数。假设 p1, p2, …, pmn 是 mn 个不同的质数。令 a1 为前 n 个质数的 s 次方之积,即 a1 = p1s · p2s · … · pns 。类似地,令 a2 为下 n 个质数的 s 次方之积,令 a3 为再下 n 个质数的 s 次方之积,以此类推,一直到令 am 为最后 n 个质数的 s 次方之积。
显然, a1, a2, …, am 两两互质。根据中国剩余定理,我们能够找到一个 x ,使得 x 除以 a1 余 a1 – 1 ,并且 x 除以 a2 余 a2 – 2 ,等等,一直到 x 除以 am 余 am – m 。于是, x + 1, x + 2, …, x + m 分别能被 a1, a2, …, am 整除,这 m 个连续正整数就满足要求了。
 
证明:存在无穷多组不同的正整数 x 、 y 、 z ,使得 x(x + 1), y(y + 1), z(z + 1) 构成等差数列。
令 y = 5x + 2, z = 7x + 3 ,于是我们有

  • x(x + 1) = x2 + x
  • y(y + 1) = 25x2 + 25x + 6
  • z(z + 1) = 49x2 + 49x + 12

它们构成了一个公差为 24x2 + 24x + 6 的等差数列。
有趣的是,如果进一步问,是否能让 x(x + 1), y(y + 1), z(z + 1), w(w + 1) 构成一个等差数列,答案就是否定的了。这个证明比较复杂,这里略去。
 
给出一个无限长的递增等差数列,使得里面的所有项都不能表示为两个质数之和。
数列 11, 17, 23, 29, … 即符合要求。这些数都是形如 6k + 5 的数。如果 6k + 5 = p + q ,考虑到 6k + 5 是一个奇数,因而 p 和 q 必然有一个是偶数。无妨假设 p 是偶数,如果它又是质数的话,那么 p = 2 。于是, q = 6k + 3 将会成为 3 的倍数。
借助这个思路,我们还能构造一个无限长的递增等差数列,使得里面的所有项都既不能表示为两个质数之和,也不能表示为两个质数之差。例如,数列 37, 67, 97, 127, … 即符合要求。这些数都是形如 30k + 7 的数。如果 30k + 7 = p + q ,考虑到 30k + 7 是一个奇数,因而 p 和 q 必然有一个是偶数。无妨假设 p 是偶数,如果它又是质数的话,那么 p = 2 。于是, q = 30k + 5 将会成为 5 的倍数。类似地,如果 30k + 7 = p – q ,那么 q 必然等于 2 ,于是 p = 30k + 9 将会成为 3 的倍数。
 
给出一个无限长的递增等差数列,使得里面不含任何一个 Fibonacci 数。
数列 4, 12, 20, 28, 36, … 符合要求。这些数都是除以 8 余 4 的数,而我们一会儿将会看到,任何一个 Fibonacci 数除以 8 都不可能余 4 。为了计算 a + b 除以 8 的余数,我们可以把 a 替换成它除以 8 的余数,把 b 也替换成它除以 8 的余数,再计算两者相加除以 8 的余数即可。例如, 23 除以 8 的余数是 7 , 67 除以 8 的余数是 3 ,因而 23 + 67 除以 8 的余数就等于 7 + 3 除以 8 的余数,也就是 2 。根据这个原理,我们很容易算出 Fibonacci 数列各项除以 8 的余数:
1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, …
第 13 项和第 14 项除以 8 的余数又变回了 1 和 1 ,而下一项除以 8 的余数完全取决于前两项除以 8 的余数,因而后面所有 Fibonacci 数除以 8 的余数就会发生循环。这就说明了,一个 Fibonacci 数除以 8 的余数只可能是 0, 1, 2, 3, 5, 7 ,不可能是 4 。因此,由所有除以 8 余 4 的数构成的等差数列里,一定不会含有任何一个 Fibonacci 数。
用类似的方法可以说明,对于所有小于 8 的正整数 m , Fibonacci 数除以 m 的余数都可以取遍 0, 1, 2, …, m – 1 所有的可能。因而,如果一个无限长的递增等差数列不含任何一个 Fibonacci 数,它的公差至少是 8 。
 
证明:对于任意一个无限长的递增等差数列,我们都能找出任意长的一段连续项,使得它们都是合数。
假设这个等差数列是 a + b, 2a + b, 3a + b, … 。假设 n 是一个足够大的正整数。任取 n 个大于 a 的质数 p1, p2, …, pn 。容易看出, a, p12, p22, …, pn2 两两互质。根据中国剩余定理,存在一个整数 m ,使得 m 除以 a 的余数为 0, 并且它除以 p12 的余数为 p12 – a – b ,除以 p22 的余数为 p22 – 2a – b ,除以 p32 的余数为 p32 – 3a – b ,以此类推。于是, m + a + b, m + 2a + b, m + 3a + b, …, m + n · a + b 就是等差数列的连续 n 项,并且由于第 i 项能被 pi2 整除,因而这里面的每一项都是合数。
 
证明:存在任意长的递增等差数列,使得里面的任意两项都是互质的。
假设 m 为某个足够大的正整数。于是, m! + 1, 2 · m! + 1, 3 · m! + 1, …, m · m! + 1 就成为了一个含有 m 项的公差为 m! 的等差数列。这里面的任意两项都是互质的。如果对于某两个不超过 m 的正整数 k 和 l , k · m! + 1 和 l · m! + 1 都是 d 的倍数(无妨假设 k < l ),那么 l · (k · m! + 1) – k · (l · m! + 1) = l – k 也应该是 d 的倍数,这说明 d ≤ l – k < m ,因而 d 能整除 m! 。但是 d 也能整除 k · m! + 1 ,因而 d = 1 。
 
证明:存在任意长的递增等差数列,使得里面的每一项都是乘方数。这里,“乘方数”的意思是形如 nk 的数,其中 n 、 k 都是正整数,且 k > 1 。
假设 p1, p2, …, ps 是任意 s 个不同的质数。根据中国剩余定理,对于每一个不超过 s 的正整数 t ,我们都能找到一个大整数 at ,使得 at 除以 pt 余 pt – 1 ,并且除以其他 s – 1 个质数都余 0 。现在,令 Q = 1a1 · 2a2 · … · sas ,那么 Q, 2 · Q, 3 · Q, …, s · Q 就是一个等差数列。我们来证明,这个等差数列满足要求。对于这个等差数列中的任意一项 t · Q ,我们都有 t · Q = 1a1 · 2a2 · … · tat + 1 · … · sas ,根据 a1, …, as 的构造方法可知,这里面的每一个指数都是 pt 的倍数。因而, t · Q 可以写成某个数的 pt 次方。由于 s 的值可以达到任意大,因而满足要求的等差数列也可以达到任意长。
那么,是否存在无限长的递增等差数列,使得里面的每一项都是乘方数呢?这回,答案就是否定的了。我们可以证明,在任何一个无限长的递增等差数列 a + b, 2a + b, 3a + b, … 中,总存在一个不是乘方数的数。首先,找出一个比 a + b 更大的质数 p 。由于 a 和 p2 互质,因此根据中国剩余定理,我们一定能够找到一个数 m ,使得 m 除以 a 余 0 ,并且除以 p2 余 1 。令 k = (p – b) · m / a 。由于 m 除以 a 余 0 ,因此 k 是个整数;由于 p > b ,因此 k 是一个正整数。于是 k · a + b = (p – b) · m + b = (p – b) · m – (p – b) + p = (p – b)(m – 1) + p 。由于 m 除以 p2 余 1 ,因而最后这个式子的前一项是 p2 的倍数;但最后这个式子的后一项却只是 p 的倍数,因而两者之和能被 p 整除,却不能被 p2 整除。这说明,它不能表示成任何一个数的 1 次以上的乘方。
 
是否存在四个连续正整数,使得它们都是乘方数?这里,“乘方数”的意思和上题一样,即形如 nk 的数,其中 n 、 k 都是正整数,且 k > 1 。
不存在。在任意四个连续正整数中,必然有一个数是形如 4k + 2 的数。这样的数能被 2 整除,却不能被 4 整除,因而永远不可能是一个乘方数。
那么,是否存在三个连续正整数,使得每一个数都是乘方数呢? 1962 年, A. Mąkowski 证明了,这也是不可能的,不过证明过程就没那么简单了。那么,是否存在两个相邻的正整数,使得它们都是乘方数呢?这次就有了,例如 8 = 23, 9 = 32 。1844 年, Eugène Catalan 猜想,除了 8 和 9 以外,没有别的相邻乘方数了。 2002 年,这个猜想终于被 Preda Mihăilescu 证明。
 
31, 331, 3331, 33331 都是质数。难道数列 31, 331, 3331, 33331, … 中的所有数都是质数吗?其实并不是这样。证明:数列 31, 331, 3331, 33331, … 中含有无穷多个合数。
数列的通项公式是 (10n + 1 – 7) / 3 。容易验证, 101, 102, …, 1017 除以 17 的余数分别是
10, 15, 14, 4, 6, 9, 5, 16, 7, 2, 3, 13, 11, 8, 12, 1, 10
其中 1017 和 101 除以 17 的余数相同,因此再往后, 10 的乘方除以 17 的余数便会开始循环,循环节的长度为 16 。由于 109 除以 17 余 7 ,这就说明所有的 1016k + 9 除以 17 都余 7 。因此,所有的 (1016k + 9 – 7) / 3 都是 17 的倍数。
事实上, 31, 331, 3331, 33331, 333331, 3333331, 33333331 都是质数,首次出现的合数为 333333331 = 17 × 19607843 ,这正是 k = 0 时 (1016k + 9 – 7) / 3 的值。我们自然会问,除了所有的 (1016k + 9 – 7) / 3 以外,数列 31, 331, 3331, 33331, … 当中还有别的合数吗?答案是,确实还有。用和刚才类似的方法可以推出,所有的 (1018k + 12 – 7) / 3 都能被 19 整除,例如 (1012 – 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) + 102 · φ(t) + … + 10s · φ(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 趋于无穷时, 2n 的各位数字之和也将随之趋于无穷。
下面这个证明是由 Andrzej Schinzel 给出的。我们先来定义一个数列 a0, a1, a2, … ,其中 a0 = 0 ,并且 ai + 1 为最小的使得 2ai + 1 大于 10ai 的正整数。在所有 2 的乘方中,最小的比 100 更大的是 2 的 1 次方,因此 a1 = 1 ;在所有 2 的乘方中,最小的比 101 更大的是 2 的 4 次方,因此 a2 = 4 ;在所有 2 的乘方中,最小的比 104 更大的是 2 的 14 次方,因此 a3 = 14 ……容易看出, a0 < a1 < a2 < … 。
下面我们来证明,如果 n 大于等于某个 ak ,那么 2n 的右起第 ak – 1 + 1 到第 ak 位里至少有一个非 0 数字。不妨让我们以 k = 3 为例来说明这一点,你会发现下面的推理过程适用于一切其他的 k 。当 k = 3 时,我们要证明的就是,如果 n ≥ a3 = 14 ,那么 2n 的右起第 a2 + 1 = 5 位到第 a3 = 14 位里至少有一个非 0 数字。反证,假设 2n 等于 abc0000000000defg ,其中 a 、 b 、 c 、 d 、 e 、 f 、 g 都是一位数字。注意到 2 的任何乘方的个位都不可能是 0 ,这说明 g 肯定不为 0 。由于 214 可以整除 1014 ,因而 214 可以整除 abc00000000000000 ;由于 n 大于等于 14 ,因而 214 也可以整除 2n = abc0000000000defg 。所以, 214 必然能整除 abc0000000000defg – abc00000000000000 = defg 。虽然 d 、 e 、 f 都可能为 0 ,但我们刚才说过, g 是肯定不为 0 的,因而 defg 是一个最多 4 位的正整数。但是,214 能整除一个最多 4 位的正整数,这是不可能的,因为根据数列 ai 的定义, 214 > 104 ,也就是说 214 至少有 5 位数,它不可能整除一个比自己小的正整数。
所以,如果 n 大于等于某个 ak ,那么 2n 的右起第 ak – 1 + 1 到第 ak 位里至少有一个非 0 数字。事实上,如果 n 大于等于某个 ak ,那它也大于 a1, a2, …, ak – 1 ,因而对于所有不超过 k 的正整数 i 来说, 2n 的右起第 ai – 1 + 1 到第 ai 位里都含有至少一个非 0 数字。可见, 2n 里至少有 k 个非 0 数字,即它的各位数字之和至少为 k 。这表明,随着 n 的增加, 2n 的各位数字之和可以达到任意大。我们的结论也就证到了。
注意, 2n 的各位数字之和趋于无穷大,并不意味着 2n 的各位数字之和是不断递增的。当 n = 1, 2, .., 20 时, 2n 的各位数字之和为
2, 4, 8, 7, 5, 10, 11, 13, 8, 7, 14, 19, 20, 22, 26, 25, 14, 19, 29, 31
可以看到,下一项比上一项更小的现象时有发生。
 
证明:对于任意两个不同的正整数 a 、 b ,我们都能找到无穷多个正整数 n ,使得 a + n 和 b + n 互质。
不妨假设 a < b 。令 n = (b – a)k + 1 – a 。只要 k 的值足够大, n 都是正整数。现在,假设 a + n 和 b + n 都是 d 的倍数,那么 (b + n) – (a + n) = b – a 必然也是 d 的倍数。同时,注意到 a + n = (b – a)k + 1 是 d 的倍数,因此 1 一定是 d 的倍数,说明 d 只能等于 1 。
大家肯定会进一步追问,那是否对于任意三个不同的正整数 a 、 b 、 c ,我们都能找到无穷多个正整数 n ,使得 a + n 、 b + n 、 c + n 两两互质呢?答案是,这也是能办到的。不过,这个证明比较复杂,我们就略去了。
那么,是否对于任意四个不同的正整数 a 、 b 、 c 、 d ,我们都能找到无穷多个正整数 n ,使得 a + n 、 b + n 、 c + n 、 d + n 两两互质呢?这就不行了。事实上,我们能够找到一组特殊的 (a, b, c, d) ,使得满足要求的 n 一个也没有。比方说 (a, b, c, d) = (1, 2, 3, 4) 。这样一来,如果 n 是奇数,那么 a + n 和 c + n 显然不互质;如果 n 是偶数,那么 b + n 和 d + n 显然不互质。
 
证明:任意一个大于 6 的正整数都可以表示成两个互质的数的和。
如果 n 是一个大于 6 的奇数,那么把 n 拆成 2 和 n – 2 显然符合要求。这是因为, 2 和任何一个奇数都是互质的。接下来,我们分别考虑 n = 4k 和 n = 4k + 2 两种情况。当 n = 4k 时,把 n 拆成 2k – 1 和 2k + 1 符合要求。这是因为,如果 2k – 1 和 2k + 1 都是 d 的倍数,则 (2k + 1) – (2k – 1) = 2 也是 d 的倍数,但 2k – 1 和 2k + 1 都是奇数,因而 d = 1 。当 n = 4k + 2 时,把 n 拆成 2k – 1 和 2k + 3 显然符合要求。这是因为,如果 2k – 1 和 2k + 3 都是 d 的倍数,那么 (2k + 3) – (2k – 1) = 4 也是 d 的倍数,但 2k – 1 和 2k + 3 都是奇数,因而 d = 1 。
我们可以用类似的分类讨论的方法来证明,任意大于 17 的正整数都可以表示成三个两两互质的数的和。我们把 n 为偶数的情况分为 n = 6k, n = 6k + 2 和 n = 6k + 4 这三类,它们都有自己的拆分方案:

  • 6k = 2 + 3 + (6(k – 1) + 1)
  • 6k + 2 = 3 + 4 + (6(k – 1) + 1)
  • 6k + 4 = 2 + 3 + (6k – 1)

当 n 为奇数时,我们分 n = 12k + 1, n = 12k + 3, n = 12k + 5, n = 12k + 7, n = 12k + 9, n = 12k + 11 六类情况讨论。

  • 12k + 1 = (6(k – 1) – 1) + (6(k – 1) + 5) + 9
  • 12k + 3 = (6k – 1) + (6k + 1) + 3
  • 12k + 5 = (6k – 5) + (6k + 1) + 9
  • 12k + 7 = (6k + 5) + (6k – 1) + 3
  • 12k + 9 = (6k – 1) + (6k + 1) + 9
  • 12k + 11 = (6(k + 1) – 5) + (6(k + 1) + 1) + 3

题目给出的结论还有一些有趣的推论。例如,我们可以据此证明,若用 pk 表示第 k 个质数,则对于任意 k ≥ 3 都有 pk + 1 + pk + 2 ≤ p1 · p2 · … · pk 。由于 k ≥ 3 ,因而 p1 · p2 · … · pk ≥ 2 · 3 · 5 > 6 ,根据题目给出的结论,它可以表示成两个互质的数 a 和 b 之和。 a 和 a + b 的任何一个公约数也一定是 a 和 b 的公约数,但 a 和 b 没有大于 1 的公约数,说明 a 和 a + b 也没有大于 1 的公约数。这说明, a 和 a + b 也是互质的,即 a 和 p1 · p2 · … · pk 是互质的。
令 p 为 a 的任意一个质因数,令 q 为 b 的任意一个质因数。由于 a 和 b 互质,它们拥有完全不同的质因数,因此 p ≠ q 。无妨假设 p < q 。由于 a 和 p1 · p2 · … · pk 互质,因此 p ≥ pk + 1 ;由于 p < q ,因此 q ≥ pk + 2 。于是,我们有
pk + 1 + pk + 2 ≤ p + q ≤ a + b = p1 · p2 · … · pk
 
证明:存在无穷多个正整数满足,它可以用至少两种不同的方法表示成四个正整数的平方和。
可以验证, (t – 8)2 + (t – 1)2 + (t + 1)2 + (t + 8)2 = (t – 7)2 + (t – 4)2 + (t + 4)2 + (t + 7)2 恒成立,因而当 t > 8 时,每一个 t 都对应一个满足要求的正整数,结论便证到了。
我们还可以证明,存在无穷多个正整数满足,它可以用至少两种不同的方法表示成四个正整数的立方和。可以验证, (t – 8)3 + (t – 1)3 + (t + 1)3 + (t + 8)3 = (t – 7)3 + (t – 4)3 + (t + 4)3 + (t + 7)3 恒成立,因而当 t > 8 时,每一个 t 都对应一个满足要求的正整数,结论便证到了。
 
证明:任意一个整数都可以用无穷多种方法表示成五个整数的立方和。
首先,可以验证, 6t = (t + 1)3 + (t – 1)3 + (-t)3 + (-t)3 。这说明,任何一个 6 的倍数都可以表示成四个立方数之和。
现在,把任意一个整数写成 6k + r 的形式,其中 r 为 0 、 1 、 2 、 3 、 4 、 5 之一。你会发现,对于任意一个整数 n 来说, 6k + r – (6n + r)3 都是 6 的倍数。这是因为
6k + r – (6n + r)3 = 6k + r – 216 · n3 – 108 · n2 · r – 18 · n · r2 – r3
这里面除了 r 和 – r3 以外,其他所有项都是 6 的倍数。而 r – r3 = – (r – 1) · r · (r + 1) 显然也是 6 的倍数—— r – 1, r, r + 1 相当于三个连续整数,其中至少有一个是 2 的倍数,且必然有一个是 3 的倍数,因而它们的乘积也就是 6 的倍数。
好了,既然 6k + r – (6n + r)3 总是 6 的倍数,那我们就可以把 6k + r 拆成
(6k + r – (6n + r)3) + (6n + r)3
其中前者可以表示成四个立方数之和,后者本身就是一个立方数。这样,我们就成功地把 6k + r 表示成了五个立方数之和。每取一个不同的 n 都会得到一种不同的表示方法,因而表示方法也就有无穷多种。
 
证明:对于任意一个整数 k ,我们都有无穷多种方法把它表示成 ± 12 ± 22 ± 32 ± … ± m2 的形式。
显然,我们只需要考虑所有的非负整数 k 即可,因为把所有的符号全都反过来,就能把正数 k 的表达方法转换成负数 k 的表达方法。首先我们来证明,任何 k ≥ 0 都有至少一种表示方法。容易验证:

  • 0 = 12 + 22 – 32 + 42 – 52 – 62 + 72
  • 1 = 12
  • 2 = – 12 – 22 – 32 + 42
  • 3 = – 12 + 22

由于对于任意 m 都有
(m + 1)2 – (m + 2)2 – (m + 3)2 + (m + 4)2 = 4
因而对于任何非负整数 k 的任何一种表达方法 ± 12 ± 22 ± 32 ± … ± m2 ,我们都有
k + 4 = ± 12 ± 22 ± 32 ± … ± m2 + (m + 1)2 – (m + 2)2 – (m + 3)2 + (m + 4)2
这意味着,只要 k 有表达方法, k + 4 就有表达方法。既然 k = 0, 1, 2, 3 时都有表达方法,那么对于一切的非负整数 k ,表达方法也都存在了。
因此,我们也就证明了,对于任意一切整数 k ,表达方法都是存在的。但是,为什么表达方法有无穷多种呢?只需要注意到
(m + 1)2 – (m + 2)2 – (m + 3)2 + (m + 4)2 – (m + 5)2 + (m + 6)2 + (m + 7)2 – (m + 8)2 = 0
所以我们可以在任何整数 k 的任何一种表达方法后面添加 8 项,然后再添上 8 项,然后再添上 8 项……从而得到无穷多种表达方法。
 
证明:除了 (2, 3) 、 (4, 3) 、 (8, 9) 三种情况以外, 2 的某个乘方和 3 的某个乘方不可能成为两个相邻数。
首先考虑 2m = 3n + 1 的情况。容易看出,随着 n 的增加, 3n 除以 8 的余数是按照 1, 3, 1, 3, 1, 3, … 的规律循环的。因而 3n + 1 除以 8 的余数是按照 2, 4, 2, 4, 2, 4, … 的规律循环的。这说明,不管正整数 n 为多少, 3n + 1 都不可能被 8 整除。如果 2m = 3n + 1 ,则 2m 也不能被 8 整除,这说明 m ≤ 2 。检验可知 (m, n) = (2, 1) 是唯一可能的情况。
接下来考虑 2m = 3n – 1 的情况。借助之前讨论的结果可以看出, 3n – 1 除以 8 的余数是按照 0, 2, 0, 2, 0, 2, … 的规律循环的,因而当 n 是奇数时, 3n – 1 不能被 8 整除。如果 2m = 3n – 1 ,则 2m 也不能被 8 整除,这说明 m ≤ 2 。检验可知 (m, n) = (1, 1) 是唯一可能的情况。那么,如果 n 是偶数呢?刚才的方法就不管用了。不过,我们还有别的招。不妨假设 n = 2k ,于是 2m = 3n – 1 = 32k – 1 = (3k – 1)(3k + 1) ,这说明 3k – 1 和 3k + 1 都只含因数 2 ,或者说 3k – 1 和 3k + 1 都是 2 的整数次幂。这只有一种可能: 3k – 1 = 2 , 3k + 1 = 4 。据此,我们得到了该问题的最后一组解: (m, n) = (3, 2) 。
 
证明:在任意三个大于 7 的连续正整数之中,一定有至少一个数,它包含至少两种不同的质因数。
首先,任何一个形如 6k 的数都必然包含至少两种不同的质因数。其次,当 k > 1 时, 6k + 2 和 6k + 3 不可能都只包含一种质因数。这是因为, 6k + 2 是 2 的倍数,如果它只包含一种质因数,则必是 2 的某个乘方; 6k + 3 是 3 的倍数,如果它只包含一种质因数,则必是 3 的某个乘方;但根据上题的结论,除去少数数值很小的情况以外, 2 的某个乘方和 3 的某个乘方都不可能成为两个相邻整数。类似地,当 k ≥ 1 时, 6k + 3 和 6k + 4 也不可能都只包含一种质因数。这是因为,前者必然是 3 的某个乘方,后者必然是 2 的某个乘方,但根据上题的结论,这是不可能的。
然而,在任意三个大于 7 的连续正整数当中,要么包含形如 6k 的数,要么包含形如 6k + 2 和 6k + 3 的两个相邻数(其中 k > 1 ),要么包含形如 6k + 3 和 6k + 4 的两个相邻数(其中 k ≥ 1 )。所以,这里面至少有一个数,它包含至少两种不同的质因数。
 
证明:存在无穷多对不同的正整数 (m, n) ,使得 m 和 n 拥有完全相同的质因数(仅每个质因数的次数可能有所不同),并且 m + 1 和 n + 1 也拥有完全相同的质因数(仅每个质因数的次数可能有所不同)。
对于任意大于 1 的正整数 k , (m, n) = (2k – 2, 2k(2k – 2)) 显然都满足要求。 m 和 n 分解质因数之后的唯一差异就是, n 比 m 多了一堆 2 ,而 2 本来就是两者都已经有了的质因数。另外, m + 1 = 2k – 1 , n + 1 = 2k(2k – 2) + 1 = (2k – 1)2 ,两者显然也拥有完全相同的质因数。
Paul Erdős 曾问,是否还有别的满足要求的 (m, n) 。答案是肯定的,例如 (75, 1215) 满足要求。 75 = 3 × 52 , 1215 = 35 × 5 ; 76 = 22 × 19 , 1216 = 26 × 19 。
 
找出所有的正整数组 (x, y, z) ,使得分数 x / y 、 y / z 、 z / x 都是最简分数,并且它们的和是一个正整数。
假设 x / y + y / z + z / x = m ,其中 m 是一个正整数。等式可以变为 x2z + y2x + z2y = mxyz 。等号左边的后面两项都是 y 的倍数,等号右边的结果也是 y 的倍数,这说明等号左边的第一项也必然是 y 的倍数。也就是说, x2z 是 y 的倍数。类似地, y2x 是 z 的倍数, z2y 是 x 的倍数。但是,分数 x / y 、 y / z 、 z / x 都是最简分数,这说明 x 、 y 、 z 两两互质,因而 x2z 和 y 是互质的, y2x 和 z 是互质的, z2y 和 x 是互质的。由此可知 y = 1, z = 1, x = 1 ,因而 1 / 1 + 1 / 1 + 1 / 1 = 3 是这个问题的唯一解。
 
证明: x / y + y / z + z / x = 1 和 x / y + y / z + z / x = 2 都没有正整数解。
第一个问题很简单。 x / y 、 y / z 和 z / x 的乘积为 1 ,说明三者必有一个大于等于 1 ,因而 x / y + y / z + z / x > 1 。第二个问题则稍微复杂一些。由于任意三个正数的算术平均数一定大于等于它们的几何平均数,因而 (x / y + y / z + z / x) / 3 ≥ ((x / y) · (y / z) · (z / x))1/3 = 1 ,这说明 x / y + y / z + z / x ≥ 3 。
容易看出, x / y + y / z + z / x = 3 是有正整数解的,例如 x = y = z = 1 。 x / y + y / z + z / x = 5 的其中一组正整数解为 x = 1, y = 2, z = 4 。 x / y + y / z + z / x = 6 的其中一组正整数解为 x = 2, y = 12, z = 9 。如果所涉及的数更大一些,找出相应的解就不太容易了。 Woody Dudley 发现 x / y + y / z + z / x = 41 是有正整数解的,其中一组正整数解为 x = 350, y = 196, z = 5 。究竟对于哪些正整数 n ,方程 x / y + y / z + z / x = n 有正整数解,这是一个非常困难的问题。
 
证明:对于任意正整数 s ≥ 3 ,方程 1 / x1 + 1 / x2 + … + 1 / xs = 1 都有满足 x1 < x2 < … < xs 的正整数解,且随着 s 的增加,满足要求的解的数量也随之增加。
当 s = 3 时, x1 = 2, x2 = 3, x3 = 6 是一组满足要求的解。另外,如果对于某个 s ≥ 3 , (x1, x2, …, xs) 是一组满足要求的解,那么 x1 必然大于 1 。于是,我们有
  1 / 2 + 1 / (2x1) + 1 / (2x2) + … + 1 / (2xs)
= 1 / 2 + (1 / 2) · (1 / x1 + 1 / x2 + … + 1 / xs)
= 1 / 2 + (1 / 2) · 1
= 1
并且 2 < 2x1 < 2x2 < … < 2xs 。它们就成为了 s 增加 1 之后的一组解。这就立即说明了,随着 s 的增加,满足要求的解的个数不会减少,至少会保持不变。但是,我们需要证明的是,随着 s 的增加,满足要求的解的个数会严格增加。怎么办呢?
很简单。如果对于某个 s ≥ 3 , (x1, x2, …, xs) 是一组满足要求的解。于是,我们有
  1 / 2 + 1 / 3 + 1 / (6x1) + 1 / (6x2) + … + 1 / (6xs)
= 5 / 6 + (1 / 6) · (1 / x1 + 1 / x2 + … + 1 / xs)
= 5 / 6 + (1 / 6) · 1
= 1
并且 2 < 3 < 6x1 < 6x2 < … < 6xs 。它们就成为了 s 增加 2 之后的一组解。而且,用这种方法生成的解肯定和用前一种方法生成的解是不同的——前一种方法中,所有的分母都是偶数;但在这里的方法中,第二项的分母是 3 。于是, s = 5 的解数至少等于 s = 4 的解数加上 s = 3 的解数,s = 6 的解数至少等于 s = 5 的解数加上 s = 4 的解数……因而,随着 s 的增加,解的数量一定是严格增加的。
且慢!这只能说明, s = 5 时的解数大于 s = 4 时的解数, s = 6 时的解数大于 s = 5 时的解数,等等,但为什么 s = 4 时的解数大于 s = 3 时的解数呢?这一点是刚才的推理覆盖不到的,我们还需要额外证明一下。
首先我们证明,当 s = 3 时, x1 = 2, x2 = 3, x3 = 6 是唯一的一组解。如果 x1 ≥ 3 ,则 x2 ≥ 4 , x3 ≥ 5 ,于是 1 / x1 + 1 / x2 + 1 / x3 ≤ 1 / 3 + 1 / 4 + 1 / 5 = 47 / 60 < 1 。这说明, x1 不能大于等于 3 ,因而只能等于 2 。类似地,由于 1 / 2 + 1 / 4 + 1 / 5 = 19 / 20 < 1 ,这说明 x2 不能大于等于 4 ,只能等于 3 。因而,当 s = 3 时, x1 = 2, x2 = 3, x3 = 6 是唯一的一组解。
可以验证,当 s = 4 时,我们至少有以下六组解:

  • 1 / 2 + 1 / 3 + 1 / 7 + 1 / 42 = 1
  • 1 / 2 + 1 / 3 + 1 / 8 + 1 / 24 = 1
  • 1 / 2 + 1 / 3 + 1 / 9 + 1 / 18 = 1
  • 1 / 2 + 1 / 3 + 1 / 10 + 1 / 15 = 1
  • 1 / 2 + 1 / 4 + 1 / 5 + 1 / 20 = 1
  • 1 / 2 + 1 / 4 + 1 / 6 + 1 / 12 = 1

因此,当 s 从 3 增加到 4 时,解的数量也是严格增加的。
 
证明:对于任意正整数 n ,方程 x1 + x2 + … + xn = x1 · x2 · … · xn 至少有一组正整数解。
当 n = 1 时,我们有 1 = 1 。当 n = 2 时,我们有 2 + 2 = 2 × 2 。当 n ≥ 3 时, 1 + 1 + … + 1 + 2 + n = 1 × 1 × … × 1 × 2 × n 总成立(等号左右两边各有 n – 2 个 1 )。
对于某些特定的 n ,有没有可能还有其他的解呢?这里,我们规定 x1 ≤ x2 ≤ … ≤ xn ,从而排除掉一些本质相同的解。答案是肯定的。例如,当 n = 5 时,除了 1 + 1 + 1 + 2 + 5 = 1 × 1 × 1 × 2 × 5 以外,我们还有以下两组解:

  • 1 + 1 + 1 + 3 + 3 = 1 × 1 × 1 × 3 × 3
  • 1 + 1 + 2 + 2 + 2 = 1 × 1 × 2 × 2 × 2

因此,当 n = 5 时,方程一共有至少三组正整数解。可以证明,当 n = 5 时,方程确实也只有这三组正整数解。
当 n = 13 时,将会首次出现有四组解的情况:

  • 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 13 = 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 2 × 13
  • 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 3 + 7 = 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 3 × 7
  • 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 4 + 5 = 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 4 × 5
  • 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 3 + 3 = 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 × 2 × 3 × 3

由此产生了一个有趣的问题:到了 n 足够大的时候,会不会出现有 5 组解、 6 组解甚至 100 组解的情况?答案仍然是肯定的。首先注意到,(2a + 1)(2b + 1) = 2a + b + 2a + 2b + 1,它应该等于 2a + b – 1 个 1 、一个 2a + 1 和一个 2b + 1 相加的结果。因此,当 n = 2200 + 1 时,至少会有这么 100 组解:前面 2200 – 1 个数都是 1 ,最后两个数是 2 + 1 和 2199 + 1 ,或者 22 + 1 和 2198 + 1 ,或者 23 + 1 和 2197 + 1 ,一直到 2100 + 1 和 2100 + 1 。利用这种思路,我们总能找到适当的 n ,使得满足要求的解的个数达到任意你想要的数目。
另一方面,不管 n 是多少,解的个数都是有限的。我们可以用一种非常简单的方法证明这一点。考虑到这 n 个数当中最大的那个数是 xn ,因而我们有
x1 · x2 · … · xn = x1 + x2 + … + xn ≤ n · xn
这说明 x1 · x2 · … · xn – 1 ≤ n ,进而说明 x1, x2, …, xn – 1 都不能超过 n 。所以, (x1, x2, …, xn – 1) 的取值组合只有有限多种情况。由于每一种情况最多只能对应一个解,因而总的解数就是有限的了。等等,为什么每一种情况最多只能对应一个解呢?假设 x1, x2, …, xn – 1 的值已经确定了,不妨设它们的和为 S ,积为 P ,那么 xn 就应该满足方程 S + xn = P · xn ,于是 xn 只能等于 S / (P – 1) 。这是否对应了一个满足要求的解,则取决于 S / (P – 1) 的值是不是正整数,以及它和 xn – 1 的大小关系。
让我们用 f(n) 来表示 n 个正整数之和等于它们的乘积有多少种不同的情况。我们已经证明了, f(n) 的值可以达到任意大,但却始终是有限的。但是,我们却很难刻画出关于数列 f(n) 的具体特征。 2002 年,经过一番计算机搜索后, Michael Ecker 作出了这么一个猜测:只有有限多个 n 满足 f(n) = 1 ,它们分别是 2, 3, 4, 6, 24, 114, 174, 444 。这个猜想是否正确,至今仍然未知。