用同余理论解决整除问题.doc

用同余理论解决整除问题重庆沙坪坝杨公桥小学 蒋焘摘　要：在数的整除理论中，经常要判断一个数能否被另一个数整除虽然用初等方法也能证明判断的正确性，但其技巧性很强,而技巧性的东西是一时难于捕捉到的如果用同余理论解决这类问题，就简捷明了本文主要利用同余性质给出一些整除问题的判别方法并阐述同余理论在整除问题中的一些应用关键词：同余;整除;判别方法1 同余的基本概念和性质整除性的证明被公认为是中学数学、特别是数学竞赛的难题之一，但用同余思想方法指导解决整除性问题就要容易和易于掌握得多本文主要阐述同余理论在整除问题中的一些应用定义 1.１ 　 设 a,b 是任意两个整数，其中 b≠0，如果存在一个整数 q 使得等式a＝bq 成立，我们就说 b 能整除 a 或 a 能被 b 整除，记作 b|a，否则记作 b a 定义 1.２ 给定一个正整数 m，把它叫做模如果用ｍ去除任意两个整数 a 和 b 所得的余数相同，我们就说 a，b 对模ｍ同余，记做 如果余数不相同，我们moda就说 a，b 对模ｍ不同余，记做 od定理 1.1　 的充分必要条件是 od|b性质 1.1　 ma性质 1.2　若 ，则 。

bmodba性质 1.3　若 ， ，则 odcodacm性质 1.4 若 ， ，则 1a2121b2od若 ，则 )bc()ab性质 1.5　　 若 ， ，1mod2od则 ， ，c 为任意整数2a1mc性质 1.6 若 ，且 ，则 modab11,,()adbm1(od)abm性质 1.7 若 ， ，则 kodkk若 ，d 为 a,b 及 m 的任一正公因数，则 )性质 1.8 同余式组 ， 同时成立的充要条件是oiab=1,2,L12m,,k性质 1.9 若 ， ，则 d0dodab定理 1.2[3] 设 是整系数多项式，1nnfxaxL若 ，则 omff定理 1.3[1]（Euler） 设 m 是大于 1 的整数， ,则 ,1amod定理 1.4[4] 若 m ,则存在 ,使 ，1、,cZod我们称 c 是 a 对模 m 的逆，记作 1a2 利用同余性质给出一些整除的判别法例２.１　任何一个整数 ，其中 ， 　则10naaL10,ina0,12,.inL025|a|、证法一　设 10na∵ |1nL∴ 2| 02|0a故 0|a|同理可证 。

0|5|证法二　设 是整系数多项式10nnfxaxaL∵ 10mod2∴由定理 1.2 得 0mod2ff即 a0则 2||对模 m=5 的情形同理论证例 2．2 ，其中 ， 　则120naaL10,ina0,12,.inL1045||、证明　∵ 210n又∵ mod4∴ 12120mod4nnaaLL于是故 104||对模 m=25 的情形同理论证例２.3　 ，其中 ，120naaL10,ina0,12,.inL则 8125||、证明　∵ 13210n又∵ 0mod8∴ 1313mod8nnaaLL于是 20故 18||对模 m=125 的情形同理论证例 2.4　任何一个整数 ，其中 ，则10naaL10,ina039||nia、证法一　∵ 10n110naaL10999nn a11n0naaL09i∴ 3||i同理可证 nia0||证法二　设 是整系数多项式10nnfxaxaL∵ 10(mod3)∴由定理 1.2 得 0mod3ff又 fa01ni所以 即(od3)i0||nia同理可证 。

