5_3合同_次同余式（PPT63页)

1、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)表示的

2、就是表示的就是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,则则d|c/d，dd|c,并且并且d|m/d，dd|m，得到，得到 dd为为c,m的公因数，则的公因数，则dd|d，即，即d|1，矛盾。，矛盾。合同的基本性质合同的基本性质性质性质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是整数

3、变量，是整数变量，则由则由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|5.3.2剩余类剩余类一次同余式一次同余式模模m合同既然是一种等价关系，就可以把所有合同既然是一种等价关系，就可以把所有整数按照模整数按照模m合同的关系分为等价类，每一个等合同的关系分为等价类，每一个等价类称为模价类称为模m的一个的一个剩余类

4、剩余类。例如，整数集合例如，整数集合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作成一个完全剩余系

5、，作成一个完全剩余系，-1，0，1也作成一个完全剩余系。也作成一个完全剩余系。例例模模2，两个数，两个数0，1作成一个完全剩余系，作成一个完全剩余系，0代表所代表所有偶数，有偶数，1代表所有奇数代表所有奇数.同余式同余式有棋子若干枚，三个三个的数剩两个，问至有棋子若干枚，三个三个的数剩两个，问至少有多少个棋子？少有多少个棋子？答：由题意，棋子的个数减答：由题意，棋子的个数减2是是3的倍数，从而的倍数，从而有，有，(x-2)=3y,x0，用合同式表示为：，用合同式表示为：x2(mod3)，从而棋子的个数可能是：，从而棋子的个数可能是：2,5,8,，都，都是是mod3合同合同2。同余式同余式含有整数变量的合同式，称为合同方程或同余含有整数变量的合同式，称为合同方程或同余式式。ax b(modm)这种形式的合同式称为一次同余这种形式的合同式称为一次同余式；类似地，式；类似地，a2x2+a1x b(modm)称为二次同余称为二次同余式。式。同余式同余式求解一次同余式求解一次同余式ax b(modm)实际上是解实际上是解ax-b=my这样的不定方程。这里讨论一次同余这样的不定方程。这里讨论一次同

6、余式在什么条件下式在什么条件下有解有解？什么条件下？什么条件下无解无解？什么？什么时候有时候有唯一解唯一解（一个剩余类一个剩余类）？什么时候有）？什么时候有多多解解（多个剩余类）？（多个剩余类）？定理定理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)。因为，由因为，由

7、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)。求解一次合同方程的方法求解一次合同方程的方法 以解合同式以解合同式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所在的剩余所在的剩余类中的数皆是解。因此，方法

8、一就是先使用辗转相类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的除方法将互质的a与与m的最大公因数的最大公因数1表示为表示为a和和m的的倍数和的形式：倍数和的形式：1=as+mt，然后取然后取x=sb，即可。即可。求解一次合同方程的方法求解一次合同方程的方法解合同式解合同式103x 57(mod211)解解：a=103与与m=211互互质质，先先将将103与与211的的最最大大公公因因数数1表表示示为为它它们们的的倍倍数数和和的的形形式式。使使用用辗辗转转相相除除方方法法逐逐次次得得商及余数并计算商及余数并计算Sk，Tk如下所示如下所示：k012345rk53210qk220112Sk01202141Tk12414384求解一次合同方程的方法求解一次合同方程的方法解合同式解合同式103x 57(mod211)因此，因此，1=（-1）341211+（-1）484103。由此知，由此知，S=（-1）484，所以所以x=sb=8457=4788=21123-65-65(mod211)。求解一次合同方程的方法求解一次合同方程的方法方法二方法二:就是利用合同的性质，使就是利用合同的性

9、质，使x的系数变成的系数变成1，即，即得到解。得到解。对于上例解合同式对于上例解合同式103x 57(mod211)。由于由于211=1032+5，由合同的性质由合同的性质7有有2103x 257(mod211)。因为因为211x 0(mod211)，所以由合同的性质所以由合同的性质4知，知，211x-2103x 0-257(mod211)。即即5x-114(mod211)97(mod211)。求解一次合同方程的方法求解一次合同方程的方法5x-114(mod211)97(mod211)。而而211x 0(mod211),由合同的性质由合同的性质7有有425x 4297 21119+65 65(mod211)。由合同的性质由合同的性质5知，知，211x-425x 0-65(mod211)。即即x-65(mod211)。对对于于一一些些例例子子，使使用用这这种种方方法法是是比比较较快快的的。比比如如，解合同解合同式式4x 1(mod15)。因为因为1 16(mod15)，所以所以4x 44(mod15)，因因为为4与与15互互质质，由由合合同同的的性性质质10知知，合合同同式式两两边可以消

10、边可以消去去4，得到，得到x 4(mod15)。例例.解合同式解合同式14x 27(mod31)。解：解：28x 54(mod31)31x 0(mod31)故故3x-54(mod31)x-18(mod31)13(mod31)还可以：还可以：14x 58(mod31)7x 29(mod31)7x 91(mod31)x 13(mod31)定理定理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|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/

《5_3合同_次同余式（PPT63页)》由会员小****分享，可在线阅读，更多相关《5_3合同_次同余式（PPT63页)》请在金锄头文库上搜索。