53合同次同余式

1、5.3 合同 一次同余式 引入看任意整数a除以3所得的余数：0 03 + 0;1 03 + 1; -1 (-1)3 + 2; 2 03 + 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(mod 3) 则，还有下面的式子： 3 0(mod 3) 0 3(mod 3) 4 1(mod 3) 1 4(mod 3) 5 2(mod 3) 2 5(mod 3) 5.3.1 合同及其性质 定义

2、. 设a,b为二整数，m是任意非0整数。 若 m|a-b，则称a合同于b 模m。 记为：ab(mod m)Note:合同为整除的另一种表示法，故整除的性质在此可用。 特别地，若b=0，则a0(mod m)表示的就是m|a。(2) 若m|a，则- m|a。所以，若未指定m而一般地讨论模m合同时，总假定m是正整数。 5.3.1 合同及其性质 (3)设a=q1m+r1，0r1m； b=q2m+r2，0r2m。于是a-b=(q1-q2)m+(r1-r2)则 m|(a-b) iff m|(r1-r2)，但|r1-r2|1 , 则d|c/d ，dd|c ,并且d|m/d ，dd|m ，得到 dd为c,m的

3、公因数，则dd|d ，即d|1，矛盾。合同的基本性质性质12 若p为质数，c0(mod p)，而acbc(mod p)，则ab(mod p)。证明：因为p是质数，c 0(mod p)就表示p | c, 即c和p互质，(c, p)=1，因而性质12不过是性质10的推论(原来的整数模m换成了现在的质数模p)。合同的基本性质 性质13 设p(x)是整系数多项式，x和y是整数变量，则由xy(mod m)可得 p(x) p(y) (mod m)。 证明：设p(x)=anxn+an-1xn-1+a1x1+a0, p(y)=anyn+an-1yn-1+a1y1+a0, 由xy(mod m)和性质8, xky

4、k(mod m).由性质7得akxkakyk(mod m).由性质4得 anxn+an-1xn-1+a1x1+a0 anyn+an-1yn-1+a1y1+a0 (mod m).即p(x) p(y) (mod m)。 例.求能被9整除的正整数的数码特征。设N=an10n+an-110n-1+a110+a0为一正整数，因为101(mod 9)，由性质13得N an1n+an-11n-1+a1+a0(mod 9)即 。于是 9|N当且仅当9| 5.3.2 剩余类 一次同余式 模m合同既然是一种等价关系，就可以把所有整数按照模 m合同的关系分为等价类，每一个等价类称为模m的一个剩余类。例如，整数集合Z

5、，模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恰好合同于此完全剩余

6、系中的一个数。例 模3，三个数0，1，2作成一个完全剩余系，-1，0，1也作成一个完全剩余系。例 模2，两个数0，1作成一个完全剩余系，0代表所有偶数，1代表所有奇数. 同余式 有棋子若干枚，三个三个的数剩两个，问至少有多少个棋子？答：由题意，棋子的个数减2是3的倍数，从而有，(x-2)=3y, x0，用合同式表示为：x2(mod 3)，从而棋子的个数可能是：2, 5, 8, ，都是mod 3合同2。同余式 含有整数变量的合同式，称为合同方程或同余式 。axb(mod m)这种形式的合同式称为一次同余式；类似地，a2x2+a1xb(mod m)称为二次同余式。 同余式 求解一次同余式axb(m

7、od m)实际上是解 ax-b=my这样的不定方程。这里讨论一次同余式在什么条件下有解？什么条件下无解？什么时候有唯一解（一个剩余类）？什么时候有多解（多个剩余类）？ 定理5.3.1 若a和m互质，b任意，则模m恰有一个数x使axb(mod m) 。证明： 存在性。因为a和m互质，根据定理5.2.1，有s，t使as+mt=1，于是asb+mtb=b，若取模m，则有asbb(mod m)。取x=sb，则sb所在的剩余类中的数皆是解。Note:证明过程也给出了x的求解方法。定理5.3.1 若a和m互质，b任意，则模m恰有一个数x使axb(mod m) 。证明： 唯一性。所谓模m只有一个这样的x，意

8、思是说在模m合同的意义下，解是唯一的。即若axb (mod m)，ayb(mod m)，则xy(mod m)。因为，由axb(mod m)，ayb(mod m)得axay(mod m)，消去和m互质的a得xy (mod m).即x, y在一个剩余类中。定理5.3.1推论 设p为质数。若a 0 (mod p)，b任意，则模p恰有一个数x使axb(mod p)。证明：由已知，a与p互质，再由定理5.3.1，模p恰有一个数x使axb(mod p)。求解一次合同方程的方法 以解合同式103x57(mod 211)为例.方法一:定理5.3.1告诉我们若a和m互质，b任意，则模m恰有一个数x使axb(mo

9、d m)。该定理证明存在性的过程即告诉了我们一种求解方法：因为a和m互质，故有s，t使as+mt=1，于是asb+mtb=b，若取模m，则有asbb(mod m)。取x=sb，则sb所在的剩余类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的a与m的最大公因数1表示为a和m的倍数和的形式：1=as+mt，然后取x=sb，即可。 求解一次合同方程的方法解合同式103x57(mod 211)解：a=103与m=211互质，先将103与211的最大公因数1表示为它们的倍数和的形式。使用辗转相除方法逐次得商及余数并计算Sk，Tk如下所示：k012345rk53210qk220112Sk0120

