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

5.3合同一次同余式,5.3.1合同及其性质,设m是任意非0整数。a被m整除时，我们就说a合同于0模m，记为：a0(modm)一般来说，若a-b被m整除，则我们说a合同于b模m：ab(modm)一个数为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(modm)必要而且只要以m除a和b所得的余数相同。,合同的基本性质,性质1aa。性质2若ab,则ba。性质3若ab，bc，则ac。这就是说，合同是一种等价关系。每一个等价类称为模m的一个剩余类。,合同的基本性质,性质4若ab(modm)，cd(modm)，则acbd(modm)，acbd(modm)证明：由题设有r，s使a-b=rm，c-d=sm。故(ac)-(bd)=(rs)m,因而acbd(modm)。其次，ac=(b+rm)(d+sm)=bd+rdm+bsm+rsm2bd+0+0+0(modm)=bd(modm)，故acbd(modm)。,合同的基本性质,性质5若ab(modm)，则akbk(modm)。其中k为整数。性质6若a+bc(modm)，则ac-b(modm)。性质7若ab(modm)，则acbc(modm)。性质8若ab(modm)，则anbn(modm)，n0。,合同的基本性质,性质9若c0而acbc(modmc)，则ab(modm)。证明：由题设有q使ac-bc=qmc，于是a-b=qm，因而ab(modm)。性质10若c和m互质，则由acbc(modm)可以推出ab(modm)。证明：ac=bc(modm)表示m|(a-b)c，但c和m互质，所以有m|(a-b)，于是ab(modm)。,合同的基本性质,性质11若acbc(modm)，且（c,m）=d，则ab(modm/d)证明：由acbc(modm)知，m|(a-b)c，而(c,m)=d，故m/d|(a-b)c/d。注意到（m/d,c/d）=1，从而得m/d|(a-b)，即ab(modm/d)。对于质数模p，则有和相等完全类似的消去律。,合同的基本性质,合同的基本性质,性质13设p(x)是整系数多项式，x和y是整数变量，则由xy(modm)可得p(x)p(y)(modm)。,运用性质13，我们再看能被9整除数的数码特征。设N=an10n+an-110n-1+a110+a0为一整数，因为101(mod9)，由性质13得Nan1n+an-11n-1+a1+a0(mod9)即。于是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代表所有奇数。,同余式,含有整数变量的合同式，称为合同方程或同余式。axb(modm)这种形式的合同式称为一次同余式；类似地，a2x2+a1xb(modm)称为二次同余式。,同余式,求解一次同余式实际上是解ax-b=my这样的不定方程。我们这里讨论一次同余式在什么条件下有解？什么条件下无解？什么时候有唯一解（一个剩余类）？什么时候有多解（多个剩余类）？,定理5.3.1,若a和m互质，b任意，则模m恰有一个数x使axb(modm)。证明：存在性。因为a和m互质，故有s，t使as+mt=1，于是asb+mtb=b，若取模m，则有asbb(modm)。取x=sb，则sb所在的剩余类中的数皆是解。唯一性。所谓模m只有一个这样的x，意思是说在模m合同的意义下，解是唯一的。即若axb(modm)，ayb(modm)，则xy(modm)。因为，由axb(modm)，ayb(modm)得axay(modm)，消去和m互质的a乃得xy(modm)。,定理5.3.1,定理5.3.2,定理5.3.3,若(a,m)=d1，且d|b，则同余式axb(modm)(1)有d个解，分别为,+m/d,+2m/d,+(d-1)m/d(2)其中是同余式(a/d)xb/d(modm/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下有唯一解，设为，不妨设0m/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个不同解。因为0m/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，0id-1，使得li(modd)。由m/d0和性质9，两边和模同乘m/d得，(l/d)m(i/d)m(modm)，故+lm/d+im/d(modm)。证毕。,求解一次合同方程的方法,我们以解合同式103x57(mod211)为例.方法一:定理5.3.1告诉我们若a和m互质，b任意，则模m恰有一个数x使axb(modm)。该定理证明存在性的过程即告诉了我们一种求解方法：因为a和m互质，故有s，t使as+mt=1，于是asb+mtb=b，若取模m，则有asbb(modm)。取x=sb，则sb所在的剩余类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的a与m的最大公因数1表示为a和m的倍数和的形式：1=as+mt，然后取x=sb，即可。,求解一次合同方程的方法,解：由于103与211互质，我们先将103与211的最大公因数1表示为它们的倍数和的形式。使用辗转相除方法逐次得商及余数并计算Sk，Tk如下表所示：,求解一次合同方程的方法,因此，1=（-1）341211+（-1）484103。由此知，S=（-1）484，所以x=sb=8457=4788=2123-65-65(mod211)。,求解一次合同方程的方法,方法二:就是利用合同的性质，使x的系数变成1，即得到解。对于上例解合同式103x57(mod211)。由于211=1032+5，由合同的性质7有2103x257(mod211)。因为211x0(mod211)，所以由合同的性质5知，211x-2103x0-257(mod211)。即5x-114(mod211)97(mod211)。,求解一次合同方程的方法,由于211=425+1由合同的性质7有425x429721119+6565(mod211)。由合同的性质5知，211x-425x0-65(mod211)。即x-65(mod211)。对于一些例子，使用这种方法是比较快的。比如，解合同式4x1(mod15)。因为116(mod15)，所以4x11644(mod15)，因为4与15互质，由合同的性质10知，合同式两边可以消去4，得到x4(mod15)。,求解一次合同方程的方法,方法三:利用Fermat-Euler定理（教材中定理5.4.7），见下例。例5.2.18解合同式7