模线性方程与模线性方程组.ppt

模线性方程模线性方程组 henu08wangnan 今天要解决的问题 ax b modn a 0n 0 x 如 4x 2 mod5 x a1 modn1 x a2 modn2 a 0n 0 x 如 x 2 mod5 x 3 mod13 求解模线性方程 ax b modn a 0n 0 x 如 4x 2 mod5 1 是否有解 2 有几个解 3 这些解分别是多少 分析 首先明确一点 如果x是解 0 x n 则对于任意整数k x kn也是解 所以解应表示成一些剩余类x xiax b modn 等价于存在整数y 使得ax ny b这是一个线性同余方程 首先判断d a n 是不是b的约数 如果是 等价于方程a x n y b 相当于求解a x b modn a n 1 分析 这个方程有两种解法直接解ax ny d 再两边同时乘以b d 注意这只是一个解 一共应该有d个 间隔为n d 因为对于模n d来说解是唯一的 在模n 的缩系中a是存在逆a 1的 因此解为x a 1b modn 同样扩展得d个解 在缩系中求逆也有两种方法求a x n y 1的解 和方法一等价利用欧拉定理a 1 a n 1 modn 求解模线性方程 ax b modn 方法一 利用Euler函数a a n 1 1 a b a n 1 b关键 求abmodna a2 a4 a8 a16 同余方程可以做乘法 b做二进制展开选择方法二 扩展的Euclid算法存在整数y 使得ax ny b记d a n a a d n n d 必须有d ba x n y 1 b d 注意 x不唯一 所有x相差n d的整数倍 欧拉定理与费马定理 欧拉函数 1 n中和n互素的元素个数 n Euler定理若gcd a n 1则a n 1 modn 意义 当b很大时ab abmod n modn 让指数一直比较小欧拉函数是积性函数 即当 m n 1时f mn f m f n 费马定理是欧拉定理在n为素数时的特殊情况 ap 1 1 modp 其中p为素数 MODULAR LINEAR EQUATION SOLVER a b n MODULAR LINEAR EQUATION SOLVER a b n 1 d x y EXTENDED EUCLID a n 2ifd b3thenx0 x b d modn4fori 0tod 15doprint x0 i n d modn6elseprint nosolutions MODULAR LINEAR EQUATION SOLVER a b n MODULAR LINEAR EQUATION SOLVER 4 2 5 1 1 4 3 EXTENDED EUCLID 4 5 2if1 23then3 4 2 1 mod54fori 0to1 15doprint 3 i 5 1 mod56elseprint nosolutions 4x 2 mod5 4x 2 mod5 x有唯一解 x 3 MODULAR LINEAR EQUATION SOLVER a b n MODULAR LINEAR EQUATION SOLVER 14 30 100 1 2 7 1 EXTENDED EUCLID 14 100 2if2 303then95 7 30 2 mod1004fori 0to2 15doprint 95 i 100 2 mod1006elseprint nosolutions 14x 30 mod100 14x 30 mod100 x有两个解 x 95 x 45 练习 Poj1061青蛙的约会 接下来要解决的问题 x a1 modn1 x a2 modn2 a 0n 0 x 如 x 2 mod5 x 3 mod13 韩信点兵 在中国数学史上 广泛流传着一个 韩信点兵 的故事 韩信是汉高祖刘邦手下的大将 他英勇善战 智谋超群 为汉朝的建立了卓绝的功劳 据说韩信的数学水平也非常高超 他在点兵的时候 为了保住军事机密 不让敌人知道自己部队的实力 先令士兵从1至3报数 然后记下最后一个士兵所报之数 再令士兵从 至 报数 也记下最后一个士兵所报之数 最后令士兵从1至7报数 又记下最后一个士兵所报之数 这样 他很快就算出了自己部队士兵的总人数 而敌人则始终无法弄清他的部队究竟有多少名士兵 韩信点兵 在中国数学史上 广泛流传着一个 韩信点兵 的故事 这个故事中所说的韩信点兵的计算方法 就是现在被称为 中国剩余定理 的一次同余式解法 它是中国古代数学家的一项重大创造 在世界数学史上具有重要的地位 孙子算经 解模线性方程组 最早提出并记叙这个数学问题的 是南北朝时期的数学著作 孙子算经 中的 物不知数 题目 这道 物不知数 的题目是这样的 今有一些物不知其数量 如果三个三个地去数它 则最后还剩二个 如果五个五个地去数它 则最后还剩三个 如果七个七个地去数它 则最后也剩二个 问 这些物一共有多少 用简练的数学语言来表述就是 求这样一个数 使它被 除余 被 除余 被 除余 x 2 mod3 x 3 mod5 x 2 mod7 X 中国剩余定理 考虑方程组x ai modmi mi两两互素在0i时ei 0 modmj 则e1a1 e2a2 ekak就是一个解 调整得到 0 m 内的唯一解 想一想 如何调整 整理一下 一般线性方程组aixi bi modni ax b modn x b1 modn1 x b1 modn1 x b1 modp1 i 用中国剩余定理其他规则同余方程二项方程 借助离散对数 本身 高次方程 分解n 降幂单个多变元线性方程 消法 求解模线性方程组步骤 找到模线性方程组中每个方程的ai ni求出相对应的mi mi 1求出相应的ci mi mi 1modni 最后一步 a a1c1 a2c2 akck modn