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

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 合同为整除的另一种表示法 故整除的性质在此可用 特别地 若b 0 则a 0 modm 表示的就是m a 2 若m a 则 m a 所以 若未指定m而一般地讨论模m合同时 总假定m是正整数 5 3 1合同及其性质 3 设a q1m r1 0 r1 m b q2m r2 0 r2 m 于是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 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 求解一次合同方程的方法 以解合同式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如下所示 求解一次合同方程的方法 解合同式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 本定理可以作为同余式无解的判定定理 定理5 3 3 若 a m d 1 且d b 则同余式ax b modm 1 有d个解 分别为 m d 2m d d 1 m d 2 其中 是同余式 a d x b d modm d 3 的解 例 解合同式6x 15 mod33 解 6 33 3而3 15 因此上述合同式有3个解 先求2x 5 mod11 的解 2x 16 mod11 x 8 mod11 原合同式有3个解 8 8 11 8 22即x 8 mod33 x 19 mod33 x 30 mod33 总结 一次同余式ax b modm a m 1 b任意 有一个解 d 1 d b 有d个解 d b 无解 作业 习题5 3 2 会把任意两个整数的最高公因数表示成倍数和形式掌握几种类型图不是H图 Cm n 当m n是非Hamilton图 是非Hamilton图会求解一次同余式 关系的性质总结 习题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 证明 因为R是等价关系 所以R具有传递性 故R2 R 下面证明R R2 任取 x y R 因R等价关系 所以R具有自反性 则有 y y R 因 x y R y y R 所以 x y R R 即 x y R2 因此R R2 综上 R2 R 证毕 求G R P Q P R 的主析取范式G R P Q P R R P Q P Q R P R P Q Q R P R Q Q P Q R R Q R P P P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R 求G R P Q P R 的主合取范式G R P Q P R R P Q R P P R R P Q R P P R R Q P Q P R R P P R R Q P Q P R R Q P P P Q R R P R Q Q P Q R P Q R P Q R P Q R 例设 A 是一个偏序集 其中A 1 2 3 11 其Hasse图如下 左图 所示 设B 6 7 10 求B的最大元 最小元 上界 下界 最小上界和最大下界 最大元 10最小元 无上界 10 11下界 1 4最小上界 10最大下界 4 例 设命题公式集合A P Q R P Q P Q Q R Q R P Q R 是集合A上的公式蕴涵关系 请画出部分序集 A 的Hasse图 并指出其中的最大元 最小元 极大元和极小元 设命题公式的集合S P Q P P P 1 P Q 0 Q Q Q P Q 是S上的公式等价关系 求S关于 的商集 解 S关于 的商集 S 为 P P P P 1 Q 0 Q Q Q P Q P Q 怎么将公式G化成与其等价的前束范式 使用基本等价式 K H K H H K K H K H可将公式G中的 和 删除 2 使用 H H 摩根律 引理3 2 1的公式 3 和 4 可将公式中所有否定号 放在原子之前 3 如果必要的话 则将约束变量改名 4 使用引理3 2 1 3 2 2将所有量词都提到公式的最左边 例 将下面公式化为Skolem范式 x y A x B x y yC y zD z 解 x y A x B x y yC y zD z 消去 x y A x B x y yC y zD z 移 x y A x B x y y C y zD z 改名 x y A x B x y t C t zD z 前提 x y t z A x B x y C t D z x y t z A x C t D z B x y C t D z 用a代替x 用b代替y 用f t 代替z 得公式的Skolem范式 t A a C t D f t B a b C t D f t 证明A B C D D E F共同蕴涵A F 1 A规则3 2 A B规则2 根据 1 3 A B C D规则1 4 C D规则2 根据 2 3 5 D规则2 根据 4 6 D E规则2 根据 5 7 D E F规则1 8 F规则2 根据 6 7 10 A F规则3 根据 1 8 简答题 1 所有质数构成的集合是可数集合吗 是2 设集合A 1 2 计算A A A A 1 1 1 1 2 1 1 2 2 2 1 2 2 2 1 2 3 设R是一个二元关系且满足R R4 则R3是否满足传递性 为什么 满足传递性 因为 R3 2 R4 R2 R R2 R3 4 有限有向图G是Euler图 则G一定是强连通图吗 G一定是平衡的吗 解 不一定 一定5 对于原子P Q R而言 共有几个极大项 满足某个极大项Mi的解释唯一吗 若不唯一 应该有多少个 解 不唯一 7 6 设集合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 c 7 设集合A 1 2 3 10 R是模4同余关系 即R x y x y A x y除以4余数相同 则R是等价关系 求商集A R 解 A R 1 5 9 2 6 10 3 7 4 8 极小项与极大项性质 极小项与极大项性质 对n个命题原子P1 Pn极小项有如下性质 1 n个命题原子P1 Pn有2n个不同的解释 每个解释对应P1 Pn的一个极小项 2 对P1 Pn的任意一个极小项m 有且只有一个解释使m取1值 若使极小项取1值的解释对应的十进制数为i 则m记为mi 3 任意两个不同的极小项的合取式恒假 mi mj 0 i j 4 所有极小项的析取式恒真 9 有限图G的闭合图一定是Hamilton图吗 若是 为什么 若不是 请举例说明解 不一定 下图的闭合图与自身同构无H回路10 对于有n个点的连通图G 图G至少需要有多少条边 为什么 解 n 1条边 因为树是n个点的连通图中 边最少的 缺少任意一条边都不再连通 1