《模线性方程与模线性方程组》由会员分享，可在线阅读，更多相关《模线性方程与模线性方程组（19页珍藏版）》请在金锄头文库上搜索。
1、模线性方程 模线性方程组henu 08wangnan今天要解决的问题：axbaxb (mod n) (mod n) a0 n0 a0 n0 x=?x=? 如：如：4x2(mod 5)4x2(mod 5)xa1 (mod n1)xa1 (mod n1)xa2 (mod n2) xa2 (mod n2)a0 n0 a0 n0 x=? x=? 如：如：x2(mod 5) x2(mod 5) x3(mod 13) x3(mod 13)求解模线性方程？axbaxb (mod n) (mod n) a0 n0 a0 n0 x=?x=? 如：如：4x2(mod 5)4x2(mod 5)1.是否有解？ 2.有
2、几个解？ 3.这些解分别是多少？分析l首先明确一点, 如果x是解(00 n0 a0 n0 x=? x=? 如：如：x2(mod 5) x2(mod 5) x3(mod 13) x3(mod 13)韩信点兵！在中国数学史上，广泛流传着一个“韩信点兵”的故事：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓 绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机 密，不让 敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个 士兵所报之数；再令士兵从至报数，也记下最后一个士兵所报之数；最后令 士兵从1至7 报数，又记下最后一个士兵所报之数；这样，他很快就
3、算出了自己 部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。韩信点兵！在中国数学史上，广泛流传着一个“韩信点兵”的故事：这个故事中所说的韩信点兵的计算方法，就是现在被称为“中国剩余定理”的 一次同余式解法。它是中国古代数学家的一项重大创造，在世界数学史上具有重 要的地位。孙子算经？解模线性方程组！最早提出并记叙这个数学问题的，是南北朝时期的数学著作孙子算经中的“ 物不知数”题目。这道“物不知数”的题目是这样的：“今有一些物不知其数量。如果三个三个地去数它，则最后还剩二个；如果 五个五个地去数它，则最后还剩三个；如果七个七个地去数它，则最后也剩二个 。问：这些物一共有多少？”用简
4、练的数学语言来表述就是：求这样一个数，使它被除余，被除余 ，被除余。 x 2(mod 3) x 3(mod 5) x 2(mod 7) X=?中国剩余定理l考虑方程组xai(mod mi), mi两两互素l在0i时ei0(mod mj)则e1a1+e2a2+ekak就是一个解, 调整得到0,m) 内的唯一解（想一想，如何调整）整理一下l一般线性方程组aixibi(mod ni)axb(mod n) xb1(mod n1)xb1(mod n1) xb1(mod p1,i)用中国剩余定理l其他规则同余方程二项方程: 借助离散对数(本身?)高次方程: 分解n, 降幂单个多变元线性方程: 消法求解模线性方程组步骤：1.找到模线性方程组中每个方程的ai ，ni 2.求出相对应的 mi , mi-1 3.求出相应的 ci =mi (mi-1 mod ni )4.最后一步：a (a1c1+a2c2+akck) (mod n)x 2(mod 3) x 3(mod 5) x 2(mod 7) x=?a1=2 n1=3 a2=3 n2=5 a3=2 n3=7n=n1*n2*n3=105m1=35 m1-1=2 m2=21 m2-1=1 m3=15 m3-2=1a=23+k*n(k=0,1,2)练习：Poj 1006
