5-4秦九韶定理 Euler函数_ou简.ppt

§5.4 秦九韶定理 Euler函数 §5.4.1 一次同余式组 秦九韶定理 证明 : 存在性. 先不讨论普遍情形而先求li，i=1,…,k，使适合下列特殊的合同式：  li?1(mod mi)，  li?0(mod mj)，j?i (2) 证明 : 证明 : 唯一性. 若x，x?都适合(1)，则 x≡x?(mod mi)，i=1,…,k，即 mi| x-x?，再由m1, m2 , …, mk两两互质，及定理5.2.4，得 m1m2 … mk | x-x? 故 x≡x? (mod m1…mk) Note:证明过程使用了构造性证明方法，先构造一些满足局部合同式的局部解，再把这些局部解合起来构造成整体解。 （1）对i=1,…,k解合同方程 求出Ci。 （2） （3） x=a1l1+…+aklk 例5.4.1 求x满足同余式组：x≡1(mod 4)x≡2(mod 5)x≡3(mod 7) 解：因为模4，5，7两两互质，所以可以用上述定理的构造性证明过程求解。先求l1，l2，l3使得 例5.4.1 l1≡1(mod 4) l2≡1(mod 5) l3≡1(mod 7) l1≡0(mod 5) l2≡0(mod 4) l3≡0(mod 4) l1≡0(mod 7) l2≡0(mod 7) l3≡0(mod 5) 得l1=35c1，l2=28c2，l3=20c3，c1满足35c1≡1(mod 4)，即 3c1≡1(mod 4)，从而 c1≡3(mod 4)。故l1=105。同理得l2=56， l3=120。 于是 x=1?105+2?56+3?120=577≡17(mod 140)。 南宋数学家 秦九韶（公元1202-1261年） 1247年，著成『数书九章』十八卷，这是一部划时代的巨著，它总结了前人在开方中所使用的方法，将其整齐而有系统地应用到高次方程的有理或无理根的求解上去。 秦九韶给出了解一次同余式组的一般方法以及理论上的证明，并将它定名为“大衍求一术”，在世界数学史上占有崇高的地位。 对「正负开方术」﹝高次方程的数值解法）等也有十分深入的研究。 §5.4.2 一元高次同余式的化简 定理5.4.3 设f(x)是整系数多项式,m=p1r1p2r2…pnrn 为m的质因数分解式，则同余式 f(x) ≡0(mod m) (4) 与下述同余式组等价 f(x) ≡0(mod p1r1) (5) … … f(x) ≡0(mod pnrn ) 证明：（4）的解显然是（5）的解。 反之，若x1是（5）的解，则 piri|f(x1)。注意到p1r1，p2r2，…，pnrn 两两互质，故 p1r1p2r2…pnrn|f(x1)，即m|f(x1)。因此 f(x1)≡0(mod m)，即x1是（4）的解。 当求解的同余式模较大且是合数时，可以将原同余式转化为模较小的同余式组进行求解。 例5.4.2 求解同余式 37x≡55(mod 60) 解：注意到（37，60）=1，故完全可以用上节的定理5.3.1证明和辗转相除法求解。这里用同余式组来求解。因为60=22?3?5，所以原同余式等价于 37x≡55(mod 4) 37x≡55(mod 3) 37x≡55(mod 5) 等价化简同余式组得 x≡3(mod 4) x≡1(mod 3) 2x≡0(mod 5) 又因为（2，5）=1，所以又等价于 x≡3(mod 4) x≡1(mod 3) x≡0(mod 5) 解此同余式组得 x≡55(mod 60) 秦九韶定理本身是解一种最简单的同余式组，较一般的 情况是 f1(x)≡0(mod m1) (6) … … … fk(x)≡0(mod mk) 其中m1，…，mk两两互质，fi (i=1, …, k)为整系数多项 式。假若（6）中第i个同余式有解ai，则（6）式的求解 就转化为一系列下述形式的同余式组的求解： x≡a1 (mod m1) … … … x≡ak (mod mk) 因此，秦九韶定理即是求解最简单的同余式组的方法， 也是解高次同余式组的基础。 结论：设n是任意正整数， A 为mod n的任意剩余类，a?A。若a和n互质，则A中任意数和n互质。 证明：任取b?A