5-3合同--一次同余式.ppt

5.3合同一次同余式合同一次同余式5.3.1 合同及其性质合同及其性质 设设m是任意非是任意非0整数。整数。a被被m整除时，我们就整除时，我们就说说a 合同于合同于0模模m，记为：记为：a 0(mod m)一般来说，若一般来说，若a-b被被m整除，则我们说整除，则我们说a合同合同于于b 模模m：a b(mod m)一个数为一个数为m整除，当且仅当此数为整除，当且仅当此数为-m整除。整除。所以，若未指定所以，若未指定m而一般地讨论模而一般地讨论模m合同时，合同时，我们总假定我们总假定m是正整数。是正整数。5.3.1 合同及其性质合同及其性质 设设a=q1m+r1，0r1m；b=q2m+r2，0r2m。于是于是a-b=(q1-q2)m+(r1-r2)由此式，由此式，m|(a-b)必要而且只要必要而且只要m|(r1-r2)，但但|r1-r2|m，故故m|(r1-r2)必要而且只要必要而且只要r1-r2=0。因之，因之，ab(mod m)必要而且只要以必要而且只要以m除除a和和b所得的余数相同。所得的余数相同。合同的基本性质合同的基本性质 性质性质1 aa。性质性质2 若若ab,则则ba。性质性质3 若若ab，bc，则则ac。这就是说，合同是一种等价关系。每一个这就是说，合同是一种等价关系。每一个等价类称为模等价类称为模m的一个的一个剩余类剩余类。合同的基本性质合同的基本性质 性质性质4 若若ab(mod m)，cd(mod m)，则则a cb d(mod m)，acbd(mod m)证明：证明：由题设有由题设有r，s使使a-b=rm，c-d=sm。故故(a c)-(b d)=(r s)m,因而因而a c b d(mod m)。其次，其次，ac=(b+rm)(d+sm)=bd+rdm+bsm+rsm2 bd+0+0+0(mod m)=bd(mod m)，故故ac bd(mod m)。合同的基本性质合同的基本性质 性质性质5 若若a b(mod m)，则则a k b k(mod m)。其中其中k为整数。为整数。性质性质6 若若a+b c(mod m)，则则a c-b(mod m)性质性质7 若若a b(mod m)，则则ac bc(mod m)。性质性质8 若若a b(mod m)，则则an bn(mod m)，n 0。合同的基本性质合同的基本性质 性质性质9 若若c 0而而ac bc(mod mc)，则则a b(mod m)。证明：由题设有证明：由题设有q使使ac-bc=qmc，于是于是a-b=qm，因而因而a b(mod m)。性质性质10 若若c和和m互质，则由互质，则由ac bc(mod m)可以推出可以推出a b(mod m)。证明：证明：ac=bc(mod m)表示表示m|(a-b)c，但但c和和m互质，所以有互质，所以有m|(a-b)，于是于是a b(mod m)。合同的基本性质合同的基本性质 性质性质11 若若ac bc(mod m)，且（且（c,m）=d，则则a b(mod m/d)证明：由证明：由ac bc(mod m)知，知，m|(a-b)c，而而(c,m)=d，故故 m/d|(a-b)c/d。注意注意到（到（m/d,c/d）=1，从而得从而得 m/d|(a-b)，即即 a b(mod m/d)。对于质数模对于质数模p，则有和相等完全类似的消去则有和相等完全类似的消去律。律。合同的基本性质合同的基本性质 性质性质12 若若p为质数，为质数，c 0(mod p)，而而ac bc(mod p)，则则a b(mod p)。证明：因为证明：因为p是质数，是质数，c 0(mod p)就表示就表示c和和p互质，互质，(c,p)=1，因而性质因而性质12不不过是性质过是性质10的推论。的推论。合同的基本性质合同的基本性质 性质性质13 设设p(x)是整系数多项式，是整系数多项式，x和和y是整是整数变量，则由数变量，则由x y(mod m)可得可得 p(x)p(y)(mod m)。运用性质运用性质13，我们再看能被，我们再看能被9整除数的数码整除数的数码特征。设特征。设N=an10n+an-110n-1+a110+a0为一为一整数，因为整数，因为10 1(mod 9)，由性质由性质13得得N an1n+an-11n-1+a1+a0(mod 9)即即 。于是于是 9|N当且仅当当且仅当9|5.3.2 剩余类剩余类 一次同余式一次同余式 模模m合同既然是一种等价关系，就可以把合同既然是一种等价关系，就可以把所有整数按照模所有整数按照模 m合同的关系分为等价类，合同的关系分为等价类，每一个等价类称为模每一个等价类称为模m的一个剩余类。的一个剩余类。同一个剩余类中的数互相合同，不同的剩同一个剩余类中的数互相合同，不同的剩余类中的数不互相合同。余类中的数不互相合同。因为以因为以m去除任意整数，可能得到的余数去除任意整数，可能得到的余数恰有恰有0，1，m-1，这这m个数，所以模个数，所以模m共有共有m个剩余类，个剩余类，5.3.2 剩余类剩余类 一次同余式一次同余式 从每个剩余类中取出一个数作为代表，这从每个剩余类中取出一个数作为代表，这样便可得到样便可得到m个数，比方个数，比方r1,r2,rm说是作说是作成一个完全剩余系，任意整数模成一个完全剩余系，任意整数模m恰好合恰好合同于此完全剩余系中的一个数。例如，同于此完全剩余系中的一个数。例如，0，1，m-1便是这样一个完全剩余系。又便是这样一个完全剩余系。又如，模如，模3，三个数，三个数0，1，2作成一个完全剩作成一个完全剩余系，余系，-1，0，1也作成一个完全剩余系。也作成一个完全剩余系。模模2，两个数，两个数0，1作成一个完全剩余系，作成一个完全剩余系，0代表所有偶数，代表所有偶数，1代表所有奇数。代表所有奇数。同余式同余式 含有整数变量的合同式，称为合同方程或含有整数变量的合同式，称为合同方程或同余式同余式。ax b(mod m)这种形式的合同式称为一这种形式的合同式称为一次同余式；类似地，次同余式；类似地，a2x2+a1x b(mod m)称称为二次同余式。为二次同余式。同余式同余式求解一次同余式实际上是解求解一次同余式实际上是解 ax-b=my这样这样的不定方程。我们这里讨论一次同余式在的不定方程。我们这里讨论一次同余式在什么条件下有解？什么条件下无解？什么什么条件下有解？什么条件下无解？什么时候有唯一解（一个剩余类）？什么时候时候有唯一解（一个剩余类）什么时候有多解（多个剩余类）？有多解（多个剩余类）？定理定理5.3.1 若若a和和m互质，互质，b任意，则模任意，则模m恰有一个数恰有一个数x使使ax b(mod m)。证明：证明：存在性存在性。因为。因为a和和m互质，故有互质，故有s，t使使as+mt=1，于是于是asb+mtb=b，若取模若取模m，则有则有asb b(mod m)。取取x=sb，则则sb所在的剩余类中所在的剩余类中的数皆是解。的数皆是解。唯一性唯一性。所谓模。所谓模m只有一个这样的只有一个这样的x，意思是说意思是说在模在模m合同的意义下，解是唯一的。即若合同的意义下，解是唯一的。即若ax b(mod m)，ay b(mod m)，则则x y(mod m)。因因为，由为，由ax b(mod m)，ay b(mod m)得得ax ay(mod m)，消去和消去和m互质的互质的a乃得乃得x y(mod m)。定理定理5.3.1推论推论 设设P为质数。若为质数。若a 0(mod p)，b任意，任意，则模则模p恰有一个数恰有一个数x使使ax b(mod p)。定理定理5.3.2若若(a,m)=d 1，且且d|b，则同余式则同余式ax b(mod m)无解。无解。证明：证明：反证法。若上式可解，则存在反证法。若上式可解，则存在，使使得得a b(mod m)。从而存在从而存在q，使得使得b=a-mq。因为因为(a,m)=d 1，故故d|(a-mq)，从而从而d|b，矛盾。矛盾。定理定理5.3.3若若(a,m)=d 1，且且d|b，则同余式则同余式ax b(mod m)(1)有有d个解，分别为个解，分别为 ,+m/d,+2m/d,+(d-1)m/d(2)其中其中 是同余式是同余式(a/d)x b/d(mod m/d)(3)的解。的解。定理定理5.3.3证明：证明：由由性质性质11和和性质性质9知知,(1)的解是的解是(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个不同解。因为个不同解。因为0 m/d，故故0 (2)中每一个式子中每一个式子 m，且互不相同，且互不相同，所以它们之间关于模所以它们之间关于模m互不同余，即互不同余，即(2)为为(1)的的d个不同解。个不同解。再考虑再考虑(1)只有只有(2)这这d个不同解。即若数个不同解。即若数+lm/d是是(1)的解，则关于模的解，则关于模m，+lm/d必同余必同余(2)中中d个数之一。个数之一。因为因为 0，1，d-1为关于模为关于模d的完全剩余系，的完全剩余系，故存在故存在i，0 i d-1，使得使得 l i(mod d)。由由m/d 0和性质和性质9，两边和模同乘，两边和模同乘m/d 得，得，(l/d)m (i/d)m(mod m)，故故+lm/d +im/d(mod m)。证毕。证毕。求解一次合同方程的方法求解一次合同方程的方法 我们以我们以解合同式解合同式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+211+（-1-1）484103103。由此知，由此知，S=S=（-1-1）484，所以所以x=sb=8457=4788=2123-6523-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+15+1由合同的性质由合同的性质7有有4255x 4297 21119+6519+65 65(mod211)。由合同的性质由合同的性质5知，知，211x-4255x 0-65(mod211)。即即x-65(mod211)。对对于于一一些些例例子子，使使用用这这种种方方法法是是比比较较快快的的。比比如如，解解合合同式同式4x 1(mod15)。因为因为 1 16(mod15)，所以所以4x 1 16 444(mod15)，因因为为4与与15互互质质，由由合合同同的的性性质质10知知，合合同同式式两两边边可可以以消去消去4，得到，得到 x 4(mod 15)。求解一次合同方程的方法求解一次合同方程的方法方法三方法三:利用利用Fermat-Euler定理（教材中定理定理（教材中定理5.4.7），见下例。），见下例。例例5.2.18解合同式解合同式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=5=727575（-1）7575 5(mod10)，所以所给合同式的解为所以所给合同式的解为x 5(mod10)。