最新5-3合同 一次同余式

5-3合同 一次同余式5-3合同 一次同余式设设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合同 一次同余式设设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所得的余数相同。所得的余数相同。5-3合同 一次同余式5-3合同 一次同余式5-3合同 一次同余式5-3合同 一次同余式5-3合同 一次同余式5-3合同 一次同余式5-3合同 一次同余式5-3合同 一次同余式)9(modN0niianiia05-3合同 一次同余式5-3合同 一次同余式5-3合同 一次同余式含有整数变量的合同式，称为合同方程含有整数变量的合同式，称为合同方程或同余式或同余式。ax b(mod m)这种形式的合同式称为一次这种形式的合同式称为一次同余式；类似地，同余式；类似地，a2x2+a1x b(mod m)称为称为二次同余式。二次同余式。5-3合同 一次同余式求解一次同余式实际上是解求解一次同余式实际上是解 ax-b=my这样这样的不定方程。我们这里讨论一次同余式在的不定方程。我们这里讨论一次同余式在什么条件下有解？什么条件下无解？什么什么条件下有解？什么条件下无解？什么时候有唯一解（一个剩余类）？什么时候时候有唯一解（一个剩余类）？什么时候有多解（多个剩余类）？有多解（多个剩余类）？5-3合同 一次同余式若若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合同 一次同余式推论推论 设设P为质数。若为质数。若a 0(mod p)，b任意，任意，则模则模p恰有一个数恰有一个数x使使ax b(mod p)。5-3合同 一次同余式若若(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合同 一次同余式若若(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合同 一次同余式证明：证明：由由性质性质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合同 一次同余式下面证明下面证明(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)。证毕。证毕。5-3合同 一次同余式 我们以我们以解合同式解合同式103x 57(mod 211)为例为例.方法一方法一:定理定理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所在的剩余类中的数皆是解。因所在的剩余类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的此，方法一就是先使用辗转相除方法将互质的a与与m的最大公因数的最大公因数1表示为表示为a和和m的倍数和的形式：的倍数和的形式：1=as+mt，然后取然后取x=sb，即可。即可。5-3合同 一次同余式解：由于解：由于103与与211互质，我们先将互质，我们先将103与与211的的最大公因数最大公因数1表示为它们的倍数和的形式。使用表示为它们的倍数和的形式。使用辗转相除方法逐次得商及余数并计算辗转相除方法逐次得商及余数并计算Sk，Tk如下如下表所示：表所示：k012345rk53210qk220113Sk01202141Tk124143845-3合同 一次同余式因此，因此，1=（-1）341211+211+（-1-1）484103103。由此知，由此知，S=S=（-1-1）484，所以所以x=sb=8457=4788=2123-6523-65-65(mod 211)。5-3合同 一次同余式方法二方法二:就是利用合同的性质，使就是利用合同的性质，使x的系数变成的系数变成1，即得到解。即得到解。对于上例解合同式对于上例解合同式103x 57(mod 211)。由于由于211=1032+5，由合同的性质由合同的性质7有有2103x 257(mod 211)。因为因为211x 0(mod 211)，所以由合同的性质所以由合同的性质5知，知，211x-2103x 0-257(mod 211)。即即5x-114(mod 211)97(mod 211)。5-3合同 一次同余式由于由于 211=425+15+1由合同的性质由合同的性质7有有425 5 x 4297 21119+6519+65 65(mod 211)。由合同的性质由合同的性质5知，知，211x-425 5 x 0-65(mod 211)。即即x-65(mod 211)。对于一些例子，使用这种方法是比较快的。比如，解合对于一些例子，使用这种方法是比较快的。比如，解合同式同式4x 1(mod 15)。因为因为 1 16(mod 15)，所以所以4x 1 16 44 4(mod 15)，因为因为4与与15互质，由合同的性质互质，由合同的性质10知，合同式两边可以知，合同式两边可以消去消去4，得到，得到 x 4(mod 15)。5-3合同 一次同余式方法三方法三:利用利用Fermat-Euler定理（教材中定理定理（教材中定理5.4.7），见下例。），见下例。例例5.2.18 解合同式解合同式7x 5(mod 10)。解：因为解：因为7和和10互质，由互质，由Fermat-Euler定理有定理有7(10)1(mod 10)，因因(10)=4，所以，所以74 1(mod 10)。由合同的性质由合同的性质7，在，在7x 5(mod 10)两边乘以两边乘以73，有，有737x 735(mod 10)，而而737x=74 x x(mod 10)，735=5=727 75 5（-1）7 75 5 5(mod 10)，所以所给合同式的解为所以所给合同式的解为x 5(mod 10)。