论文 竞赛数学中的整除问题.doc

数学科学学院本科学年论文 竞赛数学中的整除问题竞赛数学中的整除问题 引言整数的整除性是初等数论的基本内容，虽然它的性质较为简单，但它的解题往往需要一定的技巧，因此在各类数学竞赛中占有一定的比例。运用整除的性质可以解决一些繁琐的问题。整除与其他的数学方法结合是解决一些竞赛数学问题的技巧方法。例如：整除的基本性质，分解因式，按模分类等等，此文章就是研究通过这些技巧的方法来解决一些竞赛中出现的问题。一 整数的整除性的有关概念、性质整除的定义：对于两个整数 a、 d(d0)，若存在一个整数 p，使得 成立，则称 d整除 a，或 a被 d整除，记作 d|a。若 d不能整除 a，则记作 d a，如 2|6， 4 6。基本性质：1) 若 b|a，则 b|(-a)，且对任意的非零整数 m有 bm|am2) 若 a|b， b|a，则 |a|=|b|;3) 若 b|a， c|b，则 c|a4) 若(a,b)=1，且ac, bc ，则abc . 反过来也成立：(a,b)=1，abc，则ac, bc.5) 若 b|ac，而 b为质数，则 b|a，或 b|c；6) 若 c|a， c|b，则 c|(ma+ nb)，其中 m、 n为任意整数(这一性质还可以推广到更多项的和)二 解决整除问题常用的几种方法：解决整出问题一般有以下方法：（1）利用整除基本性质；（2）利用连续整数之积的性质 (3)分解因式法；(4)按模分类法； (5)反证法（1）利用整除的基本性质；例1 ：已知x， y， z均为整数，若 11|(7x+2y-5z)，求证： 11|(3x-7y+12z)。证明 4(3x-7y+12z)+3(7x+2y-5z)=11(3x-2y+3z)而 11| 11(3x-2y+3z),且 11| (7x+2y-5z), 11| 4(3x-7y+12z)又 (11,4)=1 11| (3x-7y+12z).例2：设 72| 的值。解： 72=89，且(8， 9) =1，所以只需讨论 8、 9都整除 的值。若 8| ，则 8| ，由除法可得b2。若 9| ，则 9|(a+6+7+9+2)，得 a=3。（2）利用连续整数之积的性质 任意两个连续整数之积必定是一个奇数与一个偶数之积，因此一定可被 2整除。 任意三个连续整数之中至少有一个偶数且至少有一个是 3的倍数，所以它们之积一定可以被 2整除，也可被 3整除，所以也可以被 23=6整除。这个性质可以推广到任意个整数连续之积。例3: 证明： 对任何整数 n都为整数，且用 3除时余 2。证明: 为连续二整数的积 ,必可被 2整除 .对任何整数 n均为整数 , 为整数 ,即原式为整数 .又 ，2n 、 2n+1、 2n+2为三个连续整数，其积必是 3的倍数，而 2与 3互质，是能被 3整除的整数 .故 被 3除时余 2.例4 一整数 a若不能被 2和 3整除，则 a2+23必能被 24整除 .证明 a2+23=(a2-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|(a2-1) .又 (a-1)， a，(a+1)为三个连续整数，其积必被 3整除，即 3|a(a-1)(a+1) =a(a2-1)，3 a ， 3|(a2-1) .3与 8互质 , 24|(a2-1),即 a2+23能被 24整除 .例5使 n3+100能被 n+10整除的正整数 n的最大值是多少 ?解： n3+100=(n+10)(n2-10n+100)-900.若 n+100能被 n+10整除 ,则 900也能被 n+10整除 .而且 ,当 n+10的值为最大时 ,相应地 n的值为最大 .因为 900的最大因子是 900.所以 ,n+10=900,n=890.例6：设 a、 b、 c为满足不等式 1 a b c的整数，且(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=- 矛盾 .已知 a 1. 只有 a=2.当 a=2时，代入 中得 2b+2c-1=bc，即 1= 0 b 4，知 b=3，从而易得 c=5.（3）用因式分解方法解答数的整除问题定理：n个连续正整数的积能被n！整除.（n的阶乘：n！123n）.例如：a为整数时，2a(a+1)，6a(a+1)(a+2), 24a(a+1)(a+2)(a+3)， 性质：若a 且ac, 则a(bc).公式：（n为正整数）由(ab)(an-1+an-2b+abn-2+bn-1)=anbn . 得 (ab)|(anbn).由(a+b)(a2na2n1b+ab2n1+b2n)=a2n+1+b2n+1 . 得 (a+b)|(a2n+1+b2n+1).由(a+b)(a2n1a2n2b+ab2n2b2n1)=a2nb2n . 得 (a+b)|(a2nb2n). 概括起来：齐偶数次幂的差式a2nb2n含有因式ab和ab.齐奇数次幂的和或差式a2n+1b2n+1或a2n+1b2n+1只分别含有因式ab或ab.例如：（a+b）| (a6b6), (ab)| (a8b8)； (a+b)|(a5+b5)， (ab)|(a5b5).例7：已知:整数n2.求证：n55n3+4n能被120整除.证明：n55n3+4nn(n45n2+4)=n(n1)(n+1)(n+2)(n2). (n2) (n1)n(n+1) (n2)是五个连续整数，能被n!整除，120n55n3+4n.例8：已知：n为正整数.求证：n3+n2+n是3的倍数.证明：n3+n2+nn（2n2+3n+1）=n(n+1)(2n+1) =n(n+1)(n+2+n1)= n(n+1)(n+2)+ n(n+1)(n1).3！n(n+1)(n+2)，且3！n(n+1)(n1).3n(n+1)(n+2)+ n(n+1)(n1).即n3+n2+n是3的倍数.（上两例关键在于创造连续整数）例 9求证：332551；1989（1990199019881988）.证明：255125111113211111.(321)|(3211+111 ) ， 即332551.199019901988198819901990198819901988199019881988.（添两项）（19901988）（1990199019881990）.即19892（1990199019881990）.1988199019881988=19881988(198821)19881988（19881）（19881）.即199019901988198819892N1989198819881987.（N是整数）19891990199019881988.例10：设n是正整数，求证：7（32n+1+2n+2）. 证明：32n+1+2n+2332n+42n=39 n+42 n32n32n（添两项）（42 n32n）（39 n32n）（43）3（9 n2n）72 n3（92）N . （N是整数）7（32n+1+2n+2）（上两例是设法利用乘法公式）例11：.设N，且17N, 求x.解：N2078100x=171224176x2x17（1226x）+42x.17N，1742x ，当 42x=0. x=2.(此题用到了上面说的性质)(4).按模分类法余数的定义：在等式AmBr中，如果A、B是整数，m是正整数，r为小于m的非负整数，那么我们称r是A 除以m的余数。即：在整数集合中被除数除数商余数 (0余数除数)例如：13，0，1，9除以5的余数分别是3，0，4，1（15（1）4。95（2）1。）1） 显然，整数除以正整数m ,它的余数只有m种。例如 整数除以2，余数只有0和1两种，除以3则余数有0、1、2三种。2） 整数的一种分类：按整数除以正整数m的余数，分为m类，称为按模m分类。例如：m=2时，分为偶数、奇数两类，记作2k,2k1（k为整数）m=3时，分为三类，记作3k,3k+1,3k+2. 或3k,3k+1，3k1其中3k1表示除以3余2。m=5时，分为五类，5k.5k+1,5k+2,5k+3,5k+4 或5k,5k1,5k2，其中5k2表示除以5余3。3） 余数的性质：整数按某个模m分类，它的余数有可加，可乘，可乘方的运算规律。举例如下：（3k1+1）+(3k2+1)=3(k1+k2)+2 （余数112） （4k1+1）(4k2+3)=4(4k1k2+3k1+k2)+3（余数133）（5k2）225k220k+4=5(5k24k)+4（余数224）以上等式可叙述为： 两个整数除以3都余1，则它们的和除以3必余2。 两个整数除以4，分别余1和3，则它们的积除以4必余3。 如果整数除以5，余数是2或3，那么它的平方数除以5，余数必是4或9。余数的乘方，包括一切正整数次幂。如：17除以5余2 176除以5的余数是4 （2664）。例12. 今天是星期日，99天后是星期几？分析：一星期是7天，选用模m=7, 求99除以7的余数解：99（72）9，它的余数与29的余数相同，29（23）383（71）3它的余数与13相同，99天后是星期一。又解：设A表示A除以7的余数，99（72）92983（71）3131例13. 设n为正整数，求43 n+1 除以9的余数。分析：设法把幂的底数化为9kr形式解：43 n+1443n=4(43)n=4（64）n4(971)n (971)n除以9的余数是1n=143 n+1 除以9的余数是4。例14. 求证三个连续整数的立方和是9的倍数解：设三个连续整数为n1,n,n+1M=(n1)3+n3+(n+1)3=3n(n2+2) 把整数n按模3，分为三类讨论。当n=3k （k为整数，下同）时，M33k(3k)2+2=9k(9k2+2)当n=3k+1时，M3（3k+1）(3k+1)2+23（3k+1）(9k2+6k+3)=9(3k+1)(3k2+2k+1)当n=3k+2时，M3（3k+2）(3k+2)2+23（3k+2）(9k2+12k+6)9(3k+2)(3k2+4k+2)对任意整数n，M都是9的倍数。例15. 求证：方程x23y2=17没有整数解证明：设整数x按模3分类讨论，当x3k时，（3k）23y2=17, 3(3k2y2)=17当x=3k1时，（3k1）23y2=17 3(3k22ky2)=16由左边的整数是3的倍数，而右边的17和16都不是3的倍数，上述等式都不能成立，因此，方程x23y2=17没有整数解例16. 求证：不论n取什么整数值，n2+n+1都不能被5整除证明：把n按模5分类讨论， 当n=5k时，n2+n+1=(5k)2+5k+1=5(5k2+k)+1当n=5k1 时，n2+n+1（5k1）25k1125k210k+1+5k115（5k22kk）21当n=5k2时，n2+n+1（5k2）25k2125k220k+4+5k215（5k24k+k+1）2综上所述，不论n取什么整数值，n2+n+1都不能被5整除又证：n2+n+1n(n+1)+1 n(n+1)是两个连续整数的积，其个位数只能是0，2，6n2+n+1的个位数只能是1，3，7，故都不能被5整除。(5)反证法例17.已知a，b是整数，a2b2能被3整除，求证：a和b都能被3整除证 用反证法如果a，b不都能被3整除，那么有如下两种情况：(1)a，b两数中恰有一个能被3整除，不妨设3a，3b令a=3m，b=3n1(m，n都是整数)，于是a2+b2=9m2+9n26n+1=3(3m23n22n)+1，不是3的倍数，矛盾(2)a，b两数都不能被