合同一次同余式实用教案

1、5.3.1 合同合同(h tong)及其性质及其性质 设m是任意非0整数。a被m整除时，我们就说a 合同于0模m，记为：a0(mod m)一般来说，若a-b被m整除，则我们说a合同于b 模m：ab(mod m)一个(y )数为m整除，当且仅当此数为- m整除。所以，若未指定m而一般地讨论模m合同时，我们总假定m是正整数。 第1页/共27页第一页，共28页。5.3.1 合同合同(h tong)及其性质及其性质 设a=q1m+r1，0r1m；b=q2m+r2，0r2m。于是a-b=(q1-q2)m+(r1-r2)由此式，m|(a-b)必要而且(r qi)只要m|(r1-r2)，但|r1-r2|m，

2、故m|(r1-r2)必要而且(r qi)只要r1-r2=0。因之，ab(mod m)必要而且(r qi)只要以m除a和b所得的余数相同。 第2页/共27页第二页，共28页。合同合同(h tong)的基本性质的基本性质 第3页/共27页第三页，共28页。合同的基本合同的基本(jbn)性质性质 acbd(mod m)。第4页/共27页第四页，共28页。合同合同(h tong)的基本性质的基本性质 第5页/共27页第五页，共28页。合同合同(h tong)的基本性质的基本性质 第6页/共27页第六页，共28页。合同的基本合同的基本(jbn)性质性质 第7页/共27页第七页，共28页。合同的基本合同的