10、2141Tk12414384求解一次合同方程的方法解合同式103x57(mod 211)因此， 1=（-1）341211+（-1）484103。由此知，S=（-1）484，所以x=sb=8457=4788=21123-65-65(mod 211)。求解一次合同方程的方法方法二:就是利用合同的性质，使x的系数变成1，即得到解。对于上例解合同式103x57(mod 211)。由于211=1032+5，由合同的性质7有2103x257(mod 211)。因为211x0(mod 211)，所以由合同的性质4知，211x-2103x0-257(mod 211)。即5x-114(mod 211) 97(m

11、od 211)。求解一次合同方程的方法5x-114(mod 211) 97(mod 211)。而211x0(mod 211) ,由合同的性质7有425 x4297 21119+65 65(mod 211)。由合同的性质5知，211x-425 x0-65(mod 211)。即x-65(mod 211)。对于一些例子，使用这种方法是比较快的。比如，解合同式4x1(mod 15)。因为 116(mod 15)，所以4x44(mod 15)，因为4与15互质，由合同的性质10知，合同式两边可以消去4，得到 x4(mod 15)。 例. 解合同式14x27(mod 31)。解： 28x54(mod 31

12、) 31x0(mod 31) 故 3x-54(mod 31) x-18(mod 31) 13(mod 31)还可以： 14x58(mod 31) 7x29(mod 31) 7x91(mod 31) x13(mod 31)定理5.3.2若(a, m)=d1，且d | b，则同余式axb (mod m)无解。证明：反证法。若上式可解，则存在，使得ab(mod m)。从而存在q，使a-b=mq, 即b=a-mq。因为(a, m)=d1 ，所以，d|a,d|m，因此，d|a， d|mq，故即d|b，矛盾。 Note:本定理可以作为同余式无解的判定定理.定理5.3.3若(a, m)=d1 ，且d|b，则

13、同余式axb(mod m) (1)有d个解，分别为 , +m/d, +2m/d, , +(d-1)m/d (2)其中是同余式(a/d)xb/d (mod m/d) (3)的解。 例. 解合同式6x15(mod 33)。解:(6，33)=3 而 3|15 , 因此上述合同式有3个解。 先求2x 5(mod 11)的解。 2x 16(mod 11) x 8(mod 11) 原合同式有3个解：8，8+11，8+22即x8(mod 33)， x19(mod 33)， x30(mod 33)总结一次同余式ax b(mod m)：(a, m)=1, b任意; 有一个解d1d | b; 有d个解 d | b

14、; 无解 作业：习题5.3-2会把任意两个整数的最高公因数表示成倍数和形式掌握几种类型图不是H图 Cm,n ;当mn 是非Hamilton图 是非Hamilton图 会求解一次同余式KmcKnc关系的性质总结自反的反自反的对称的反对称的传递的定义任取 aA有(a,a)R任取 aA有(a,a)R若(a,b)R,则(b,a)R若(a,b)R,(b,a)R, 则 a=b若(a,b)R且(b,c)R, 则(a,c)R 集合IARIAR=R-1=RRR-1IAR2 R关系图图中每个结点都有自回路图中每个结点都无自回路任意两个不同结点间要么没有弧,要么有一对方向相反的弧任意两个不同结点间至多有一条弧若a到

15、b有弧,b到c有弧,则a到 c有弧关系矩阵主对角线上全为1主对角线上全为0对称矩阵以主对角线为对称的元素不同时为1MR2中某元素为1， MR中相应位置元素也一定为1习题1.2-6、若非空关系R是反自反的，是对称的，试证明R不是传递的。证明：反证法：假设R是传递的，对于任意(a，b)R，因为R是对称的，所以(b，a) R，则有(a，a) R，这与R是反自反的矛盾，故假设不成立，原结论成立。习题1.2-7、集合A上的关系是对称的，反对称的，试指明关系R的结构。解：IA的任意子集。例：集合A有n个元素，则A上有多少个即具有对称性有具有反对称性的关系？ 2n设R是集合A上的等价关系，证明：R2=R。证

