假设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)
初中数学奥林匹克竞赛教程
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)