3、基本(jbn)性质性质 第8页/共27页第八页，共28页。合同的基本合同的基本(jbn)性质性质 第9页/共27页第九页，共28页。)9(modN0niianiia0第10页/共27页第十页，共28页。5.3.2 剩余剩余(shngy)类类 一次同余式一次同余式 共有m个剩余类，第11页/共27页第十一页，共28页。5.3.2 剩余剩余(shngy)类类 一次同余式一次同余式 01第12页/共27页第十二页，共28页。同余式同余式 含有整数变量(binling)的合同式，称为合同方程或同余式 。axb(mod m)这种形式的合同式称为一次同余式；类似地，a2x2+a1xb(mod m)称为二次

4、同余式。 第13页/共27页第十三页，共28页。同余式同余式求解一次同余式实际上是解 ax-b=my这样的不定方程。我们这里讨论一次同余式在什么条件下有解？什么条件下无解？什么时候有唯一(wi y)解（一个剩余类）？什么时候有多解（多个剩余类）？ 第14页/共27页第十四页，共28页。定理定理(dngl)5.3.1 (dngl)5.3.1 若a和m互质，b任意，则模m恰有一个数x使axb(mod m) 。证明： 存在性。因为a和m互质，故有s，t使as+mt=1，于是asb+mtb=b，若取模m，则有asbb(mod m)。取x=sb，则sb所在的剩余类中的数皆是解。唯一性。所谓(suwi)模

5、m只有一个这样的x，意思是说在模m合同的意义下，解是唯一的。即若axb (mod m)，ayb(mod m)，则xy(mod m)。因为，由axb(mod m)，ayb(mod m)得axay(mod m)，消去和m互质的a乃得xy (mod m)。 第15页/共27页第十五页，共28页。定理定理(dngl)5.3.1(dngl)5.3.1推论 设P为质数。若a 0 (mod p)，b任意，则模p恰有一个数x使ax b(mod p)。 第16页/共27页第十六页，共28页。定理(dngl)5.3.2若(a, m)=d 1，且d|b，则同余式ax b (mod m)无解。证明：反证法。若上式可解

6、，则存在 ，使得a b(mod m)。从而存在q，使得b=a -mq。因为(a, m)=d 1 ，故d|(a -mq)，从而d|b，矛盾。 第17页/共27页第十七页，共28页。定理(dngl)5.3.3若(a, m)=d1 ，且d|b，则同余式axb(mod m) (1)有d个解，分别(fnbi)为 , +m/d, +2m/d, , +(d-1)m/d (2)其中是同余式(a/d)xb/d (mod m/d) (3)的解。 第18页/共27页第十八页，共28页。定理(dngl)5.3.3证明：由性质11和性质9知, (1)的解是(3)的解， (3)的解也是(1)的解。因为(a, m)=d，所

7、以(a/d, m/d)=1。由定理5.3.1知， (3)在模m/d下有唯一解，设为 ，不妨设0 m/d。因为+km/d恰是所在的模m/d剩余类的全部元素，k=0, 1, 2, ，故(3)的解作为数都可以表示(biosh)成+km/d的形式。于是(1)的解都是+km/d形式的数，k=0, 1, 2, 。 第19页/共27页第十九页，共28页。定理(dngl)5.3.3下面证明(2)式是(1)的d个不同解。因为0 m/d，故0 (2)中每一个(y )式子 m，且互不相同，所以它们之间关于模m互不同余，即(2)为(1)的d个不同解。再考虑(1)只有(2)这d个不同解。即若数+lm/d是(1)的解，则

8、关于模m， +lm/d必同余(2)中d个数之一。因为 0，1，d-1为关于模d的完全剩余系，故存在i，0id-1，使得 li (mod d)。由m/d0和性质9，两边和模同乘m/d 得，(l/d)m (i/d)m (mod m)，故+lm/d +im/d(mod m)。证毕。 第20页/共27页第二十页，共28页。求解一次合同方程求解一次合同方程(fngchng)(fngchng)的方法的方法 我们以解合同式103x57(mod 211)为例. 方法一:定理5.3.1告诉我们若a和m互质，b任意，则模m恰有一个数x使axb(mod m)。该定理证明存在性的过程即告诉了我们一种求解方法：因为a和

9、m互质，故有s，t使as+mt=1，于是asb+mtb=b，若取模m，则有asbb(mod m)。取x=sb，则sb所在的剩余类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的a与m的最大公因数1表示为a和m的倍数和的形式(xngsh)：1=as+mt，然后取x=sb，即可。 第21页/共27页第二十一页，共28页。求解求解(qi ji)(qi ji)一次合同方程的方法一次合同方程的方法 解：由于103与211互质，我们先将103与211的最大公因数1表示为它们(t men)的倍数和的形式。使用辗转相除方法逐次得商及余数并计算Sk，Tk如下表所示： k012345rk53210qk22

10、0113Sk01202141Tk12414384第22页/共27页第二十二页，共28页。求解一次合同方程求解一次合同方程(fngchng)(fngchng)的方法的方法 因此(ync)， 1=（-1）341211+（-1）484103。 由此知，S=（-1）484，所以 x=sb=8457=4788=2123-65-65(mod 211)。第23页/共27页第二十三页，共28页。求解一次合同求解一次合同(h tong)(h tong)方程的方法方程的方法 方法二:就是利用合同的性质，使x的系数变成1，即得到解。 对于上例解合同式103x57(mod 211)。由于 211=1032+5， 由合

11、同的性质7有 2103x257(mod 211)。 因为(yn wi) 211x0(mod 211)， 所以由合同的性质5知， 211x-2103x0-257(mod 211)。 即5x-114(mod 211) 97(mod 211)。第24页/共27页第二十四页，共28页。求解一次合同方程求解一次合同方程(fngchng)(fngchng)的方法的方法 由于 211=425+1 由合同的性质(xngzh)7有 425 x4297 21119+65 65(mod 211)。 由合同的性质(xngzh)5知， 211x-425 x0-65(mod 211)。 即x-65(mod 211)。 对

12、于一些例子，使用这种方法是比较快的。比如，解合同式4x1(mod 15)。因为 116(mod 15)， 所以4x1 16 44(mod 15)， 因为4与15互质，由合同的性质(xngzh)10知，合同式两边可以消去4，得到 x4(mod 15)。 第25页/共27页第二十五页，共28页。求解一次合同方程求解一次合同方程(fngchng)(fngchng)的方法的方法 方法三:利用Fermat-Euler定理（教材中定理5.4.7），见下例。 例5.2.18 解合同式7x5(mod 10)。 解：因为(yn wi)7和10互质，由Fermat-Euler定理有 7(10)1(mod 10)， 因(10)=4，所以741(mod 10)。由合同的性质7，在7x5(mod 10)两边乘以73，有 737x735(mod 10)， 而737x=74 x x(mod 10)， 735=7275（-1）75 5(mod 10)， 所以所给合同式的解为x 5(mod 10)。第26页/共27页第二十六页，共28页。谢谢您的观看(gunkn)！第27页/共27页第二十七页，共28页。NoImage内容(nirng)总结5.3