初等数论第三章同余

第三章同余§1同余的概念及其基本性质定义设加称之为模若用相去除两个整数〃与所得的余数相同，则1W Z+,5称Q,Z对模相同余，记作a=b modm；若所得的余数不同，则称，匕对模相不同余，记作a mod mo例如，；所有偶数［三所有奇数三8=1mod7,0mod2,Q1mod2同余是整数之间的一种关系，它具有下列性质、；反身性1a=a mod m、若〃三机，贝脑三〃机；对称性25mod mod、若〃三，则三；传递性故同余关3b mod m b=c mod m,c mod m系是等价关系定理整数对模相同余的充分必要条件是即1m\a-a=b+mt,t eZo证明设=+r,b=mq+r,0r rm,5112212则a=b modrri r=r oa—b=mq-q m\a-bo1212性质若贝；11a=b mod m,a=b mod m,=b+b modmiJ〃+〃11221212若则〃三一2Q+b=c modTn,c b modm性质若根，则；2a=b modni,a=b mod=b b modm11221212特别地，若三根，则Z modka=kb modmo贝Aij Zx%a--a1_Vo1ka…a；特别地，1k modm=b modm,・・Xaya=乙」万ya〔•••k定理若三纥…，弓三匕孙2A-a a modm mod12…贝・・・〃i=lj a+a xn-y+—b a=b xn+b++mod mon nH-10〃一10a=b modrri性质若则131=a d,b-bd,d,m=a=b modm,1§4欧拉定理・费马定理定理设根Z,贝三根1Euler EmL a,m=L1mod证设厂,…,是模阳的简化剩余系，则…,〃也是模相的简r12p7/212pm化剩余系，于是・・““♦a=r r---r modm,12pm12p,nBP6Z P^r r•••r=r r•••r mod加,又r,m=r,m=・・・r,m=1,〃〃12p/H12p12p故厂厂从而叭⑼三根…r,m=L Q1mod12P77推论定理若.是质数，则Fermat=a mod p证若则由定理可知三从而〃三〃a,p=l,1QPT1mod p,P mod p若，则故三p w1,p|4,a mod po例设是奇质数，证明L p〃-；112-1+2P-1+,,,+-lp-i=1mod p21P+2P+・・・+p—1P=0modp；-若加丰贝321mod p,U1+2m-|p-1^=0mod p证由费马定理可知三，11modp,i=1,2…,p—1,〃1-1+2P-1+•••+p—lpT=1+1+***+1=p—1=-1mod po由费马定理可知，〃-2ip=i modp,i=l,2,…1,pp-1故-------1--三\P+2P1-p-P=1+2d1-p-1=0modpo因为是模〃的简化剩余系，所以〃也是模的简化31,2,…,p-12,4,…,2-1p剩余系，于是加三〃+2+,,•+p—12m+2m2+,,•+21n—1m机［加+机］，=212m+,…+p—1modp又团丰故加+机21modp,1m+2・・・+p_1=0modp例设是除与外的任一质数，证明2p25k£Z+,p199--9okp-1个证因为所以po2,5,10k,p=1,由费马定理可知故10k-i=1modp,|iOkp-i-1=99^9oP pkp-1个性质⑴若三，贝!；4a b modmk0,J ak=bk modmka b m是/及小的任一公因数，则一=2=b modm,d—mod—d dd性质…，匕则［三［加，加，…，加］5^a=b modm,i=1,2,bmod ik12反之亦然性质则6=b modni,d\m,d0,a=b moddo性质则因而若能整除，力及根两数7=b modm,«,m=b,rri,d之一，则必能整除中的另一数例求写成十进位数时的个位数码1346解事实上，只需求满足三的数〃因为三3406a mod10,0Va«9329三一所以三三一三一三即个位数码1mod10,3406322031”0319mod10,是9例证明当〃为奇数时，〃当〃为偶数时，〃23|2+1,3/|2+1证明因为三所以当〃为奇数时，〃2-1mod3,2«+1=-1«+1mod3,2三―〃三三故〃当〃为偶数时，〃三―〃+11+1—1+10mod3,3|2+1,2+11三三故〃+11+12mod3,3/|2+1同余性质在算术中的一些应用

