1、竞赛讲座 02整数的整除性1 整数的整除性的有关概念、性质(1) 整除的定义:对于两个整数 a、d(d0),若存在一个整数 p,使得 成立,则称 d整除 a,或 a被 d整除,记作 d|a。若 d不能整除 a,则记作 d a,如 2|6,4 6。(2)性质1) 若 b|a,则 b|(-a),且对任意的非零整数 m有 bm|am2) 若 a|b,b|a,则|a|=|b|;3) 若 b|a,c|b,则 c|a4) 若 b|ac,而(a,b)=1(a,b)=1 表示 a、b 互质,则 b|c;5) 若 b|ac,而 b为质数,则 b|a,或 b|c;6) 若 c|a,c|b,则 c|(ma+nb),
2、其中 m、n 为任意整数(这一性质还可以推广到更多项的和)例 1 (1987 年北京初二数学竞赛题)x,y,z 均为整数,若 11(7x+2y-5z),求证:11(3x-7y+12z)。证明4(3x-7y+12z)+3(7x+2y-5z)=11(3x-2y+3z)而 1111(3x-2y+3z),且 11(7x+2y-5z), 114(3x-7y+12z)又 (11,4)=1 11(3x-7y+12z).2.整除性问题的证明方法(1) 利用数的整除性特征(见第二讲)例 2(1980 年加拿大竞赛题)设 72 的值。解 72=89,且(8,9)=1,所以只需讨论 8、9 都整除 的值。若 8 ,
3、则 8 ,由除法可得。若 9 ,则 9(a+6+7+9+2),得 a=3。(2)利用连续整数之积的性质 任意两个连续整数之积必定是一个奇数与一个偶数之一积,因此一定可被 2整除。 任意三个连续整数之中至少有一个偶数且至少有一个是 3的倍数,所以它们之积一定可以被 2整除,也可被 3整除,所以也可以被 23=6整除。这个性质可以推广到任意个整数连续之积。例 3(1956 年北京竞赛题)证明: 对任何整数 n都为整数,且用 3除时余2。证明 为连续二整数的积,必可被 2整除. 对任何整数 n均为整数, 为整数,即原式为整数.又,2n、2n+1、2n+2 为三个连续整数,其积必是 3的倍数,而 2与
4、 3互质, 是能被 3整除的整数.故 被 3除时余 2.例 4 一整数 a若不能被 2和 3整除,则 a2+23必能被 24整除.证明 a 2+23=(a 2-1)+24,只需证 a2-1可以被 24整除即可.2 .a 为奇数.设 a=2k+1(k为整数),则 a2-1=(2k+1)2-1=4k2+4k=4k(k+1).k、k+1 为二个连续整数,故 k(k+1)必能被 2整除,8|4k(k+1),即 8|(a 2-1).又(a-1),a,(a+1)为三个连续整数,其积必被 3整除,即 3|a(a-1)(a+1)=a(a 2-1),3 a,3|(a 2-1).3 与 8互质, 24|(a 2-
5、1),即 a2+23能被 24整除.(3)利用整数的奇偶性下面我们应用第三讲介绍的整数奇偶性的有关知识来解几个整数问题.例 5 求证:不存在这样的整数 a、b、c、d 使:abcd-a= abcd-b= abcd-c= abcd-d= 证明 由,a(bcd-1)= .右端是奇数,左端 a为奇数,bcd-1 为奇数.同理,由、知 b、c、d 必为奇数,那么 bcd为奇数,bcd-1 必为偶数,则 a(bcd-1)必为偶数,与式右端为奇数矛盾.所以命题得证.例 6 (1985年合肥初中数学竞赛题)设有 n个实数 x1,x2,,x n,其中每一个不是+1 就是-1,且试证 n是 4的倍数.证明 设
6、(i=1,2,,n-1),则 yi不是+1 就是-1,但 y1+y2+yn=0,故其中+1 与-1 的个数相同,设为 k,于是 n=2k.又y1y2y3yn=1,即(-1) k=1,故 k为偶数,n 是 4的倍数.其他方法:整数 a整除整数 b,即 b含有因子 a.这样,要证明 a整除 b,采用各种公式和变形手段从 b中分解出因子 a就成了一条极自然的思路.例 7 (美国第 4届数学邀请赛题)使 n3+100能被 n+10整除的正整数 n的最大值是多少?解 n3+100=(n+10)(n2-10n+100)-900.若 n+100能被 n+10整除,则 900也能被 n+10整除.而且,当 n
7、+10的值为最大时,相应地 n的值为最大.因为 900的最大因子是 900.所以,n+10=900,n=890.例 8 (上海 1989年高二数学竞赛)设 a、b、c 为满足不等式 1abc 的整数,且(ab-1)(bc-1)(ca-1)能被 abc整除,求所有可能数组(a,b,c).解 (ab-1)(bc-1)(ca-1)=a2b2c2-abc(a+b+c)+ab+ac+bc-1,abc|(ab-1)(bc-1)(ca-1).存在正整数 k,使ab+ac+bc-1=kabc, k= k=1.若 a3,此时1= - 矛盾.已知 a1. 只有 a=2.当 a=2时,代入中得 2b+2c-1=bc
8、,即 1= 0b4,知 b=3,从而易得 c=5. 说明:在此例中通过对因数 k的范围讨论,从而逐步确定 a、b、c 是一项重要解题技巧.例 9 (1987 年全国初中联赛题)已知存在整数 n,能使数 被 1987整除.求证数,都能被 1987整除. 证明 (10 3n+),且 能被 1987整除,p 能被 1987整除.同样,q= ( )且故 、10 2(n+1) 、 被 除,余数分别为1000,100,10,于是 q表示式中括号内的数被 除,余数为 1987,它可被 1987整除,所以括号内的数能被 1987整除,即 q能被 1987整除.练习二1 选择题(1)(1987 年上海初中数学竞
9、赛题)若数n=2030405060708090100110120130,则不是 n的因数的最小质数是( ).(A)19 (B)17 (C)13 (D)非上述答案(2)在整数 0、1、2、8、9 中质数有 x个,偶数有 y个,完全平方数有 z个,则 x+y+z等于( ).(A)14 (B)13 (C)12 (D)11 (E)10(3)可除尽 311+518的最小整数是( ).(A)2 (B)3 (C)5 (D)3 11+518(E)以上都不是2 填空题(1)(1973 年加拿大数学竞赛题)把 100000表示为两个整数的乘积,使其中没有一个是 10的整倍数的表达式为_.(2) 一个自然数与 3的
10、和是 5的倍数,与 3的差是 6的倍数,这样的自然数中最小的是_.(3) (1989年全国初中联赛题)在十进制中,各位数码是 0或 1,并且能被 225整除的最小自然数是_.3.求使 为整数的最小自然数 a的值.4.(1971年加拿大数学竞赛题)证明:对一切整数 n,n2+2n+12不是 121的倍数.5.(1984年韶关初二数学竞赛题)设 是一个四位正整数,已知三位正整数 与 246的和是一位正整数 d的 111倍, 又是 18的倍数.求出这个四位数 ,并写出推理运算过程.6.(1954年苏联数学竞赛题)能否有正整数 m、n 满足方程 m2+1954=n2.7.证明:(1)133|(11 n
11、+2+12n+1),其中 n为非负整数.(2)若将(1)中的 11改为任意一个正整数 a,则(1)中的 12,133将作何改动?证明改动后的结论.8.(1986年全国初中数学竞赛题)设 a、b、c 是三个互不相等的正整数.求证:在 a3b-ab3,b3c-bc3,c3a-ca3三个数中,至少有一个能被 10整除.9.(1986年上海初中数学竞赛题)100 个正整数之和为 101101,则它们的最大公约数的最大可能值是多少?证明你的结论.练习参考答案() ()由 2000a为一整数平方可推出 a=5反证法若是的倍数,设 () ()是素数且除尽() ,除尽 除尽() 或,不可能由 是的倍, 可能是,;又 是的倍数, 只能是而, 是() ( )第一项可被整除又 , ()改为改为,改为()改动后命题为() () ,可仿上证明 ( );同理有( );( )若、中有偶数或均为奇数,以上三数总能被整除又在、中若有一个是的倍数,则题中结论必成立若均不能被整除,则 , , 个位数只能是,从而 , , 的个位数是从,中,任取三个两两之差,其中必有或,故题中三式表示的数至少有一个被整除,又、互质设个正整数为 , , ,最大公约数为,并令则 ( ),故知 , , 不可能都是,从而 ,;若取 , ,则满足 ,且,故的最大可能值为