• / 32
  • 下载费用:10 金币  

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

关 键 词:
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),因ji时,mi和mj互质,由定理5.2.3知,mi和 互质,从而由定理5.3.1,有ci使,证明 :,,取 ,则li适合(2)。今取x=a1l1+…+aklk (3) 则模mi, ,故x适合(1)。,证明 :,唯一性. 若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.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 一元高次同余式的化简,当求解的同余式模较大且是合数时,可以将原同余式转化为模较小的同余式组进行求解。例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,则ba(mod n),即,n|b-a,故有q,使得a=b+qn。 反证。若b和n不互质, 则b和n 有大于1的公因数d
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:5-4秦九韶定理 Euler函数_ou简.ppt
链接地址:https://www.weizhuannet.com/p-7352653.html
微传网是一个办公文档、学习资料下载的在线文档分享平台

微传网博客

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开