国际数学奥林匹克试题分类解析—A数论_A4整除

A4整除A4－001证明：当且仅当指数n不能被4整除时，1n＋2n＋3n＋4n能被5整除．【题说】1901年匈牙利数学奥林匹克题1．【证】容易验证14≡24≡34≡44（mod5）假设n=4k＋r，k是整数，r=0，1，2，3．则Sn=1n＋2n＋3n＋4n≡1r＋2r＋3r＋4r（mod5）由此推出，当r=0时，Sn≡4，而当r=1，2，3时，Sn≡0（mod5）．因此，当且仅当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－0031．设n为正整数，证明132n－1是168的倍数．2．问：具有那种性质的自然数n，能使1＋2＋3＋…＋n整除1·2·3…·n．【题说】1956年上海市赛高三复赛题1．【解】1．132n－1=（132）n－1，能被132－1，即168整除．2．问题即何时为整数．（1）若n＋1为奇质数，则（n＋1）2（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整除1·2…·n．A4－004证明：如果三个连续自然数的中间一个是自然数的立方，那么它们的乘积能被504整除．【题说】1957年～1958年波兰数学奥林匹克三试题1．【证】设三个连续自然数的乘积为n=（a3－1）a3（a3＋1）．（1）a≡1，2，-3（mod7）时，7|a3－1．a≡－1，－2，3（mod7）时，7|a3＋1．a≡0（mod7）时，7|a3．因此7|n．（2）当a为偶数时，a3被8整除；而当a为奇数时，a3－1与a3＋1是两个相邻偶数，其中一个被4整除，因此积被8整除．（3）a≡1，－2，4（mod9）时，9|a3－1．a≡－1，2，-4（mod9）时，9|a3＋1．a≡0，±3（mod9）时，9|a3．因此9|n．由于7、8、9互素，所以n被504=7×8×9整除．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．A4－007（a）求出所有正整数n使2n－1能被7整除．（b）证明：没有正整数n能使2n＋1被7整除．【题说】第六届（1964年）国际数学奥林匹克题1．本题由捷克斯洛伐克提供．解的关键是找出2n被7除所得的余数的规律．【证】（a）设m是正整数，则23m=（23）m=（7＋1）m=7k＋1（k是正整数）从而23m+1=2·23m=2（7k＋1）=7k1＋223m+2=4·23m=4（7k＋1）=7k2＋4所以当n=3m时，2n－17k；当n=3m＋1时，2n－1=7k1＋1；当n=3m＋2时，2n－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）能被乘积C1·C2·…·Cn整除．【题说】第九届（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）·（m＋k＋2）（m＋k＋3）·…·（m＋k＋n＋1）C1C2…Cn=n！（n＋1）！因此只需证=A·B是整数．由于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）al－bl=al-n（an＋bn）－bn（al-n＋bl-n）所以（i）如果ak＋bk能被an＋bn整除，那么ak-n－bk-n也能被an＋bn整除．（ii）如果al－bl能被an＋bn整除，那么al-n＋bl-n也能被an＋bn整除．设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．本题由罗马尼亚提供．又两式相乘得因为72n+1=7×49n≡2×（－1）n（mod5）A4－012设p和q均为自然数，使得证明：数p可被1979整除．【题说】第二十一届（1979年）国际数学奥林匹克题1．本题由原联邦德国提供．将等式两边同乘以1319！，得其中N是自然数．由此可见1979整除1319！×p．因为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）所以m|6，而m＞4，故这时只有一组正整数3，4，5，6具有所述性质．设n＞4．由于m|（m－1）（m－2）…（m－n＋1），所以m|（n－1）！取m=（n－1）（n－2），则（n－1）|（m－（n－1）），（n－2）|（m－（n－2））．由于n－1与n－2互质，m－（n－1）与m－（n－2）互质，所以m=（n－1）（n－2）整除m－（n－1）与m－（n－2）的最小公倍数，因而m具有题述性质．类似地，取m=（n－2）（n－3），则m整除m－（n－2）与m－（n－3）的最小公倍数，因而m具有题述性质．所以，当n≥4时，总能找到具有题述性质的一组正整数．当且仅当n=4时，恰有唯一的一组正整数．A4－015求一对正整数a和b，使得：（1）ab（a＋b）不被7整除；（2）（a＋b）7－a7－b7被77整除．证明你的论断．【题说】第二十五届（1984年）国际数学奥林匹克题2．【解】（a＋b）7－a7－b7=7a6b＋21a5b2＋35a4b3＋35a3b4＋21a2b5＋7ab6=7ab[（a5＋b5）＋3ab（a3＋b3）＋5a2b2（a＋b）]=7ab（a＋b）[a4＋2a3b＋3a2b2＋2ab3＋b4]=7ab（a＋b）（a2＋ab＋b2）2取a=18，b=1，则a2＋ab＋b2=a（a＋b）＋b2=343=73．所以（a＋b）7－a7－b7被77整除，ab（a＋b）不被7整除．A4－0161．是否存在14个连续正整数，其中每一个数均至少可被一个不小于2、不大于11的素数整除？2．是否存在21个连续正整数，其中每一个数均至少可被一个不小于2、不大于13的素数整除？【题说】第十五届（1986年）美国数学奥林匹克题1．【解】1．14个连续正整数中，有7个奇数n，n＋2，n＋4，n＋6，n＋8，n＋10，n＋12不能被2整除．这7个奇数中，至多1个被11整除，一个被7整除，2个被5整除，3个被3整除．如果被3整除的数少于3个或被5整除的数少于2个，那么这7个奇数中被3，5，7，11整除的数不足7个．如果恰有3个数被3整除，2个数被5整除，那么，被3整除的数必须是n，n＋6，n＋12，被5整除的2个数必须为n与n＋10或n＋2与n＋12．此时必有一个数n或n＋12同时被3，5整除．即这7个奇数中被3，5，7，11整除的数仍不足7个．不管怎样，这14个连续正整数中必有1个不被2，3，5，7，11任一个整除．故答案为不存在．2．存在．以下21个连续整数－10，－9，…，－1，0，1，2，3，…，10除去±1，其余整数被2，3，5，7之一整除．由中国剩余定理，满足N≡0（mod210）N≡1（mod11）N≡－1（mod13）的整数N存在，于是N－10，N－9，…，N，N＋1，…，N＋10这21个连续整数满足所有要求．A4－018试求出所有的正整数a、b、c，其中1＜a＜b＜c，使得（a－1）（b－1）（c－1）是abc－1的约数．【题说】第三十三届（1992年）国际数学奥林匹克题1．本题由新西兰提供．【解】设x=a－1，y=b－1，z=c－1，则1≤x＜y＜z并且xyz是（x＋1）（y＋1）（z＋1）－1=xyz＋x＋y＋z＋xy＋yz＋zx的约数，从而xyz是x＋y＋z＋xy＋yz＋zx的约数．由于x＋y＋z＋xy＋yz＋zx＜3yz，所以x=1或2．若x=1，则yz是奇数1＋2y＋2z的约数．由于1＋2y＋2z＜4z，所以y=3．并且3z是7＋2z的约数．于是z=7．若x=2，则2yz是2＋3y＋3z＋yz的约数，从而y，z均为偶数，设y=2y1，z=2z1，则4y1z1≤1＋3y1＋3z1＋2y1z1＜6z1＋2y1z1，所以y1＜3．因为y＞x，所以y1=2，y=4．再由8z1是7＋7z1的约数得z1=7，z