《谢尔宾斯基的初等数论问题》由会员分享,可在线阅读,更多相关《谢尔宾斯基的初等数论问题(21页珍藏版)》请在金锄头文库上搜索。
1、波兰数学家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
2、 的整倍数,那么 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 ,这就说明满足要求
3、的等差数列不存在。找出所有这样的质数,它既能表示成两个质数之和,也能表示成两个质数之差。满足要求的数只有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)
4、= (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 的整数之积的。证明:方程
5、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
6、 ,则方程 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 1 ,那么 x 显然
7、都不能整除 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, 里的所
8、有数都能被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 整除。在再下一题中,我们会用到这
9、个结论。证明:存在无穷多个正整数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 整除呢?答案是,只有一个满
10、足要求的解,即n = 1 。证明比较复杂,这里略去。人们已经知道了,质数有无穷多个。一个经典的结论是,相邻质数之间的间隔也可以达到任意大,或者说存在任意长的连续正整数,使得里面的所有数都是合数。例如,n! + 2, n! + 3, , n! + n 就是连续n 1 个正整数,由于它们分别能被 2, 3, , n 整除, 因而它们都是合数。 Mersenne 质数是形如2n 1 的质数,例如3, 7, 31, 127 等等。目前人们还不知道,Mersenne 质数是否有无穷多个。一个有意思的问题是,在所有形如2n 1 的数里面,相邻的Mersenne 质数之间的间隔也能达到任意大吗?换句话说,在
11、数列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! + 31, ,
12、2n! + n 1 分别能被22 1, 231, , 2n 1 整除,因而在所有形如2n 1 的数里面,相邻的 Mersenne 质数之间的间隔能达到任意大。 存在任意长的并且全是合数的连续正整数 真的是一个很经典的结论,除了可以平行地扩展到其他的场合, 其本身也还有很多加强版。 下面这个可以算是我所见过的最终极的加强版了。 证明:对于任意的正整数n 和 s ,我们都能找到任意长的连续正整数,使得对于这里面的每一个数来说,它里面都含有至少n 个不同的质因数,其中的每个质因数都出现了至少s 次。下面,我们就来构造一段满足要求的并且长度为m 的连续正整数,其中m 是任意大的正整数。假设p1, p2
13、, , pmn是 mn 个不同的质数。令a1为前 n 个质数的 s 次方之积,即a1 = p1s p 2s 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 个连续正整数就满足要求了。证明:存在无穷多组不同的正
14、整数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) 构成一个等差数列,答案就是否定的了。这个证明比较复杂,这里略去。给出一个无限长的递增等差数列,使得里面的所有项都不能表
15、示为两个质数之和。数列 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
16、是一个奇数, 因而 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 的余数