合同-一次同余式-ou.ppt

5.3合同合同一次同余式一次同余式引入引入看任意整数看任意整数a除以除以3所得的余数：所得的余数：003+0;103+1;-1(-1)3+2;203+2;-2(-1)3+1;可以看到余数有三种情况：可以看到余数有三种情况：0,1,2;对于对于-1和和2,它们除以它们除以3余数相同，两式相减则有：余数相同，两式相减则有：2-(-1)=(0-(-1)3+(2-2)，则，则，3|(2-(-1)引入引入引入一种新的记法来对引入一种新的记法来对3|(2-(-1)进行表达：进行表达：2-1(mod3)则，还有下面的式子：则，还有下面的式子：3 0(mod3)0 3(mod3)4 1(mod3)1 4(mod3)5 2(mod3)2 5(mod3)5.3.1合同及其性质合同及其性质 定义定义.设设a,b为二整数，为二整数，m是任意非是任意非0整数。整数。若若m|a-b，则称，则称a合同于合同于b模模m。记为：记为：a b(modm)Note:(1)合同为整除的另一种表示法，故整除的性质合同为整除的另一种表示法，故整除的性质在此可用。在此可用。特别地，若特别地，若b=0，则，则a 0(modm)表示的就是表示的就是m|a。(2)若若m|a，则，则-m|a。所以，若未指定。所以，若未指定m而一般地而一般地讨论模讨论模m合同时，总假定合同时，总假定m是正整数是正整数。5.3.1合同及其性质合同及其性质 (3)设设a=q1m+r1，0r1m；b=q2m+r2，0r2m。于是于是a-b=(q1-q2)m+(r1-r2)则则m|(a-b)iffm|(r1-r2)，但但|r1-r2|1。设设mm1m2，在模，在模m时属于同一剩时属于同一剩余类的整数，在模余类的整数，在模m1(或者模或者模m2)时时必定属于同一个剩余类，但在模必定属于同一个剩余类，但在模mq时就会被分到时就会被分到q个不同的剩余类中。个不同的剩余类中。合同的基本性质合同的基本性质性质性质11若若ac bc(modm)，且（且（c,m）=d，则则a b(modm/d)证明：由证明：由ac bc(modm)知，知，m|(a-b)c，而而(c,m)=d，故故m/d|(a-b)c/d。注意到注意到（m/d,c/d）=1，所以由所以由定理定理5.2.2，m/d|(a-b)，即即a b(modm/d)。合同的基本性质合同的基本性质对于对于质数模质数模p(即即模模p为质数，如为质数，如mod3)，则有与相等完全类似的消去律。则有与相等完全类似的消去律。性质性质12若若p为质数，为质数，c 0(modp)，而而ac bc(modp)，则则a b(modp)。证明：因为证明：因为p是质数，是质数，c 0(modp)就表示就表示p|c,即即c和和p互质，互质，(c,p)=1，因而性因而性质质12不过是性质不过是性质10的推论的推论(原来的整原来的整数模数模m换成了现在的质数模换成了现在的质数模p)。合同的基本性质合同的基本性质性质性质13设设p(x)是整系数多项式，是整系数多项式，x和和y是整数变量，是整数变量，则由则由x y(modm)可得可得p(x)p(y)(modm)。证明：设证明：设p(x)=anxn+an-1xn-1+a1x1+a0,p(y)=anyn+an-1yn-1+a1y1+a0,由由x y(modm)和性质和性质8,xk yk(modm).由性质由性质7得得akxk akyk(modm).由性质由性质4得得anxn+an-1xn-1+a1x1+a0 anyn+an-1yn-1+a1y1+a0(modm).即即p(x)p(y)(modm)。例例.求能被求能被9整除的正整数的整除的正整数的数码特征数码特征。设设N=an10n+an-110n-1+a110+a0为一整数，为一整数，因为因为10 1(mod9)，由性质由性质13得得N an1n+an-11n-1+a1+a0(mod9)即即。于是于是9|N当且仅当当且仅当9|模模m合同既然是一种等价关系，就可以把合同既然是一种等价关系，就可以把所有整数按照模所有整数按照模m合同的关系分为等价类，合同的关系分为等价类，每一个等价类称为模每一个等价类称为模m的一个剩余类。的一个剩余类。同一个剩余类中的数互相合同，不同的剩同一个剩余类中的数互相合同，不同的剩余类中的数不互相合同。余类中的数不互相合同。因为以因为以m去除任意整数，可能得到的余数去除任意整数，可能得到的余数恰有恰有0，1，m-1，这这m个数，所以模个数，所以模m共有共有m个剩余类，用个剩余类，用a表示表示a所在的剩余类。所在的剩余类。剩余类间的运算剩余类间的运算设设S为由模为由模m的所有剩余类组成的集合，在的所有剩余类组成的集合，在S上定义上定义和和两种运算。两种运算。这样规定合理吗？这样规定合理吗？记为，为，则对于任意剩余类记为，为，则对于任意剩余类求求在模的剩余类集合中是否存在元素满在模的剩余类集合中是否存在元素满足？记足？记若剩余类若剩余类A中存在与中存在与m互质的元素，则互质的元素，则存在。存在。在模的剩余类集合中在模的剩余类集合中ABAC成成立立未必能保证未必能保证BC成立。成立。例如，在模例如，在模6的剩余类集合中的剩余类集合中3135不不能得出能得出15但是，若但是，若存在时，由存在时，由 ABAC可可以得到以得到BC。若剩余类若剩余类A中存在中存在a与与m互质，则互质，则A中任意元中任意元素素x均与均与m互质。互质。结论结论5.3.2剩余类剩余类一次同余式一次同余式模模m合同既然是一种等价关系，就可以把合同既然是一种等价关系，就可以把所有整数按照模所有整数按照模m合同的关系分为等价类，合同的关系分为等价类，每一个等价类称为模每一个等价类称为模m的一个的一个剩余类剩余类。例如，整数集合例如，整数集合Z，模，模3，得到：，得到：余数为余数为0:,-6,-3,0,3,6,余数为余数为1:,-5,-2,1,4,7,余数为余数为2:,-4,-1,2,5,8,5.3.2剩余类剩余类一次同余式一次同余式同一个剩余类中的数互相合同，不同的剩同一个剩余类中的数互相合同，不同的剩余类中的数不互相合同。余类中的数不互相合同。因为以因为以m去除任意整数，可能得到的余数去除任意整数，可能得到的余数恰有恰有0，1，m-1，这这m个数，所以个数，所以模模m共有共有m个剩余类个剩余类.5.3.2剩余类剩余类一次同余式一次同余式从模从模m每个剩余类中每个剩余类中任意任意取出取出一个数一个数作为代表，作为代表，得到得到m个数，比方个数，比方r1,r2,rm，称这，称这m个数作成个数作成一个一个完全剩余系完全剩余系。例例0，1，m-1便是这样一个完全剩余系，便是这样一个完全剩余系，称为模称为模m的非负最小完全剩余系。的非负最小完全剩余系。任意整数模任意整数模m恰好恰好合同于此完全剩余系中的一个合同于此完全剩余系中的一个数。数。例例模模3，三个数，三个数0，1，2作成一个完全剩余系，作成一个完全剩余系，-1，0，1也作成一个完全剩余系。也作成一个完全剩余系。例例模模2，两个数，两个数0，1作成一个完全剩余系，作成一个完全剩余系，0代代表所有偶数，表所有偶数，1代表所有奇数代表所有奇数.5.3.2剩余类剩余类一次同余式一次同余式由模由模m的全部剩余类构成的集合称为该等价关的全部剩余类构成的集合称为该等价关系（模系（模m合同关系）的商集，商集是惟一确定的。合同关系）的商集，商集是惟一确定的。模模m的完全剩余系在形式上不惟一。的完全剩余系在形式上不惟一。例例模模3，三个数，三个数0，1，2作成一个完全剩余系，作成一个完全剩余系，-1，0，1也作成一个完全剩余系。也作成一个完全剩余系。即，模即，模m的不同的完全剩余系间可以建立双射。的不同的完全剩余系间可以建立双射。m个整数构成模个整数构成模m的完全剩余系，的完全剩余系，这这m个整数中不存在模个整数中不存在模m合同的两个数合同的两个数(这这m个个整数中任何两个数模整数中任何两个数模m均不同余均不同余)。证明：证明：()A=0,1,2,m-1记记m个整数构成的集合为个整数构成的集合为B=b1,b2,bm对于对于任意的任意的bi，存在，存在A中元素中元素f(bi)满足满足bi f(bi)(modm)。则则f为集合为集合B到到A的映射，由已知，的映射，由已知，f为单射为单射，又，又|B|=m=|A|，则，则f为双射，故这为双射，故这m个整个整数构成了模数构成了模m的完全剩余系。的完全剩余系。注意注意若若|A|=|B|，存在从，存在从B到到A内内的单射的单射f，则，则f未必为满射。未必为满射。例如，为例如，为A无限集。无限集。同余式同余式有棋子若干枚，三个三个的数剩两个，问有棋子若干枚，三个三个的数剩两个，问至少有多少个棋子？至少有多少个棋子？答：由题意，棋子的个数减答：由题意，棋子的个数减2是是3的倍数，的倍数，从而从而有，有，(x-2)=3y,x0，用合同式表示为：，用合同式表示为：x2(mod3)，从而棋子的个数可能是：，从而棋子的个数可能是：2,5,7,，都是，都是mod3合同合同2。同余式同余式含有整数变量的合同式，称为合同方程或含有整数变量的合同式，称为合同方程或同余式同余式。ax b(modm)这种形式的合同式称为一这种形式的合同式称为一次同余式；类似地，次同余式；类似地，a2x2+a1x b(modm)称称为二次同余式。为二次同余式。同余式同余式求解一次同余式求解一次同余式ax b(modm)实际上是实际上是解解ax-b=my这样的不定方程。这里讨论一这样的不定方程。这里讨论一次同余式在什么条件下次同余式在什么条件下有解有解？什么条件下？什么条件下无解无解？什么时候有？什么时候有唯一解唯一解（一个剩余类）（一个剩余类）？什么时候有？什么时候有多解多解（多个剩余类）？（多个剩余类）？定理定理5.3.1若若a和和m互质，互质，b任意，则模任意，则模m恰有一个恰有一个数数x使使ax b(modm)。证明：证明：存在性存在性。因为。因为a和和m互质，根据定理互质，根据定理5.2.1，有，有s，t使使as+mt=1，于是于是asb+mtb=b，若取模若取模m，则有则有asb b(modm)。取取x=sb，则则sb所在的剩余类中的数皆是解。所在的剩余类中的数皆是解。Note:证明过程也给出了证明过程也给出了x的求解方法。的求解方法。定理定理5.3.1若若a和和m互质，互质，b任意，则模任意，则模m恰有一个恰有一个数数x使使ax b(modm)。证明：证明：唯一性唯一性。所谓模。所谓模m只有一个这样的只有一个这样的x，意思是说在模意思是说在模m合同的意义下，解是唯合同的意义下，解是唯一的。即若一的。即若ax b(modm)，ay b(modm)，则则x y(modm)。因为，由因为，由ax b(modm)，ay b(modm)得得ax ay(modm)，消去和消去和m互质的互质的a得得x y(modm).即即x,y在一个剩在一个剩余类中。余类中。定理定理5.3.1推论推论设设p为质数。若为质数。若a 0(modp)，b任意，任意，则模则模p恰有一个数恰有一个数x使使ax b(modp)。证明：由已知，证明：由已知，a a与与p p互质，再由互质，再由定理定理5.3.1，模，模p恰有一个数恰有一个数x使使ax b(modp)。例例解合同式解合同式35x1(mod97)解：解：a=35,m=97,首先使用辗转相除方法将互首先使用辗转相除方法将互质的质的a与与m的最大公因数的最大公因数1表示为表示为a和和m的倍数的倍数和的形式：和的形式：1=as+mt，然后取然后取x=sb，即可。即可。k01234567rk352783210qk0213212Sk0123112536Tk10114913例例从而从而(35,97)=1，n=6,则则xsb=(-1)6-1361=-36(mod97)，即：，即：x61(mod97)求解一次合同方程的方法求解一次合同方程的方法 以解合同式以解合同式103x 57(mod211)为例为例.方法一方法一:定理定理5.3.1告诉我们若告诉我们若a和和m互质，互质，b任意，任意，则模则模m恰有一个数恰有一个数x使使ax b(modm)。该定理证该定理证明存在性的过程即告诉了我们一种求解方法：因明存在性的过程即告诉了我们一种求解方法：因为为a和和m互质，故有互质，故有s，t使使as+mt=1，于是于是asb+mtb=b，若取模若取模m，则有则有asb b(modm)。取取x=sb，则则sb所在的剩余类中的数皆是解。因此，所在的剩余类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的方法一就是先使用辗转相除方法将互质的a与与m的最大公因数的最大公因数1表示为表示为a和和m的倍数和的形式：的倍数和的形式：1=as+mt，然后取然后取x=sb，即可。即可。求解一次合同方程的方法求解一次合同方程的方法解解：103与与211互互质质，先先将将103与与211的的最最大大公公因因数数1表表示示为为它它们们的的倍倍数数和和的的形形式式。使使用用辗辗转转相相除除方方法逐次得商及余数并计算法逐次得商及余数并计算Sk，Tk如下表所示：如下表所示：k012345rk53210qk220113Sk01202141Tk12414384求解一次合同方程的方法求解一次合同方程的方法因此，因此，1=（-1）341211+（-1）484103。由此知，由此知，S=（-1）484，所以所以x=sb=8457=4788=21123-65-65(mod211)。求解一次合同方程的方法求解一次合同方程的方法方法二方法二:就是利用合同的性质，使就是利用合同的性质，使x的系数变成的系数变成1，即得到解。，即得到解。对于上例解合同式对于上例解合同式103x 57(mod211)。由于由于211=1032+5，由合同的性质由合同的性质7有有2103x 257(mod211)。因为因为211x 0(mod211)，所以由合同的性质所以由合同的性质5知，知，211x-2103x 0-257(mod211)。即即5x-114(mod211)97(mod211)。求解一次合同方程的方法求解一次合同方程的方法由于由于211=425+1由合同的性质由合同的性质7有有425x 4297 21119+65 65(mod211)。由合同的性质由合同的性质5知，知，211x-425x 0-65(mod211)。即即x-65(mod211)。对于一些例子，使用这种方法是比较快的。比如，解合同对于一些例子，使用这种方法是比较快的。比如，解合同式式4x 1(mod15)。因为因为1 16(mod15)，所以所以4x 1 16 44(mod15)，因为因为4与与15互质，由合同的性质互质，由合同的性质10知，合同式两边可以消知，合同式两边可以消去去4，得到，得到x 4(mod15)。例例.解合同式解合同式14x 27(mod31)。解：解：14x 58(mod31)7x 29(mod31)7x 91(mod31)x 13(mod31)还可以：还可以：28x 54(mod31)31x 0(mod31)故故3x-54(mod31)x-18(mod31)13(mod31)求解一次合同方程的方法求解一次合同方程的方法方法三方法三:利用利用Fermat-Euler定理（下节再介绍）。定理（下节再介绍）。例例.解合同式解合同式7x 5(mod10)。解：因为解：因为7和和10互质，由互质，由Fermat-Euler定理有定理有7(10)1(mod10)，因因(10)=4，所所以以74 1(mod10)。由由合合同同的的性性质质7，在在7x 5(mod10)两边乘以两边乘以73，有，有737x 735(mod10)，而而737x=74x x(mod10)，735=7275（-1）75 5(mod10)，所以所给合同式的解为所以所给合同式的解为x 5(mod10)。定理定理5.3.2若若(a,m)=d 1，且且d|b，则同余式则同余式ax b(modm)无解。无解。证明：证明：反证法。若上式可解，则存在反证法。若上式可解，则存在，使使得得a b(modm)。从而存在从而存在q，使使a-b=mq,即即b=a-mq。因为因为(a,m)=d 1，所以，所以，d|a,d|m，因此，因此，d|a，d|mq，故故d|(a-mq)，即即d|b，矛盾。矛盾。Note:本定理可以作为同余式无解的判定定理本定理可以作为同余式无解的判定定理.定理定理5.3.3若若(a,m)=d 1，且且d|b，则同余式则同余式ax b(modm)(1)有有d个解，分别为个解，分别为,+m/d,+2m/d,+(d-1)m/d(2)其中其中 是同余式是同余式(a/d)x b/d(modm/d)(3)的解。的解。定理定理5.3.3证明：首先证明证明：首先证明(1)和和(3)的解相同。的解相同。若若x是是(1)的解，即，的解，即，ax b(modm)，由由(a,m)=d，知，知d|a,d|m,再由再由d|b及及性质性质9知知,(a/d)x b/d(modm/d),即即x是是(3)的解，的解，若若x是是(3)的解，即，的解，即，(ax-b)/d=qm/d，所以所以(ax-b)=qm，即即ax b(modm)，因此因此x是是(1)的解。的解。定理定理5.3.3证明：其次根据证明：其次根据(3)的解探讨的解探讨(1)的解的形式的解的形式.因为因为(a,m)=d，所以所以(a/d,m/d)=1。由由定理定理5.3.1知，知，(3)在模在模m/d下有唯一解，设下有唯一解，设为为，不妨设不妨设0 m/d。因为因为+km/d恰是恰是 所在的模所在的模m/d剩余类的剩余类的全部元素，全部元素，k=0,1,2,，故故(3)的解作为的解作为数都可以表示成数都可以表示成+km/d的形式。于是的形式。于是(1)的解都是的解都是+km/d形式的数，形式的数，k=0,1,2,。定理定理5.3.3证明：最后证明证明：最后证明(2)式是式是(1)的的d个不同解，个不同解，而且而且(1)式只有式只有(2)式这式这d个个不同不同的解的解。往证往证(2)式是式是(1)的的d个个不同不同解，因为解，因为0 m/d，故故0(2)中每一个式子中每一个式子 m，且互不相同，所以它们之间关于模且互不相同，所以它们之间关于模m互互不同余不同余，即，即(2)为为(1)的的d个个不同不同解。解。定理定理5.3.3再考虑再考虑(1)只有只有(2)这这d个不同解。即若数个不同解。即若数+km/d是是(1)的解，往证关于模的解，往证关于模m，+km/d必同余必同余(2)中中d个数之一。个数之一。因为因为0，1，d-1为关于模为关于模d的的完全剩完全剩余系余系，故存在，故存在i，0 i d-1，使得使得k i(modd)。由由m/d 0，两边和模同乘，两边和模同乘m/d得，得，(k/d)m(i/d)m(modm)，故故+km/d +im/d(modm)。证毕。证毕。例例.解合同式解合同式6x 15(mod33)。解：解：（6，33）=33|15先求先求2x 5(mod11)的解。的解。2x 16(mod11)x 8(mod11)原合同式有原合同式有3个解：个解：8，8+11，8+22即即x 8(mod33)，x 19(mod33)，x 30(mod33)总结总结一次同余式一次同余式axb(modm)：(a,m)=1,b任意任意;有一个解有一个解d1d|b;有有d个解个解d|b;无解无解作业：习题作业：习题5.32,3此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！