一、检查因数的方法、一整数能被或整除的充分必要条件是它的十进位数码之和能被139或整除39证明只需讨论正整数即可任取则可以写成十进位的形式eZ+,a=10〃+〃10«-于是，由三可知Q QI a,0a10101mod3H---------1-n i〃一10・从而+…+〃1=1+ci+••+]mod3,31a31ci+an n72-10〃-10对于同理可证

9、设正整数=+〃…+，贝或210001000-01000,I]7nn-\1+40i或的充分必要条件是或或〃1113|a71113\{a+a+--+[+…,02137证明因为7X11X13=1001o例能被和整除3a=587419239例能被整除，但不能被整除4a=43569339例能被整除；二能被整除5a=6376937a13

二、弃九法验算整数计算结果的方法例设检查计算是否正确6a=28997,b=39495,P=ab=15,解令10a,04Z10«-1H—+n i〃一10〃・・・b=b10+/10e++Z,0b10m mj-10P-c1c1+c,0c100/+0/-1+•••I k/-10则mod9*i j%k=0f=0J=0若*不成立，贝故在本题中，计算不正确UP/ab,注若*不成立，则计算不正确；但否命题不成立1利用同样的方法可以用来验证整数的加、减运算的正确性2§2剩余类及完全剩余系定理设则全体整数可分成根个集合，记作，，,其1m0,K,K…K01中这些集合具有下列性质K={qm+r\q EZ},r=0515---3m-1,r⑴每个整数必包含在而且仅在上述的一个集合中；两个整数同在一个集合的充分必要条件是对模相同余2证设是任一整数，则必有1a=mq+r,0rm,a a于是由〃的存在性可知由的唯一性可知〃只能在中a EK,r Ka ra rICl设整数贝故2a=mq+r,b=mq+r,2=Z modmI or12反之，若三则,/必处于同一中b modm,Q Kr定义定理中的称为模机的剩余类，一个剩余类中的任一11K,K,…,K01m-\数称为它同类数的剩余若根个整数〃中任何两个数都不在同一剩余类，贝以，〃Q,Q,…,4,…,01m-y m-\01称为模帆的一个完全剩余系推论个整数作成模的一个完全剩余系的充分必要条件是它们对模两两m m m不同余例如，下列序列都是模的完全剩余系:m⑴・・・；最小非负完全剩余系0J2,,m-1；20m+1---am+a---m-1m+m-155555电；30—rn+1,•••,_1am+—11m+m-13m mm当为偶数时,4m^广^—+，…厂・1111,…1;222-,,一,••一一2+1・・・1QJ・L-;222m—1rn—1当为奇数时，----，…，----------绝对最小完全剩余系Z7722定理设若通过模的一个完全剩余系，则2n£Z+,a,m=1,be Z,x m也通过模的一个完全剩余系，即若是模团的完全剩余系，ax+b ma,a,…,a01m-1则・・・也是模的完全剩余系aa+b,aa+h,aa+bmm—101证只需证明两两不同余即可，采用反证法aa+haa+h…,aa+bm-101设力，则aa+b=aa+bmod m iw aa=aa modm,i J/J又于是与已知矛盾，•a,m=1,a=a modmiw j,♦I J故・・也是模的完全剩余系aa+haa+h,,aa+bm01m-1定理设团而分别通过模的完全剩3m,eZ+,m,m=1,x,x m,m12121212余系，则也通过模的完全剩余系mx+m x mm211212证因为分别通过个整数，所以通过个整数，x,xmm mx+mx mm51212211212下证这个整数对模两两不同余mm mm1212设三其中，分别是所mx+mxm X,+mx”modmm,xx xxi x,x2112211212112212通过的完全剩余系中的数，则M11m x*=m xmodm,m x=mx modm,2121112122又故三!M这说明m,m=1,x x modm,x=xmodm,mx+m x121112222112所通过的数两两不同余，因此，也通过模的完全剩余系m x+/77X mm211212例设加三都是模根的完全剩余系,10mod2,a,•••,a Rbmm11，…,不是模相的完全剩余系a+b Q+bmm11证因为，〃及〃，…/都是模相的完全剩余系,m11tn同理三上X modm,所以modm,，2，三乙=22i=1z=1z=1从而£〃三+£=M+M=+6Z0mod，•i i i22Z=1Z=1若是模机的完全剩余系,则£+a+b+b Qb=—modm,tn mii211矛盾i=1因此，不是模相的完全剩余系a+b,•••,a+b inm11例证明对任何正整数〃，存在着仅有数字组成的数〃，使得证:21,0考察〃+个数；二，它们对模〃至少有两个在同一同余类中，1…,111〃+1个1设二]，则〃|Zc,b=[1b=cmod n,b-c=[1=a2个1s个1个1s个0例号设他加=，则mwZ+,1beZ,^ax+b]1=通过模机的一个完全剩余系,x证因为通过模相的一个完全剩余系，所以+通过模相的一个完全X QX丁、c/m—1剩余系，从而f通过，卜ax+b\01,m根曲-1++・・・m-1o2§3简化剩余系与欧拉函数定义欧拉函数（（〃）是定义在正整数集上的函数，它的值等于序列1p0,1,2,1中与〃互质的数的个数注若〃是质数，则（（）；若〃是合数，则P Q=Q-1定义如果一个模机的剩余类中的数与相互质，则称它为一个与模相互质的剩2余类在与模相互质的全部剩余类中，从每一类各取一数所作成的数的集合称为模机的一个简化剩余系定理模机的剩余类与模相互质的充分必要条件是此类中有一数与相互质因1此，与模相互质的剩余类的个数为吹加），模相的每一简化剩余系是由与相互质的中（切个对模相不同余的整数组成的证设…，是模机的全部剩余类，若与模相互质，则亿加）；K,K,K K=101一r1反之，若有左（则对于中任一数左有（%［阳）=£K,k K=qm+k,1,r r r rrrr即与模相互质Kr定理若，是（（）个与相互质的整数，并且两两对模相不同余，2Q,…,4p m12（p（M则〃是模加的一个简化剩余系a12（p（〃z）定理若（,刈=通过模机的简化剩余系，则也通过模机的简化剩余31,X QX系证通过（（租）个整数，而且由（）（根）可知（）4X P4,777=1,X,=14%w若（）（力，则三（）（）与已知矛盾，••=1,ox=ax modmiwX xmodmi wj,••J J故以通过模机的简化剩余系定理4设相，加G Z+,（mm）=1,而分别通过模相，加的简化剩512121212余系，则根也通过模根根的简化剩余系x+m x211212证由上一节定理可知，若九分别通过模根，机的完全剩余系，则3x,1212也通过模根机的完全剩余系下证当分别通过模根，根的简mx+mx2112121212化剩余系时，通过模根机的一个完全剩余系中一切与相根互质的mx+m x21121212整数一方面，由（根）=（相）=（加，加）=可知（加，根）（加）x,x,1x=1,x,m=1,112212211122于是（根，）=（）=从而（根根根根）mx+x421,mx+mx,m1,x+x,=1,2112112212211212另一方面，由（mX+MX,根加）=1可知（m x+m x,m）=（mx+mx,m）=1,2112122112112212于是（）（）从而（）（）m x,m=m xj m=1,%m=%m=1552111221122推论设根（）则（（根）=（）（（）m£Z+,m,m=1,p mcp mp m512121212证由定理可知，若分别通过模根，根的简化剩余系，则加4x xx+m x512122112通过模相机的简化剩余系，即通过中（根加）个整数mX+mX12211212另一方面，由于通过中（勿）个整数，通过（（加）个整数，因此，x2x pmx+mx11222112设=，p%…PA定理p%15k2通过加个整数故根根p pmp=pm pmo121212证先证（（）=在模外的完全剩余系中，与小不互质p papa-pa-112…,P则〃p=a\1的数为〃,，〃，共有个，2p,・・・/a-1pa-1=〃故邛（〃）〃-〃-九因此,

①⑷=p/7a

①Pa・・・p pa12k=1k121a—1・・・pa_pa_12k k72k k。