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

分析 首先明确一点, 如果x是解(0=xn), 则对于任意整数k, x+kn也是解, 所以解应表示成一些剩余类x≡xi ax≡b(mod n)等价于存在整数y, 使得 ax-ny=b 这是一个线性同余方程, 首先判断d=(a,n)是不是b的约数, 如果是, 等价于方程a’x-n’y=b’, 相当于求解 a’x≡b’(mod n’), (a’,n’)=1 分析 这个方程有两种解法 直接解ax-ny=d, 再两边同时乘以b/d. 注意这只是一个解, 一共应该有d个, 间隔为n/d(因为对于模n/d来说解是唯一的) 在模n’的缩系中a是存在逆a-1的. 因此解为x≡a’-1b’(mod n’), 同样扩展得d个解. 在缩系中求逆也有两种方法 求a’x-n’y=1的解, 和方法一等价 利用欧拉定理a-1≡aφ(n)-1(mod n) 求解模线性方程 ax≡b(mod n) 方法一：利用Euler函数 a*a?(n)-1 ?1 ?a(b*a?(n)-1) ?b 关键: 求abmod n a, a2, a4, a8, a16, … 同余方程可以做乘法，b做二进制展开选择 方法二：扩展的Euclid算法 存在整数y，使得ax-ny=b 记d=(a,n)，a’=a/d, n’=n/d，必须有d|b a’x-n’y=1*(b/d) 注意：x不唯一, 所有x相差n/d的整数倍 欧拉定理与费马定理 欧拉函数: 1~n中和n互素的元素个数?(n) Euler定理 若gcd(a, n)=1则a?(n) ?1 (mod n) 意义：当b很大时ab ?ab mod ?(n)(mod n)，让指数一直比较小 欧拉函数是积性函数，即当(m,n)=1时f(mn)=f(m)*f(n) 费马定理是欧拉定理在n为素数时的特殊情况： ap-1 ?1 (mod p) 其中p为素数 中国剩余定理 考虑方程组x≡ai(mod mi), mi两两互素 在0=xM=m1m2…mk内有唯一解 记Mi=M/mi，则(Mi,mi)=1 存在pi,qi，Mipi+miqi=1 记录ei=Mipi，则 j=i时ei≡1(mod mj) ji时ei≡0(mod mj) 则e1a1+e2a2+…+ekak就是一个解, 调整得到[0,m)内的唯一解（想一想，如何调整） 整理一下 一般线性方程组aixi≡bi(mod ni) ax≡b(mod n) ? x≡b1(mod n1) x≡b1(mod n1) ? x≡b1(mod p1,i) 用中国剩余定理 其他规则同余方程 二项方程: 借助离散对数(本身??) 高次方程: 分解n, 降幂 单个多变元线性方程: 消法 * * 模线性方程 模线性方程组 henu 08wangnan 今天要解决的问题： ax≡b (mod n) a0 n0 x=? 如：4x≡2(mod 5) x≡a1 (mod n1) x≡a2 (mod n2) a0 n0 x=? 如：x≡2(mod 5) x≡3(mod 13) 求解模线性方程？ ax≡b (mod n) a0 n0 x=? 如：4x≡2(mod 5) 1.是否有解？ 2.有几个解？ 3.这些解分别是多少？ ？ MODULAR-LINEAR-EQUATION-SOLVER(a, b, n) MODULAR-LINEAR-EQUATION-SOLVER(a, b, n) 1 (d, x′, y′) ← EXTENDED-EUCLID(a, n) 2 if d | b 3 then x0 ← x′(b/d) mod n 4 for i ← 0 to d - 1 5 do print (x0 + i(n/d)) mod n 6 else print no solutions MODULAR-LINEAR-EQUATION-SOLVER(a, b, n) MODULAR-LINEAR-EQUATION-SOLVER(4, 2, 5) 1 (1, 4, -3) ← EXTENDED-EUCLID(4 , 5 ) 2 if 1 | 2 3 then 3 ← 4 (2/1) mod 5 4 for i ← 0 to 1- 1 5 do print (3 + i (5/1)) mod 5 6 else print no solutions 4x≡2(mod 5) 4x≡2(mod 5) x有唯一解，x=3 MODULAR-LINEAR-EQUATION-SOLVER(a, b, n) MODULAR-LINE