xge[中学教育]国际数学奥林匹克试题分类解析—A数论_A4整除

xge[中学教育]国际数学奥林匹克试题分类解析—A数论_A4整除 A4 整除 nnnnA4,001 证明:当且仅当指数n不能被4整除时，1，2，3，4能被5整除( 【题说】1901年匈牙利数学奥林匹克题1( 4444 【证】容易验证1?2?3?4(mod 5) 假设n=4k，r，k是整数，r=0，1，2，3(则 nnnnrrrrS=1，2，3，4?1，2，3，4(mod 5) n 由此推出，当r=0时，S?4，而当r=1，2，3时，S?0(mod 5)(因此，当且仅当n不能被4nn 整除时，S能被5整除( n A4,002 证明:从n个给定的自然数中，总可以挑选出若干个数(至少一个，也可能是全体)， 它们的和能被n整除( 【题说】1948年匈牙利数学奥林匹克题3( 【证】设a，a，…，a是给定的n个数(考察和序列:a，a，a，a，a，a，…，a，a，…12n11212312，a( n 如果所有的和数被n除时余数都不相同，那么必有一个和数被n除时余数为0(此时本题的断言 成立( 如果在n个和数中，有两个余数相同(被n除时)，那么从被加项较多的和数中减去被加项较少 的和数，所得的差能被n整除(此时本题的断言也成立( 2nA4,003 1(设n为正整数，证明13,1是168的倍数( 2(问:具有那种性质的自然数n，能使1，2，3，…，n整除1?2?3…?n( 【题说】1956年上海市赛高三复赛题1( 2n2n2【解】1(13,1=(13),1，能被13,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( 333【证】设三个连续自然数的乘积为n=(a,1)a(a，1)( 33(1)a?1，2，-3(mod 7)时，7|a,1(a?,1，,2，3(mod 7)时，7|a，1(a?0(mod 7) 3时，7|a(因此7|n( 333(2)当a为偶数时，a被8整除;而当a为奇数时，a,1与a，1是两个相邻偶数，其中一个被4整除，因此积被8整除( 33(3)a?1，,2，4(mod 9)时，9|a,1(a?,1，2，-4(mod 9)时，9|a，1(a?0，?3 3(mod 9)时，9|a(因此9|n( 由于7、8、9互素，所以n被504=7×8×9整除( 555A4,005 设x、y、z是任意两两不等的整数，证明(x,y)，(y,z)，(z,x)能被5(y,z)(z,x)(x,y)整除( 【题说】1962年全俄数学奥林匹克十 年级 六年级体育公开课教案九年级家长会课件PPT下载六年级家长会PPT课件一年级上册汉语拼音练习题六年级上册道德与法治课件 题3( 【证】令x,y=u，y,z=v，则z,x=,(u，v)( 555555(x,y)，(y,z)，(z,x)=u，v,(u，v) 22=5uv(n，v)(u，uv，v) 2而 5(y,z)(z,x)(x,y)=,5uv(u，v)(因此，结论成立，而且除后所得商式为u，uv，2222v=x，y，z,2xy,2yz,2xz( 【别证】也可利用因式定理，分别考虑原式含有因式(x,y)，(y,z)，(z,x)以及5( 22A4,006 已知自然数a与b互质，证明:a，b与a，b的最大公约数为1或2( 【题说】1963年全俄数学奥林匹克八年级题4( 22【证】设(a，b，a，b)=d，则d可以整除 222(a，b),(a，b)=2ab 但由于a、b互质，a的质因数不整除a，b，所以d与a互质，同理d与b互质(因此d=1或2( nA4,007 (a)求出所有正整数n使2,1能被7整除( n(b)证明:没有正整数n能使2，1被7整除( 【题说】第六届(1964年)国际数学奥林匹克题1(本题由捷克斯洛伐克提供(解的关键是找出n2被7除所得的余数的规律( 【证】(a)设m是正整数，则 3m3mm2=(2)=(7，1) =7k，1(k是正整数) 3m+13m从而 2=2?2=2(7k，1)=7k，2 1 3m+23m2=4?2=4(7k，1)=7k，4 2 n所以当n=3m时，2,17k; n当n=3m，1时，2,1=7k，1; 1 n当n=3m，2时，2,1=7k，3( 2 n因此，当且仅当n是3的倍数时，2,1能被7整除( nn(b)由(a)可知，2，1被7除，余数只可能是2、3、5(因此，2，1总不能被7整除( A4,008 设k、m和n为正整数，m，k，1是比n，1大的一个质数，记C=s(s，1)(证明:乘s积 (C,C)(C-C)…(C,C) m+1km+2km+nk 能被乘积C?C?…?C整除( 12n 【题说】第九届(1967年)国际数学奥林匹克题3(本题由英国提供( 【证】C,C=p(p，1),q(q，1) pq 22=p,q，p,q=(p,q)(p，q，1) 所以 (C,C)(C,C)…(C,C) m+1km+2km+nk =(m,k，1)(m,k，2)…(m,k，n)?(m，k，2)(m，k，3)?…?(m，k，n，1) CC…C=n～(n，1)～ 12n 因此只需证 =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也是整数，命题得证( mmnnA4,009 设a、b、m、n是自然数且a与b互素，又a,1，证明:如果a，b能被a，b整除，那么m能被n整除( 【题说】第六届(1972年)全苏数学奥林匹克十年级题1( 【证】由于 kkk-nnnnk-nk-na，b=a(a，b),b(a,b) lll-nnnnl-nl-na,b=a(a，b),b(a，b) 所以 kknnk-nk-nnn(i)如果a，b能被a，b整除，那么a,b也能被a，b整除( llnnl-nl-nnn(ii)如果a,b能被a，b整除，那么a，b也能被a，b整除( rqrnnrqr设m=qn，r，0?r,n，由(i)、(ii)知a，(,1)b能被a，b整除，但0?|a，(,1)b| nn,a，b，故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) )为整数，则由(1)，f(m，1，n)是整数( n 因此，对一切非负整数m、n，f(m，n)是整数( A4,011 证明对任意的自然数n，和数 不能被5整除( 【题说】第十六届(1974年)国际数学奥林匹克题3(本题由罗马尼亚提供( 又 两式相乘得 2n+1nn因为7=7×49?2×(,1)(mod 5) 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整除; 7777(2)(a，b),a,b被7整除( 证明你的论断( 【题说】第二十五届(1984年)国际数学奥林匹克题2( 777【解】(a，b),a,b 6524334256=7ab，21ab，35ab，35ab，21ab，7ab 553322=7ab[(a，b)，3ab(a，b)，5ab(a，b)] 432234=7ab(a，b)[a，2ab，3ab，2ab，b] 222=7ab(a，b)(a，ab，b) 22237777取a=18，b=1，则a，ab，b=a(a，b)，b=343=7(所以(a，b),a,b被7整除，ab(a，b)不被7整除( A4,016 1(是否存在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任一个整除(故 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 为不存在( 2(存在(以下21个连续整数 ,10，,9，…，,1，0，1，2，3，…，10 除去?1，其余整数被2，3，5，7之一整除(由中国剩余定理，满足 N?0(mod 210) N?1(mod 11) N?,1(mod 13) 的整数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=2y，z=2z，则4yz?1，11113y，3z，2yz,6z，2yz，所以y,3(因为y,x，所以y=2，y=4(再由8z是7，7z的约数11111111111得z=7，z=14( 1 因此，所求解为(3，5，15)与(2，4，8)( nn019 x与y是两个互素的正整数，且xy?1，n为正偶数(证明:x，y不整除x，y( 【题说】1992年日本数学奥林匹克题1( 【证】由(x，y)=1知(x，y，y)=1，(x，y，xy)=1( 2222当n=2时，x，y=(x，y),2xy(由于x，y,2，所以(x，y)2xy(故(x，y)(x， 2y)( 2k2k假设当n=2k(k?N)时，(x，y)(x，y)(则当n=2(k，1)时，由于 + 2(k+1)2(k+1)2k+12k+12k2kx，y=(x，y)(x，y),xy(x，y) 2(k+1)2(k+1)nn所以(x，y)(x，y)(故对一切正偶数n，x，y不整除x，y( A4,020 证明当且仅当n，1不是奇素数时，前n个自然数的积被前n个自然数的和整除( 【题说】第二十四届(1992年)加拿大数学奥林匹克题1( 若n，1为奇合数，设n，1=qr，q、r为奇数且3?q?r，则n A4,021 找出4个不同的正整数，它们的积能被它们中的任意两个数的和整除( 你能找出一组5个或更多个数具有同样的性质吗, 【题说】1992年英国数学奥林匹克题3( 【解】显然，2、6、10、14满足要求( 任取n个不同的正整数。a、a、…、a，令 12n 2n则n个不同的正整数la、la、…、la中任意两个的和显然整除l，从而整除它们的积laa…12n12 a( n yyA4,022 求最大自然数x，使得对每一个自然数y，x能整除7，12,1( 【题说】1992年友谊杯国际数学竞赛七年级题1( yy【解】当y=1时，7，12y,1=18(假设7，12y,1是18的倍数，因为 y+1yy7，12(y，1),1=6×7，12，(7，12y-1) yy=6×(7，2)，(7，12y-1) y7，2?1，2?0(mod 3) y+1所以，7，12(y，1),1是18的倍数( y从而对一切自然数y，18整除7，12y,1，所求的x即18( nA4,023 证明:若n为大于1的自然数，则2,1不能被n整除( 【题说】1992年友谊杯国际数学竞赛九年级题2( nn【证】若n是偶数，显然有n(2,1)(若n是奇素数，由费马定理知2?2(mod n)，所以 nnp-12,1?1(mod n)，即n(2,1)(若n是奇合数，设p是n的最小素因子，由费马定理知2 i?1(mod P);若i是使2?1(mod P)成立的最小自然数，则2?i?P,1，从而in，设n=qi nrn，r，0,r,i，则2?21(mod p)，即p(2n,1)，故n(2,1)( nnnA4,024 当n为何正整数时，323整除20，16,3,1, 【题说】第三届(1993年)澳门数学奥林匹克第一轮题5( 【解】 323=17×19 当n为偶数时， nnnnn20，16,3,1?1，3,3,1?0(mod 19) nnnnnn20，16,3,1?3，1,3,1?0(mod 17) nnn所以此时323整除20，16,3,1( nnnnnnn当n为奇数时，20，16,3,1?3,1,3?,20(mod 17)，所以此时323不整除20，16 n,3,1( A4,025 设x、y、z都是整数，满足条件 (x,y)(y,z)(z,x)=x，y，z( (*) 试证:x，y，z可以被27整除( 【题说】第十九届(1993年)全俄数学奥林匹克九年级二试题5( 【证】(1)整数x、y、z被3除后余数都相同时，27|(x,y)(y,z)(z,x)，即27|x，y，z( (2) x、y、z被3除后有且仅有两个余数相同，例如x?y(mod 3)，且yz(mod 3)，这时 3x，y，z且3|(x,y)，与(*)式矛盾，可见情形(2)不会发生( (3)x、y、z被3除后余数都不相同，这时3|(x，y，z)，但3(x,y)(y,z)(z,x)(仍 与(*)式矛盾，可见情况(3)也不会发生( 于是，x、y、z除以3余数都相同，并且，27|x，y，z( n2nA4,026 对于自然数n，如果对于任何整数a，只要n|a,1，就有n|a,1，则称n具有性质P( (1)求证每个素数n都具有性质P; (2)求证有无穷多个合数也都具有性质P( 【题说】第三十四届(1993年)IMO预选题(本题由印度提供( p【证】(1)设n=P为素数且p|(a,1)，于是，(a，p)=1(因为 pp-1a,1=a(a,1)，(a,1) p-1由费马小定理p|(a,1)(所以，p|(a,1)，即a?1(mod p)(因而 ia?1(mod p)，i=0，1，2，…，p,1 将这p个同余式加起来即得 p-1p-2a，a，…，a，1?0(mod p) 所以， 2p-1p-2pp|(a,1)(a，a，…，a，1)=a,1 2na?1(mod n)(于是，像(1)一样又可推得n|(a,1)(因此， (q,1)(p,1)(因为q|(p,2)，所以q(p,1)(又因 22,n,p(取大于p的素数，又可获得另一个具有性质P的合数(所以，有无具有性质P(显然p 穷多个合数n具有性质p( 2A4,027 证明:对于自然数k、m和n(不等式[k，m]?[m，n]?[n，k]?[k，m，n]成立( (其中[a，b，c，…，z] 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示数a、b、c，…，z的最小公倍数() 【题说】第二十届(1994年)全俄数学奥林匹克十年级(决赛)题5( 【证】将k、m、n分解(设 其中p(i=1，2，…，l)为不同的素数，α、β、γ为非负整数( iiii 对任一个素因数p，不妨设0?α?β?γ(在所要证明的不等式左边，p的指数为β，γiiiiiii，γ=β，2γ;而右边p的指数为γ?2=2γi( iiiii 因而所要证明的不等式成立( A4,029 证明;所有形如10017，100117，1001117，…的整数皆可被53整除( 【题说】第五十八届(1995年)莫斯科数学奥林匹克八年级题2( 【证】易知第一个数10017可被53整除，而数列中相邻二数的差 也可被53整除，所以数列中所有数皆可被53整除( A4,030 证明:无论在数12008的两个0之间添加多少个3，所得的数都可被19整除( 【题说】第五十八届(1995年)莫斯科数学奥林匹克九年级题7( 【证】我们有 故结论成立( A4,031 设S={1，2，…，50)，求最小自然数k，使S的任一k元子集中都存在两个不同的数a与b，满足(a，b)|ab( 【题说】1996年中国数学奥林匹克(第十一届数学冬令营)题2( 【解】设a、b?S，满足(a，b)|ab，令(a，b)=c， 则 a=ca，b=cb，(a，b)=1( 1111 从而 2c(a，b)=(a，b)|ab=cab 1111 因为(a，b，a)=1，(a，b，b)=1，所以 111111 (a，b)|c 11 由于a、b是S中不同的数，从而a，b?99即 c(a，b)?99，而a，b|c，故有3?a，b?9( 111111在a，b=3时，d=3，6，9，12，15，18，21，24，相应的(a，b)=(3，6)，(6，12)，(9，18)，11 (12，24)，(15，30)，(18，36)，(21，42)，(24，48)(类似地，可得出a，b=4，5，6，7，118，9时的数对(a，b)(将每一对得到的a、b用线相连成右图( S中剩下的25个数与图上画圈的13个数所成的38元集，不含任一对a、b满足(a，b)|ab( 另一方面，S中任一集R，如果元数?39，那么图上至多11个数R，从而12对数(14，35)， (9，18)，(28，21)，(42，7)，(5，20)，(30，15)，(45，36)，(6，3)，(10，40)，(12，4)，(24，8)，(48，16)中至少有一对数都属于R，即R中有a、b满足(a，b)|ab( 综上所述，K=39( A4,032 设自然数x、y、p、n和k满足等式 nnkx+y=p 证明:若n(n,1)是奇数，p是奇素数，则n是数p的正整数幂( 【题说】第二十二届(1996年)全俄数学奥林匹克九年级题3( 【证】不失一般性，设x与y都不被p整除(因为n为奇数，所以 用A表示上式右边(由于p,2，因此x、y中至少有一个数大于1(因为n,1，所以A,1(因为 kA(x，y)=p，所以A被p整除，数x，y也被p整除( 于是得到 n-1n-2n-320?A?x,x(,x)，x(,x),… n-2n-1,x(,x)，(,x)(mod p) n-1即nx?0(mod p)，而x不被素数P整除，所以n被p整除( srsrk对n的任一素因数r，设n=rs，则(x)，(y)=p，根据上面所证，r被p整除，所以r=p，从而n是p的正整数幂( A4,033 是否存在3个大于1的自然数，使得其中每个自然数的平方减1，能分别被其余的每个自然数所整除, 【题说】第二十二届(1996年)全俄数学奥林匹克十一年级题5 22【解】设a?b?c是满足题设条件的三个自然数(因为a,1被b整除，所以a与b互素(又c 22,1能分别被a、b整除，因而被ab整除，于是c,1?ab(另一方面由a?c及b?c得ab?c，矛盾(所以满足题设的数不存在( 222A4,034 是否存在三个相异的素数p、q、r，使qr整除p，d，rp整除q，d，pq整除r，d，其中 (1)d=10; (2)d=11( 【题说】1996年城市数学联赛低年级较高水平题2( 【解】(1)满足条件的素数不存在，事实上，若p、q、r满足条件，不妨设p,q,r(则r?2 22(若不然，pq|14=r，d，与q,2相矛盾)，从而q?r，2，又3，10=19是素数，从而p、q、r不可能是三个连续奇数(因三个连续奇素数中必有一个是3)，所以p?r，6，但 22r，10?pq?(r，6)(r，2)=r，8r，12 这是不可能的( (2)p=5，q=3，r=2满足条件(