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

用同余理论解决整除问题 重庆沙坪坝杨公桥小学 蒋焘摘要：在数的整除理论中，经常要判断一个数能否被另一个数整除。虽然用初等方法也能证明判断的正确性，但其技巧性很强,而技巧性的东西是一时难于捕捉到的。如果用同余理论解决这类问题，就简捷明了。本文主要利用同余性质给出一些整除问题的判别方法并阐述同余理论在整除问题中的一些应用。关键词：同余;整除;判别方法1 同余的基本概念和性质整除性的证明被公认为是中学数学、特别是数学竞赛的难题之一，但用同余思想方法指导解决整除性问题就要容易和易于掌握得多。本文主要阐述同余理论在整除问题中的一些应用。定义1.设a,b是任意两个整数，其中b0，如果存在一个整数q使得等式abq成立，我们就说b能整除a或a能被b整除，记作b|a，否则记作ba 。定义1. 给定一个正整数m，把它叫做模。如果用去除任意两个整数a和b所得的余数相同，我们就说a，b对模同余，记做。如果余数不相同，我们就说a，b对模不同余，记做。定理1.1的充分必要条件是。性质1.1。性质1.2若，则。性质1.3若，则。性质1.4 若，则。 若，则。性质1.5若，则，c为任意整数。性质1.6 若，且，则。性质1.7 若，则。 若，d为a,b及m的任一正公因数，则。性质1.8 同余式组，同时成立的充要条件是。性质1.9 若，则。定理1.23 设是整系数多项式，若，则。定理1.31（Euler） 设m是大于1的整数，,则。定理1.44 若m,则存在,使，我们称c是a对模m的逆，记作。2 利用同余性质给出一些整除的判别法例.任何一个整数，其中，则证法一设故同理可证。证法二设是整系数多项式。由定理1.2得即则对模m=5的情形同理论证。例22 ，其中，则证明 又 于是故对模m=25的情形同理论证。例.3 ，其中，则证明又 于是故对模m=125的情形同理论证。例2.4任何一个整数，其中，则证法一 同理可证。证法二设是整系数多项式。由定理1.2得又所以即同理可证。例2.5任何一个整数，其中，则证明各位数字都是9的偶数位整数都能被11整除，且形如 的偶数位整数也能被11整除。若记整数为 前n项中的每一项都有偶数位因数或10001，都能被11整除。因此，若能被11整除，就能被11整除；若11|a，则11|。例2.6正整数则证明设是整系数多项式。由定理1.2得又所以故对模m=7、13的情形同理论证。例.7 则证明设是整系数多项式。由定理1.2得即故例.设正整数则证明设是整系数多项式。由定理1.2得即故101|a同余理论在整除问题中的应用例3.1 n为非负整数,证明证法一当n=0时，=49+8=57 当n0时， 评注本题的解法之技巧在于加上一项再减去一项,若没有想到此法,则难于得到证明。证法二用同余思想方法证明当n=0时，结论显然成立。当n0时，647（mod57）（mod57）于是=故例3.2 试证 7|+证法一 2222=7317+3 ，5555=7793+4 而+ =（2222+4）M =7318M,MZ = (55554)N =7793N，NZ 于是+ =（+）+（）+ =7（318M+793N）（1） 而（1）= =（1）L =63L =79p;L,pZ +=7(318M+793N+9p) 故7|(+)评注证法一的技巧性非常强，用加，再减去，再用因式分解公式；n是奇数 ；n是正整数证法二用同余思想方法证明 从而 于是 故例.当n为正整数时，证明330能整除证明 因 故又因故又因故由性质1.7得故330|。例3.4证明：当且仅当指数不能被4整除时，能被5整除，其中n是正整数。证明即设，其中是整数，由以上易知当时，故当时，故当时，故当时，故综上所诉，命题得证。例3.5 证明：641| 证明故641|例3. 设3a, 3b,证明3 证明3a,从而3b,从而于是故3例3.(IMO-6-1) 求所有能使被7整除的正整数n。证明：没有正整数n，使得被7整除。解：因由同余性质，有即7|-1于是-1=2（-1）+1，-1=4（-1）+3都不能被7整除。从而，当且仅当3|n时，有7|由于有+1有+1 +1故对任何总有7不整除。例.8设，b的素因子都大于n,证明证明b的素因子都大于n，则。由定理定理1.4知b对模n!有逆，则有 由于式是n个连续整数的积，所以 即 命题得证。 有此可见许多整除性的证明我们可以用同余思想方法作为指导加以证明，避免了整除性证明的技巧性强和移植性差的缺陷，寻找到了一条比较便当的解题途径，收到事半功倍的效果。参考文献：1 闵嗣贺，严士健. 初等数论M. 北京:人民教育出版社,2003. 2 吴美捷. 整数的整除法J.科教论坛,2006，7（2）：90. 3 潘承洞，潘承彪. 初等数论M. 北京: 北京大学出版社,2003. 4 张君达.数论基础M. 北京: 北京科学技术出版社，2002.5 李复中. 初等数论选讲M. 长春:东北师范大学出版社,2003.6 邬永光. 用