16、明：因为R是等价关系，所以R具有传递性，故R2R；下面证明RR2，任取(x,y)R，因R等价关系，所以R具有自反性，则有(y,y)R，因(x,y)R，(y,y)R，所以(x,y) RR，即(x,y)R2。因此RR2。综上，R2=R。证毕。求G=(RP)(Q(PR)的主析取范式G =(RP)(Q(PR)=(R P)(Q P)(Q R)=(P R)(P Q)(Q R) =(PR)(QQ)(PQ)(RR)( (QR)(PP) =(PQR) (PQR) (PQR) (PQR) (PQR) (PQR) =(PQR)(PQR)(PQR)(PQR)求G=(RP)(Q(PR)的主合取范式G=(R P) (Q(

17、PR)=（(R P) Q）（(R P) (PR)）=(R P) Q) (R P) (PR)）=(RQ) ( P Q) ( PRR) ( P PR)=(RQ) ( P Q) ( PR)=(RQ(P P) )( P Q(R R) ( PR( Q Q)=(PQ R) ( PQ R) ( PQ R) (PQ R)例设（A, ）是一个偏序集，其中A=1,2,3,11，其Hasse图如下（左图）所示，设B=6,7,10，求B的最大元、最小元、上界、下界、最小上界和最大下界.最大元：10 最小元：无上界：10,11 下界：1,4最小上界：10 最大下界：4例：设命题公式集合A=P, Q, R, PQ, PQ

18、, QR, QR, PQR，“”是集合A上的公式蕴涵关系，请画出部分序集（A，）的Hasse图，并指出其中的最大元、最小元、极大元和极小元。PQRPQQRRQPP QQR设命题公式的集合S=P, Q, PP, P1, PQ, 0Q, QQ, PQ，=是S上的公式等价关系，求S关于=的商集？ 解：S关于=的商集(S/=)为P, PP, P1, Q, 0Q, QQ, PQ, PQ怎么将公式G化成与其等价的前束范式？使用基本等价式(KH)=(KH)(HK)(KH)=KH可将公式G中的和删除。2. 使用(H)=H，摩根律，引理3.2.1的公式(3)和(4)，可将公式中所有否定号放在原子之前。3. 如果

19、必要的话，则将约束变量改名。4. 使用引理3.2.1，3.2.2将所有量词都提到公式的最左边。例. 将下面公式化为Skolem范式xy（A(x) B(x,y)）(yC(y) zD(z) 解： xy（A(x) B(x,y)）(yC(y) zD(z) (消去)= xy( A(x) B(x,y)(yC(y) zD(z) (移)= xy(A(x) B(x,y) (y C(y) zD(z) (改名)= xy(A(x) B(x,y) (t C(t) zD(z) (前提）= xytz(A(x) B(x,y) C(t) D(z)）=xytz(A(x)C(t)D(z)(B(x,y)C(t)D(z)用a代替x，用

20、b代替y，用f(t)代替z，得公式的Skolem范式：t(A(a) C(t) D(f(t) ( B(a,b) C(t) D(f(t) 证明ABCD,DEF共同蕴涵 AF(1)A 规则3(2)AB 规则2，根据(1)(3) ABCD 规则1(4) CD 规则2,根据(2) (3)(5) D 规则2,根据(4) (6) DE 规则2，根据(5)(7) DEF 规则1(8) F 规则2,根据(6) (7)(10) AF 规则3，根据(1) (8)简答题：1、所有质数构成的集合是可数集合吗？ 是2、设集合A=1, 2，计算A(A).A(A)=(1,),(1,1),(1,2),(1,1,2),(2,),

21、(2,1),(2,2),(2,1,2)3、设R是一个二元关系且满足R=R4，则R3是否满足传递性，为什么？满足传递性；因为(R3)2= R4R2= RR2= R3.4、有限有向图G是Euler图，则G一定是强连通图吗？G一定是平衡的吗？解：不一定，一定5、对于原子P、Q、R而言，共有几个极大项？满足某个极大项Mi的解释唯一吗？若不唯一，应该有多少个？解：不唯一；76、设集合A=a, b, c, d，R是A上的等价关系且A/R=a,b,c,d，求R.解：R=a,a,b,b,c,c,d,d,a,b,b,a,c,d, d,c7、设集合A=1,2,3,10，R是模4同余关系，即R= (x,y)|x,y

22、A，x,y除以4余数相同 ，则R是等价关系，求商集A/R。解：A/R=1,5,9,2,6,10,3,7,4,8极小项与极大项性质PQR极小项 极大项 000m0= P QRM0=PQR 001m1= P QRM1=PQR010m2= P QRM2=PQR011m3= P QRM3=PQR100m4= P Q RM4=PQR101m5= P Q RM5=PQ R110m6= P Q RM6=P Q R111m7= P Q RM7=PQR极小项与极大项性质对n个命题原子P1，Pn极小项有如下性质：（1）n个命题原子P1，Pn有2n个不同的解释，每个解释对应P1，Pn的一个极小项。（2）对P1，Pn

23、的任意一个极小项m，有且只有一个解释使m取1值，若使极小项取1值的解释对应的十进制数为i，则m记为mi。（3）任意两个不同的极小项的合取式恒假： mi mj=0，ij。（4）所有极小项的析取式恒真。 9、有限图G的闭合图一定是Hamilton图吗？若是，为什么？若不是，请举例说明解：不一定，下图的闭合图与自身同构无H回路10、对于有n个点的连通图G，图G至少需要有多少条边？为什么？ 解：n-1条边，因为树是n个点的连通图中，边最少的，缺少任意一条边都不再连通。11、设命题公式的集合S=P, Q, PP, P1, PQ, 0Q, QQ, PQ，=是S上的公式等价关系，求S关于=的商集？解：S关于=的商集(S/=)为P, PP, P1, Q, 0Q, QQ