假设n=4k＋r，k是整数，r=0，1，2，3．则
Sn=1＋2＋3＋4≡1＋2＋3＋4（mod 5）
由此推出，当r=0时，Sn≡4，而当r=1，2，3时，Sn≡0（mod 5）．因此，当且仅当n不能被4整除时，Sn能被5整除． A4－002 证明：从n个给定的自然数中，总可以挑选出若干个数（至少一个，也可能是全体），它们的和能被n整除． 【题说】1948年匈牙利数学奥林匹克题3．
【证】设a1，a2，?，an是给定的n个数．考察和序列：a1，a1＋a2，a1＋a2＋a3，?，a1＋a2＋?＋an． 如果所有的和数被n除时余数都不相同，那么必有一个和数被n除时余数为0．此时本题的断言成立．
如果在n个和数中，有两个余数相同（被n除时），那么从被加项较多的和数中减去被加项较少的和数，所得的差能被n整除．此时本题的断言也成立．
A4－003 1．设n为正整数，证明132n－1是168的倍数．
2．问：具有那种性质的自然数n，能使1＋2＋3＋?＋n整除12223?2n． 【题说】1956年上海市赛高三复赛题1．
【解】1．132n－1=（132）n－1，能被132－1，即168整除． 2．问题即
n
n
n
n
r
r
r
r
何时为整数．
（1）若n＋1为奇质数，则
（n＋1）
（2）若n＋1=2，则
（n＋1）|2（n－1）！
（3）若n＋1为合数，则
n＋1=ab
其中a?b＞1．
在b=2时，a=n＋1－a?n－1，所以
a|（n－1）！，（n＋1）|2（n－1）！
在b＞2时，2a?n＋1－a＜n－1，所以
2ab|（n－1）！
更有 （n＋1）|2（n－1）！
综上所述，当n≠p－1（p为奇质数）时，1＋2＋?＋n整除122?2n．
2（n－1）！
A4－004 证明：如果三个连续自然数的中间一个是自然数的立方，那么它们的乘积能被504整除． 【题说】 1957年～1958年波兰数学奥林匹克三试题1． 【证】设三个连续自然数的乘积为n=（a－1）a（a＋1）．
（1）a≡1，2，-3（mod 7）时，7|a3－1．a≡－1，－2，3（mod 7）时，7|a3＋1．a≡0（mod 7）时，7|a3．因此7|n． （2）当a为偶数时，a3被8整除；而当a为奇数时，a3－1与a3＋1是两个相邻偶数，其中一个被4整除，因此积被8整除． （3）a≡1，－2，4（mod 9）时，9|a3－1．a≡－1，2，-4（mod 9）时，9|a3＋1．a≡0，±3（mod 9）时，9|a3．因此9|n． 由于7、8、9互素，所以n被504=73839整除．
A4－005 设x、y、z是任意两两不等的整数，证明（x－y）5＋（y－z）5＋（z－x）5能被5（y－z）（z－x）（x－y）整除． 【题说】1962年全俄数学奥林匹克十年级题3． 【证】令x－y=u，y－z=v，则z－x=－（u＋v）． （x－y）5＋（y－z）5＋（z－x）5=u5＋v5－（u＋v）5 =5uv（n＋v）（u2＋uv＋v2）
而 5（y－z）（z－x）（x－y）=－5uv（u＋v）．因此，结论成立，而且除后所得商式为u2＋uv＋v2=x2＋y2＋z2－2xy－2yz－2xz．
【别证】也可利用因式定理，分别考虑原式含有因式（x－y），（y－z），（z－x）以及5． A4－006 已知自然数a与b互质，证明：a＋b与a2＋b2的最大公约数为1或2． 【题说】1963年全俄数学奥林匹克八年级题4． 【证】设（a＋b，a2＋b2）=d，则d可以整除
（a＋b）2－（a2＋b2）=2ab
但由于a、b互质，a的质因数不整除a＋b，所以d与a互质，同理d与b互质．因此d=1或2
3
3
3
第十九讲 整数问题：整除之二
A4－007 （a）求出所有正整数n使2n－1能被7整除． （b）证明：没有正整数n能使2＋1被7整除．
【题说】第六届（1964年）国际数学奥林匹克题1．本题由捷克斯洛伐克提供．解的关键是找出2被7除所得的余数的规律． 【证】（a）设m是正整数，则 2=（2）=（7＋1）
3m
3
m
m
n
n
=7k＋1（k是正整数）
从而 23m+1=2223m=2（7k＋1）=7k1＋2 23m+2=4223m=4（7k＋1）=7k2＋4
所以当n=3m时，2n－17k； 当n=3m＋1时，2－1=7k1＋1； 当n=3m＋2时，2－1=7k2＋3．
因此，当且仅当n是3的倍数时，2n－1能被7整除．
（b）由（a）可知，2n＋1被7除，余数只可能是2、3、5．因此，2n＋1总不能被7整除． A4－008 设k、m和n为正整数，m＋k＋1是比n＋1大的一个质数，记Cs=s（s＋1）．证明：乘积
（Cm+1－Ck）（Cm+2-Ck）?（Cm+n－Ck）
能被乘积C12C22?2Cn整除．
【题说】第九届（1967年）国际数学奥林匹克题3．本题由英国提供． 【证】Cp－Cq=p（p＋1）－q（q＋1） =p2－q2＋p－q=（p－q）（p＋q＋1）
所以 （Cm+1－Ck）（Cm+2－Ck）?（Cm+n－Ck）
=（m－k＋1）（m－k＋2）?（m－k＋n）2（m＋k＋2）（m＋k＋3）2?2（m＋k＋n＋1）
C1C2?Cn=n！（n＋1）！
因此只需证
nn
=A2B 是整数．
由于n个连续整数之积能被n！整除，故A是整数．
是整数．因为m＋k＋1是大于n＋1的质数，所以m＋k＋1与（n＋1）！互素，从而（m＋k＋2）（m＋k＋3）?（m＋k＋n＋1）能被（n＋1）！整除，于是B也是整数，命题得证．
A4－009 设a、b、m、n是自然数且a与b互素，又a＞1，证明：如果am＋bm能被an＋bn整除，那么m能被n整除． 【题说】第六届（1972年）全苏数学奥林匹克十年级题1． 【证】由于
ak＋bk=ak-n（an＋bn）－bn（ak-n－bk-n） a－b=a（a＋b）－b（a＋b）
l
l
l-n
n
n
n
l-n
l-n
所以
（i）如果a＋b能被a＋b整除，那么a－b（ii）如果a－b能被a＋b整除，那么a＋b
l
l
n
n
l-n
k
k
n
n
k-n
k-n
也能被a＋b整除．
n
n
nn
l-n
也能被a＋b整除．
设m=qn＋r，0?r＜n，由（i）、（ii）知ar＋（－1）qbr能被an＋bn整除，但0?|ar＋（－1）qbr|＜an＋bn，故r=0（同时q是奇数）．亦即n|m．
A4－010 设m，n为任意的非负整数，证明：
是整数（约定0！=1）．
【题说】第十四届（1972年）国际数学奥林匹克题3．本题由英国提供．
易证 f（m＋1，n）=4f（m，n）－f（m，n＋1） （1） n）为整数，则由（1），f（m＋1，n）是整数． 因此，对一切非负整数m、n，f（m，n）是整数． A4－011 证明对任意的自然数n，和数
不能被5整除．
【题说】第十六届（1974年）国际数学奥林匹克题3．本题由罗马尼亚提供．
又
两式相乘得
因为7
2n+1
=7349≡23（－1）（mod 5）
nn
A4－012 设p和q均为自然数，使得
证明：数p可被1979整除．
【题说】第二十一届（1979年）国际数学奥林匹克题1．本题由原联邦德国提供．
将等式两边同乘以1319！，得
其中N是自然数．
由此可见1979整除1319！3p．因为1979是素数，显然不能整除1319！，所以1979整除p．
A4－013 一个六位数能被37整除，它的六个数字各个相同且都不是0．证明：重新排列这个数的六个数字，至少可得到23个不同的能被37整除的六位数．
【题说】第十四届（1980年）全苏数学奥林匹克十年级题1．
（c＋f）被37整除．
由于上述括号中的数字是对称出现的，且各数字不为0，故交换对
又因为100a＋10b＋c=－999c＋10（100c＋10a＋b），所以
各再得7个被37整除的数，这样共得23个六位数．
第二十讲 整数问题：整除之三
A4－014 （a）对于什么样的整数n＞2，有n个连续正整数，其中最大的数是其余n－1个数的最小公倍数的约数？ （b）对于什么样的n＞2，恰有一组正整数具有上述性质？ 【题说】第二十二届（1981年）国际数学奥林匹克题4． 【解】设n个连续正整数中最大的为m．
当n=3时，如果m是m－1，m－2的最小公倍数的约数，那么m整除（m－1）（m－2），由m|（m－1）（m－2）得m|2，与m－2＞0矛盾．
设n=4．由于
m|（m－1）（m－2）（m－3）
初中数学奥林匹克竞赛教程
