1、数学科学学院本科学年论文 竞赛数学中的整除问题- 1 -竞赛数学中的整除问题引言整数的整除性是初等数论的基本内容，虽然它的性质较为简单，但它的解题往往需要一定的技巧，因此在各类数学竞赛中占有一定的比例。运用整除的性质可以解决一些繁琐的问题。整除与其他的数学方法结合是解决一些竞赛数学问题的技巧方法。例如：整除的基本性质，分解因式，按模分类等等，此文章就是研究通过这些技巧的方法来解决一些竞赛中出现的问题。数学科学学院本科学年论文 竞赛数学中的整除问题- 2 -一 整数的整除性的有关概念、性质整除的定义：对于两个整数 a、 d(d0)，若存在一个整数 p，使得 成立，则称 d 整除 a，或 a 被
2、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，且 a c, b c ，则 ab c . 反过来也成立：(a,b)=1， ab c， 则 a c, b c.5) 若 b|ac，而 b 为质数，则 b|a，或 b|c；6) 若 c|a， c|b，则 c|(ma+ nb)，其中 m、 n 为任意整数(这一性质还可以推广到更多项的和)二 解决整除问题常用的几种方法：解决整出
3、问题一般有以下方法：（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 都整除 的
4、值。数学科学学院本科学年论文 竞赛数学中的整除问题- 3 -若 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 均为整数 , 为整数
5、,即原式为整数 .又 ，2n 、 2n+1、 2n+2 为三个连续整数，其积必是 3 的倍数，而 2 与 3 互质， 是能被 3 整除的整数 .故 被 3 除时余 2.例 4 一整数 a 若不能被 2 和 3 整除，则 a 2+23 必能被 24 整除 .证明 a 2+23=(a2-1) +24，只需证 a 2-1 可以被 24 整除即可 .2 .a 为奇数 .设 a=2k+1(k 为整数 ),数学科学学院本科学年论文 竞赛数学中的整除问题- 4 -则 a 2-1=(2k+1)2-1=4k2+4k=4k(k+1).k 、 k+1 为二个连续整数，故 k(k+1)必能被 2 整除，8|4k (k
6、+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-1),即 a 2+23 能被 24 整除 .例 5 使 n 3+100 能被 n+10 整除的正整数 n 的最大值是多少 ?解： n 3+100=(n+10)(n2-10n+100)-900.若 n+100 能被 n+10 整除 ,则 900 也能被 n+10 整除 .而且 ,当 n+10 的值为最大时 ,相应地 n 的值为最大 .因为 900 的最大因子是 900.所以
7、 ,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.数学科学学院本科学
8、年论文 竞赛数学中的整除问题- 5 -（3）用因式分解方法解答数的整除问题定理：n 个连续正整数的积能被 n！整除.（n 的阶乘：n！123n）.例如：a 为整数时，2 a(a+1)， 6 a(a+1)(a+2), 24 a(a+1)(a+2)(a+3)， 性质：若 a 且 a c, 则 a (b c). b公式：（n 为正整数）由(ab)(a n-1+an-2b+abn-2+bn-1)=anb n . 得 (ab)|(a nb n).由(a+b)(a 2na 2n1 b+ab2n1 +b2n)=a2n+1+b2n+1 . 得 (a+b)|(a 2n+1+b2n+1).由(a+b)(a 2n1
9、 a 2n2 b+ab2n2 b 2n1 )=a2nb 2n . 得 (a+b)|(a 2nb 2n).概括起来：齐偶数次幂的差式 a2nb 2n含有因式 ab 和 ab.齐奇数次幂的和或差式 a2n+1b 2n+1或 a2n+1b 2n+1只分别含有因式 ab 或 ab.例如：（a+b）| (a 6b 6), (ab)| (a 8b 8)； (a+b)|(a5+b5)， (ab)|(a 5b 5).例 7：已知:整数 n2. 求证：n 55n 3+4n 能被 120 整除.证明：n 55n 3+4nn(n 45n 2+4)=n(n1)(n+1)(n+2)(n2).(n2) (n1)n(n+1
10、) (n2)是五个连续整数，能被 n!整除， 120n 55n 3+4n.例 8：已知：n 为正整数. 求证：n 3+ n2+ n 是 3 的倍数.1证明：n 3+ n2+ n n（2n 2+3n+1）1= n(n+1)(2n+1)= n(n+1)(n+2+n1)2= n(n+1)(n+2)+ n(n+1)(n1).121 3！n(n+1)(n+2)， 且 3！n(n+1)(n1). 3 n(n+1)(n+2)+ n(n+1)(n1).212数学科学学院本科学年论文 竞赛数学中的整除问题- 6 -即 n3+ n2+ n 是 3 的倍数.1（上两例关键在于创造连续整数）例 9 求证： 332 5
11、51； 1989（1990 19901988 1988）.证明： 2 5512 5111 1132 111 11.(321)|(32 11+111 ) ， 即 332 551. 1990 19901988 19881990 19901988 19901988 19901988 1988.（添两项）（19901988）（1990 19901988 1990）. 即 19892（1990 19901988 1990）. 1988 19901988 1988=19881988(198821)1988 1988（19881） （19881）.即 1990 19901988 198819892N1989
12、1988 19881987. （N 是整数） 19891990 19901988 1988.例 10： 设 n 是正整数， 求证：7（3 2n+1+2n+2）.证明：3 2n+1+2n+233 2n+42n=39 n+42 n32 n 32 n （添两项）（42 n32 n ）（39 n32 n ）（43）3（9 n2 n ）72 n3（92）N . （N 是整数）7（3 2n+1+2n+2）（上两例是设法利用乘法公式）例 11：.设 N ，且 17N, 求 x.782x解：N2078100x=171224176x2x17（1226x）+42x. 17N， 1742x ，当 42x=0. x=
13、2.(此题用到了上面说的性质)(4).按模分类法余数的定义：在等式 AmBr 中，如果 A、B 是整数，m 是正整数，数学科学学院本科学年论文 竞赛数学中的整除问题- 7 -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 类
14、，称为按模 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 分类，它的余数有可加，可乘，可乘方的运算规律。举例如下：（3k 1+1）+(3k 2+1)=3(k1+k2)+2 （余数 112）（4k 1+1）(4k 2+3)=4(4k1k2+3k1+k2)+3 （余数 133）（5k2）
15、225k 220k+4=5(5k24k)+4 （余数 224）以上等式可叙述为： 两个整数除以 3 都余 1，则它们的和除以 3 必余 2。 两个整数除以 4，分别余 1 和 3，则它们的积除以 4 必余 3。 如果整数除以 5，余数是 2 或 3，那么它的平方数除以 5，余数必是4 或 9。余数的乘方，包括一切正整数次幂。如：17 除以 5 余 2 17 6除以 5 的余数是 4 （2 664） 。例 12. 今天是星期日，9 9天后是星期几？分析：一星期是 7 天，选用模 m=7, 求 99除以 7 的余数解：9 9（72） 9，它的余数与 29的余数相同，29（2 3） 38 3（71）
16、 3它的余数与 13相同，9 9天后是星期一。又解：设A表示 A 除以 7 的余数，数学科学学院本科学年论文 竞赛数学中的整除问题- 8 -9 9（72） 92 98 3（71） 31 31例 13. 设 n 为正整数，求 43 n+1 除以 9 的余数。分析：设法把幂的底数化为 9kr 形式解：4 3 n+144 3n=4(43)n=4（64） n4(971) n(971) n除以 9 的余数是 1n=14 3 n+1 除以 9 的余数是 4。例 14. 求证三个连续整数的立方和是 9 的倍数解：设三个连续整数为 n1,n,n+1M=(n1) 3+n3+(n+1)3=3n(n2+2)把整数
17、n 按模 3，分为三类讨论。当 n=3k （k 为整数，下同）时，M33k(3k) 2+2=9k(9k 2+2)当 n=3k+1 时， M3（3k+1） (3k+1) 2+23（3k+1）(9k 2+6k+3)=9(3k+1)(3k2+2k+1)当 n=3k+2 时， M3（3k+2） (3k+2) 2+23（3k+2）(9k 2+12k+6)9(3k+2)(3k 2+4k+2)对任意整数 n，M 都是 9 的倍数。例 15. 求证：方程 x23y 2=17 没有整数解证明：设整数 x 按模 3 分类讨论，当 x3k 时， （3k） 23y 2=17, 3(3k 2y 2)=17当 x=3k1
18、 时， （3k1） 23y 2=17 3(3k22ky 2)=16由左边的整数是 3 的倍数，而右边的 17 和 16 都不是 3 的倍数，上述等式都不能成立，因此，方程 x23y 2=17 没有整数解例 16. 求证：不论 n 取什么整数值，n 2+n+1 都不能被 5 整除证明：把 n 按模 5 分类讨论， 当 n=5k 时，n 2+n+1=(5k)2+5k+1=5(5k2+k)+1当 n=5k1 时，n 2+n+1（5k1） 25k1125k 210k+1+5k115（5k 22kk）21当 n=5k2 时，n 2+n+1（5k2） 25k2125k 220k+4+5k215（5k 24
19、k+k+1）2综上所述，不论 n 取什么整数值，n 2+n+1 都不能被 5 整除数学科学学院本科学年论文 竞赛数学中的整除问题- 9 -又证：n 2+n+1n(n+1)+1n(n+1)是两个连续整数的积，其个位数只能是 0，2，6n 2+n+1 的个位数只能是 1，3，7，故都不能被 5 整除。(5)反证法例 17.已知 a，b 是整数，a2b2 能被 3 整除，求证：a 和 b 都能被 3 整除证 用反证法如果 a，b 不都能被 3 整除，那么有如下两种情况：(1)a，b 两数中恰有一个能被 3 整除，不妨设 3a，3 b令 a=3m，b=3n1(m，n 都是整数)，于是a2+b2=9m2
20、+9n26n+1=3(3m 23n 22n)+1，不是 3 的倍数，矛盾(2)a，b 两数都不能被 3 整除令 a=3m1，b=3n1，则a 2b 2=(3m1)2+(3n1)2=9m 26m+1+9n26n1=3(3m2+3n22m2n)2，不能被 3 整除，矛盾总结：本文介绍了整数的整除性的有关概念性质 以及一些特殊整数的性质，最主要的是讲了一些解决竞赛数学问题的方法。但本文只是讲了简单数的整除。还缺少对整式整除的研究，希望读者在这方面有更好更多的见解。数学科学学院本科学年论文 竞赛数学中的整除问题- 10 -参考文献：1:数论初步 李晓军2:整数的整除性 巨人奥数网3：初中数学竞赛专题选讲 巨人奥数网4：竞赛数学教程第二版 ，陈传理、张同君主编， 高等教育出版社
