资源描述：
《用同余理论解决整除问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、用同余理论解决整除问题重庆沙坪坝杨公桥小学蒋春摘要：在数的整除理论中，经常要判断一个数能否被另一个数整除。虽然用初等方法也能证明判断的正确性，但其技巧性很强，而技巧性的东西是一时难于捕捉到的。如果用同余理论解决这类问题，就简捷明了。木文主要利用同余性质给出一些整除问题的判别方法并阐述同余理论在整除问题中的一些应用。关键词：同余;整除;判别方法1同余的基本概念和性质整除性的证明被公认为是中学数学、特别是数学竞赛的难题之一，但用同余思想方法指导解决整除性问题就要容易和易于掌握得多。本文主要阐述同余理论在整除问题中的一些应用。定义1・1设a,b是任意两个整数，其中bHO,如果存在一个整数q使得等式a
2、=bq成立，我们就说b能整除a或a能被b整除，记作b
3、a,否则记作b”ao定义1.2给定一个止整数m,把它叫做模。如果用m去除任意两个整数3和b所得的余数相同，我们就说a,b对模m同余，记做°三b(mod加)。如果余数不相同，我们就说a,b对模m不同余,记做q芋b(mod”2)。定理1.1a=/?(modm)的充分必要条件是ma-b。性质1.1a三a(mod加)。性质1.2若a=/?(modm),贝0Z?=^(modm)o性质1.3若q三方(mod加)，b=c(mod/7?),则°三c(mod加)。性质1.4若缶三b、(modni),a2=h2(modm),则a{±a2=b{±h2(^mod
4、rri)。若d+方三c(mod加)，贝Jtz=c-/?(modm)。性质1.5若a〕三(mod加)，a2=b2(mod/??),则a}a2=h}h2(modm),吗＜?三b
5、C(mod%),c为任意整数。性质1.6若°三b(mod加)，且Q=Q
6、d,/?=b[d,(d,"2)=l,则坷三也(mod加)。性质1・7若°三b(mod加)，k>o,则ak三bk(modmk)。若a=b(modm),d为a,b及m的任一正公因数，则—=—(mod—)。ddd性质1.8同余式组d三b(mod“)，i二1,2,…,k,同时成立的充要条件是a三b(mod[玛，勒，…'®])o性质1.9若a=b[modm),d
7、m,d>0,贝ija三b(modd)。定理1.2⑶设于(兀)兀"一】+…+a°是整系数多项式,若a=y^(modm),则/(6f)=/(/?)(modm)o定理1.3⑴(Euler)设in是大于1的整数，(a,m)=l,则/""三l(mod加)。定理1.4⑷若m>l,(a,m)=1,则存在cwZ,使co=1(modni),我们称c是a对模m的逆，记作”】。2利用同余性质给出一些整除的判别法例2.1任何一个整数a=anan_{---axaQ,其屮05勺vlO,a”HO,i=0丄2,则2>5
8、a<=>2s5
9、a0证法一设a=anan_{…qx1()+a()•・•2
10、a/”_]・・・d
11、X10/.2
12、
13、anan_{•・・a】x10+a。o2
14、故2
15、au>2
16、a()同理可证5
17、do5
18、a。。证法二设f[x)=anxn+%兀z+・・・+°0是整系数多项式。T10三0(mod2)・•・由定理1.2得/(10)=/(0)(mod2)即a三a{}(mod2)则2
19、ao2
20、a()对模呼5的情形同理论证。例2.2a=anan_y---a2a{aQ,其中0SqvlOqHO,d=0,l,2,・贝!J4>25
21、ao4、25恒品0证明•:a=anan_{・・•偽x100+qa。又•/100=0(mod4):.anan_{…色x100三anan_Y…勺x0(mod4)于是d三qq)(mod4)故41au>4
22、d[
23、d()对模沪25的情形同理论证。例2.3a=anan_l---a2aiaQ,其中0WqvlO,a“HO,i=0,l,2,则8、125
24、008、125
25、02坷。0证明*.*a=anan_{•••a3x1000+a2axaQ又*.*1000=0(mod8)/.anan_x・••冬x1000=anan_x…a3xO(mod8)于是a三(mod8)故81«81a2a}a{}对模m二125的情形同理论证。例2.4任何一个整数a=anan_x---axa{},其中05再vl0,a”工0,则3、91ao3、9
26、工q/=0证法一・.•a=anan_x…qa()=ClnX10"+x10?,1+…+G]X10+d
27、()=x(9+1)'+%x(9+1)"'+…+a〕x(9+1)+q=a”X(9q“+1)+勺_]X(9%_]+1)+•••+qx(9+1)+q()=9q+an+an_x+・・・+坷+a()n匸0”•I31a<=>31工yto”同理可证9
28、ao心。/=0证法二设/（兀）=色兀"+%兀心+…+Q。是整系数多项式。V10=l(mod3)・・・由定理1.2得/(10)三/(l)(mod3)又/(10)=d
