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

§5.3合同一次同余式引入看任意整数a除以3所得的余数：0＝0×3+0;1＝0×3+1;-1＝(-1)×3+2;2＝0×3+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)表示的就是m|a。(2)若m|a，则-m|a。所以，若未指定m而一般地讨论模m合同时，总假定m是正整数。§5.3.1合同及其性质(3)设a=q1m+r1，0≤r1m；b=q2m+r2，0≤r2m。于是a-b=(q1-q2)m+(r1-r2)则m|(a-b)iffm|(r1-r2)，但|r1-r2|m，故m|(r1-r2)iffr1-r2=0。故a≡b(modm)iff以m除a和b所得的余数相同。有些书中将合同又叫做同余。合同的基本性质合同是整除的又一表达方式，但这种表达有许多好处：（1）直观；（2）合同的很多性质与相等类似。性质1a≡a。性质2若a≡b,则b≡a。性质3若a≡b，b≡c，则a≡c。故合同是一种等价关系。每一个等价类称为模m的一个剩余类。合同的基本性质性质4若a≡b(modm),c≡d(modm)，则ac≡bd(modm)，ac≡bd(modm)证明：由题设有r，s使a-b=rm，c-d=sm。故(ac)-(bd)=(rs)m,因而acbd(modm)。ac=(b+rm)(d+sm)=bd+rdm+bsm+rsm2bd+0+0+0(modm)=bd(modm)，故acbd(modm)合同的基本性质性质5若ab(modm)，则akbk(modm)。其中k为整数。证明：由ab(modm)，kk(modm)和性质4有，a+kb+k(modm)。同理得a-kb-k(modm)。性质6若a+bc(modm)，则ac-b(modm)。证明：由a+bc(modm)和-b-b(modm)得a+b-bc-b(modm)，即ac-b(modm)。合同的基本性质性质7若ab(modm)，则acbc(modm)。证明：由ab(modm)，cc(modm)和性质4有，acbc(modm)。性质8若ab(modm)，则anbn(modm)，n0。证明：若n=0,有a0b0(modm);一般情况下，有n个式子ab(modm)成立，根据性质4，有：anbn(modm)。例.证明：正整数n是3的倍数iffn的各个数字之和是3的倍数。证明：设n=ak10k+ak-110k-1+…+a110+a0因为101(mod3)，由性质8得10i1(mod3)，由性质7得ai10iai(mod3)故由性质4得n=ak10k+ak-110k-1+…+a110+a0ak+ak-1+…+a1+a0(mod3)因此，3|niffn0(mod3)iffak+ak-1+…+a1+a00(mod3)合同的基本性质这8条性质都和相等的性质相同，但对于数的相等，我们还有消去律：若c0而ac=bc则a=b。这对合同并不普遍成立，例如，虽然20(mod6)，却不能从合同式814（mod6）的两边消去2得出47(mod6)。但是，下列两个事实成立：合同的基本性质性质9若c0而acbc(modmc)，则ab(modm)。证明：由题设有q使ac-bc=qmc，c0，于是a-b=qm，因而ab(modm)。性质10若c和m互质，则由acbc(modm)可以推出ab(modm)。证明：acbc(modm)表示m|(a-b)c，但c和m互质，所以由定理5.2.2，有m|(a-b)，故ab(modm)。例.822(mod7)，（2，7）=1，则411(mod7)。合同的基本性质性质11若acbc(modm)，且（c,m）=d，则ab(modm/d)证明：由acbc(modm)知，m|(a-b)c，而(c,m)=d，故m/d|(a-b)c/d。注意到（m/d,c/d）=1，所以由定理5.2.2，m/d|(a-b)，即ab(modm/d)。结论：若(c,m)=d,则(c/d,m/d)=1①证明：反证法，假设(c/d,m/d)=d’不是1，即d’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是整数变量，则由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|)9(modN0niianiia0§5.3.2剩余类一次同余式模m合同既然是一种等价关系，就可以把所有整数按照模m合同的关系分为等价类，每一个等价类称为模m的一个剩余类。例如，整数集合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作成一个完全剩余系，-1，0，1也作成一个完全剩余系。例模2，两个数0，1作成一个完全剩余系，0代表所有偶数，1代表所有奇数.同余式有棋子若干枚，三个三个的数剩两个，问至少有多少个棋子？答：由题意，棋子的个数减2是3的倍数，从而有，(x-2)=3y,x≥0，用合同式表示为：x≡2(mod3)，从而棋子的个数可能是：2,5,8,……，都是mod3合同2。同余式含有整数变量的合同式，称为合同方程或同余式。axb(modm)这种形式的合同式称为一次同余式；类似地，a2x2+a1xb(modm)称为二次同余式。同余式求解一次同余式axb(modm)实际上是解ax-b=my这样的不定方程。这里讨论一次同余式在什么条件下有解？什么条件下无解？什么时候有唯一解（一个剩余类）？什么时候有多解（多个剩余类）？定理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)。因为，由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与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所在的剩余类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的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）3×41×211+（-1）4×84×103。由此知，S=（-1）4×84，所以x=sb=84×57=4788=211×23-65-65(mod211)。求解一次合同方程的方法方法二:就是利用合同的性质，使x的系数变成1，即得到解。对于上例解合同式103x57(mod211)。由于211=103×2+5，由合同的性质7有2×103x2×57(mod211)。因为211x0(mod211)，所以由合同的性质4知，211x-2×103x0-2×57(mod211)。即5x-114(mod211)97(mod211)。求解一次合同方程的方法5x-114(mod211)97(mod211)。而211x0(mod211),由合同的性质7有42×5x42×97211×19+6565(mod211)。由合同的性质5知，211x-42×5x0-65(mod211)。即x-65(mod211)。对于一些例子，使用这种方法是比较快的。比如，解合同式4x1(mod15)。因为116(mod15)，所以4x4×4(mod15)，因为4与15互质，由合同的性质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:本定理可以作为同余式无解的判