nia0|9|例 2.5　任何一个整数 ，其中 ，则10nL10,ina01||(1)nii证明　∵各位数字都是 9 的偶数位整数都能被 11 整除，且形如 的偶数位01L整数也能被 11 整除∴若记整数 为10naaL11110[0()][()][0()1]nnnn aaL1 0][()nn ii 前 n 项中的每一项都有偶数位因数 或 100…01，都能被 11 整除9L因此，若 能被 11 整除， 就能被 11 整除；若 11|a，则 11| 0()niiaa niia01例 2.6　正整数 111000nnn a则1,,1,2.inaiL073|73|()nii、证明　设 是整系数多项式10nnfxaxa∵ 0(mod)∴由定理 1.2 得 0modff又 1fa0nii所以 od1ii故 01||niiaa对模 m=7、13 的情形同理论证例２.7 2 11100nnn aL则01,0,1,2.inainL037||nia证明　设 是整系数多项式。

1nfxax∵ (mod37)∴由定理 1.2 得 0mod37ff即 10()nniaaL故 037||ni例２.８　设正整数 11100nnaaL则01,,1,2.inaiLii0||证明　设 是整系数多项式1nnfxaxa∵ 10(mod10)∴由定理 1.2 得 1mod0ff即 0od10niia故 101|a nii0|３　同余理论在整除问题中的应用例 3.1 n 为非负整数,证明 n+2157|8证法一　当 n=0 时， =49+8=57 ∴n+21n+2157|8当 n＞0 时，∵ 2nn=496=4978-nn5+(6)-1n-2147+nLn---1=7[8()]∴　 n+215|评注　本题的解法之技巧在于加上一项再减去一项,若没有想到此法,则难于得到证明证法二　用同余思想方法证明当 n=0 时，结论显然成立当 n＞0 时，∵64≡7（mod57）∴ ≡ （mod57）64n7于是 +218= 9n740mod5故 n+21|8例 3.2 试证 7| +852证法一 ∵2222=7×317+3 ，5555=7×793+4而 +5254=（2222+4）M=7×318M,M∈Z－2524= (5555－4)N=7×793N，N∈Z于是 +522=（ + ）+（ － ）－ +42524524=7×（318M+793N）－ （ －1）3而 （ －1）=232= （ －1）L =63× L44=7×9p;L,p∈Z∴ + =7(318M+793N+9p)522故 7|( + )评注　证法一的技巧性非常强，用加 ， 再减去 ， ，再用因式分解542542公式；n 是奇数12321nnnabababL；n 是正整数n 证法二　用同余思想方法证明∵ 23(mod7),1,∴ (7)16Q从而 6)54(od,71,∴ (7)61m)于是 525223469670(3)(4)0(mod7)故 527|例３.３ 　当 n 为正整数时，证明 330 能整除 2651n证明　 因 30612mod51modn051故 2651odn又因 20mod606n251mn1故 26501od6n又因 2mod631nn5m10故 26530od1nn由性质 1.7 得 26510mod561n故 330| 。

例 3.4 　证明：当且仅当指数ｎ不能被 4 整除时， 能被 5 整除，其4 234nn中 n 是正整数证明　 41mod52431od5即 　4mka,234a设 ，其中 是整数， 由以上易知nrk0,1r1231mod5nr当 时， ，故５0r4r234nn当 时， ，故５｜0r 1当 时， ，故５｜2r13rnn当 时， ，故５｜34r234综上所诉，命题得证例 3.5 　证明：641|5321证明　∵ 423285620541713mod64∴ 320故 641| 1例 3.６ 设 3 a, 3 b,证明 3 2ab证明　∵3 a　∴ ,从而mod1mod3∵3 b　∴ ,从而12于是 23故 3 2ab例 3.７ (IMO-6-1) ①求所有能使 被 7 整除的正整数 n6 21n②证明：没有正整数 n，使得 被 7 整除21n解：①因 321mod7由同余性质，有 3k1od7即 7| -13k于是 -1=2（ -1）+1， -1=4（ -1）+3 都不能被 7 整除。

1232k3k从而，当且仅当 3|n 时，有 7| 1n②由于 3kmod7有 +12有 +131k+125od7故对任何 总有 7 不整除 nN、21n例３.8 　设 ，b 的素因子都大于 n,证明41!|21nabanbL证明　b 的素因子都大于 n，则 由定理定理 1.4 知 b 对模 n!有逆 ，则,!b有 12naaL111b mod!n由于⑴式是 n 个连续整数的积，所以12baanbL0、即 1bodn命题得证　　　　　　　　　 有此可见许多整除性的证明我们可以用同余思想方法作为指导加以证明，避免了整除性证明的技巧性强和移植性差的缺陷，寻找到了一条比较便当的解题途径，收到事半功倍的效果参考文献：[1] 闵嗣贺，严士健. 初等数论[M]. 北京:人民教育出版社,2003. [2] 吴美捷. 整数的整除法[J].科教论坛,2006，7（2）：90. [3] 潘承洞，潘承彪. 初等数论[M]. 北京: 北京大学出版社,2003. ⑴[4] 张君达.数论基础[M]. 北京: 北京科学技术出版社，2002.[5] 李复中. 初等数论选讲[M]. 长春:东北师范大学出版社,2003.[6] 邬永光. 用同余理论证明数的整除[J].内蒙古教育学院学报,1998，12（4）：52-54.[7] 晏能中.数论基础[M]. 成都: 电子科技大学出版社，2005.[8] 乐茂华. 初等数论[M]. 广州:广东高等教育出版社教育出版社,2003. 。