同余理论在数学竞赛中应用

《同余理论在数学竞赛中应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、同余理论在数学竞赛中应用摘要：利用同余理论中同余的定义、性质和重要定理可以解决数学竞赛中有关余数、整除、数列和不定方程等问题。关键词：同余；模；整除；剩余类中图分类号：G633.6文献标识码：A文章编号：1992-7711(2013)13-0118同余理论是初等数论的重要组成部分，也是研究初等数学的有效工具之一。近几年来，在初、高中数学竞赛中，与同余有关的试题越来越多。这就要求我们不但要掌握同余理论，而且要深入探讨同余理论在数学竞赛中的应用，为解决相关问题提供思路和方法。下面结合数学竞赛试题讨论同余理论及其应用。一、同余的基本理论1.同余的相关定义定义1给定一个正整数m,把它叫做模m

2、.如果用m去除任意两个整数a与b所得的余数相同，则称a,b对模m同余，记作a=b(modm)o定义2全体整数可按对模m是否同余分为若干个两两不相交的集合，使得在同一集合中的任意两个数对模m—定同余，而属于不同集合的两个数对模一定不同余。每一个这样的集合称为是模m的一个剩余类。1.同余的基本性质性质1a=b(modm)ma-b.特别地，a=0(modm)ma.性质2若al=bl(modm),a2=b2(modm),则al土a2三bl土b2(modm).性质3若a+b=c(modm),则a=c~b(modm)・性质4若ai=bi(modm),i=l,2,n,则ai=bi(modm),特别

3、地，an=bn(modm)性质5da=db(modm)a=b(modm/(d,m))特别地，当(d,m)=1时dai=db(modm)a=b(modm).性质6对任意的整数a,b和k(k>0),若ak=bk(modmk),贝寸a=b(modm).性质7若a=b(modml),i二1，2,,n,则a=b(mod[ml,m2,,mn]).特别地,当iHj时,若有(mi,mj)=1,贝a=b(modmlm2Lmn).性质8若a=b(modm),dm,d>0,则a=b(modd).2.几个重要的定理定理1(Euler定理)设m是大于1的整数，(a，m)=1,则a(m)=1(modm)其中©(

4、m)是整数的m欧拉函数.定理2(Fermat小定理)设P是素数，则aP-l=l(modP)•定理3一个整数阡能被某个自然数b整除的特征是：这个整数的各数位上的数ai(i=0,1,,n)与对应的10的i次幕除以这个自然数所得到的余数ri(i=0,1,,n)的乘积能被这个自然数整除。即10i=qib+ri(OWri8k+5=5(mod8)8k+7=7(mod8)由性质4,得(8k+l)(8k+3)(8k+5)(8k+7)三1X3X5X7三1(mod8)N=1(mod8)M=1(mod8)将q=l,2,,7带入上式，只有当q=5时才满足.故M=125X5=625,即N的末三位数为625.(

5、3)整除方面由性质1可以看出，同余可以看作是对整除问题的进一步探讨，整除可以看作是同余的一种特例，因而同余与整除有着密切的联系.2.证明整除问题例3.证明18972903n-803n-464n+261n(n为自然数).分析由a=0(modm)ma知，该问题可以转化为证明2903n-803n-464n+261n=0(mod1897)成立.因1897=7X271,且(7,271)=1,所以问题又转化为证明式2903n-803n-464n+261n=0(mod7)2903n-803n-464n+261n=0(mod271)同时成立.解：由同余关系2903=803(mod7),464=261

6、(mod7)和性质4,得2903n=464n(mod7)803n=261n(mod7)由性质2和性质3,得2903n-803n-464n+261n=0(mod7)2903=464(mod271)803=261(mod271)由性质4,得2903n=464n(mod271)803n=261n(mod271)由性质2和性质3,得2903n-803n-464n+261n=0(mod271)由于1897=7X271,且(7,271=1),所以由性质7,得2903n-803n-464n+261n=0(mod1897)3.寻求能被某整数整除的数的特征例4.求证：能被11整除的数的特征是：这个数的

7、偶数位上的数字之和与奇数位上的数字之和的差能被11整除。分析：由定理3知，解决问题的关键在于求出10i=qib+ri中的ri.证明由10=-1(mod11),得102i=l(mod11)(i二0,1,2,……)102i+l=l(mod11)(i=0,1,2,……)N=ail0i=a2il02i+a2i+1102i+l=a2i+a2i+l(mod11)N=0(mod11)二a2i+a2i+l(mod11)=(mod11)1.数列方面数学竞赛中的一些数列问题利