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

§5.4秦九韶定理Euler函数§5.4.1一次同余式组秦九韶定理秦九韶定理设m1,m2,…,mk两两互质。a1,a2,…,ak为k个整数，则下列同余式组有解，且在模m1m2…mk下解唯一：xa1(modm1)，xa2(modm2)，..........，xak(modmk)。(1)证明:存在性.先不讨论普遍情形而先求li，i=1,…,k，使适合下列特殊的合同式：li1(modmi)，li0(modmj)，ji(2)因ji时，mi和mj互质，由定理5.2.3知，mi和互质，从而由定理5.3.1，有ci使jijm)(mod1ijijimmc证明:取，则li适合(2)。今取x=a1l1+…+aklk(3)则模mi，，故x适合(1)。jijiimcliijjijijjiiaaalaxla01证明:唯一性.若x，x都适合(1)，则x≡x(modmi)，i=1,…,k，即mi|x-x，再由m1,m2,…,mk两两互质，及定理5.2.4，得m1m2…mk|x-x故x≡x(modm1…mk)Note:证明过程使用了构造性证明方法，先构造一些满足局部合同式的局部解，再把这些局部解合起来构造成整体解。（1）对i=1,…,k解合同方程求出Ci。（2）（3）x=a1l1+…+aklk)(mod1ijijimmcjijiimcl例5.4.1求x满足同余式组：x≡1(mod4)x≡2(mod5)x≡3(mod7)解：因为模4，5，7两两互质，所以可以用上述定理的构造性证明过程求解。先求l1，l2，l3使得例5.4.1l1≡1(mod4)l2≡1(mod5)l3≡1(mod7)l1≡0(mod5)l2≡0(mod4)l3≡0(mod4)l1≡0(mod7)l2≡0(mod7)l3≡0(mod5)得l1=35c1，l2=28c2，l3=20c3，c1满足35c1≡1(mod4)，即3c1≡1(mod4)，从而c1≡3(mod4)。故l1=105。同理得l2=56，l3=120。于是x=1105+256+3120=577≡17(mod140)。南宋数学家秦九韶（公元1202-1261年）1247年，著成『数书九章』十八卷，这是一部划时代的巨著，它总结了前人在开方中所使用的方法，将其整齐而有系统地应用到高次方程的有理或无理根的求解上去。秦九韶给出了解一次同余式组的一般方法以及理论上的证明，并将它定名为“大衍求一术”，在世界数学史上占有崇高的地位。对「正负开方术」﹝高次方程的数值解法）等也有十分深入的研究。定理5.4.3设f(x)是整系数多项式,m=p1r1p2r2…pnrn为m的质因数分解式，则同余式f(x)≡0(modm)(4)与下述同余式组等价f(x)≡0(modp1r1)(5)……f(x)≡0(modpnrn)证明：（4）的解显然是（5）的解。反之，若x1是（5）的解，则piri|f(x1)。注意到p1r1，p2r2，…，pnrn两两互质，故p1r1p2r2…pnrn|f(x1)，即m|f(x1)。因此f(x1)≡0(modm)，即x1是（4）的解。§5.4.2一元高次同余式的化简当求解的同余式模较大且是合数时，可以将原同余式转化为模较小的同余式组进行求解。例5.4.2求解同余式37x≡55(mod60)解：注意到（37，60）=1，故完全可以用上节的定理5.3.1证明和辗转相除法求解。这里用同余式组来求解。因为60=2235，所以原同余式等价于37x≡55(mod4)37x≡55(mod3)37x≡55(mod5)等价化简同余式组得x≡3(mod4)x≡1(mod3)2x≡0(mod5)又因为（2，5）=1，所以又等价于x≡3(mod4)x≡1(mod3)x≡0(mod5)解此同余式组得x≡55(mod60)秦九韶定理本身是解一种最简单的同余式组，较一般的情况是f1(x)≡0(modm1)(6)………fk(x)≡0(modmk)其中m1，…，mk两两互质，fi(i=1,…,k)为整系数多项式。假若（6）中第i个同余式有解ai，则（6）式的求解就转化为一系列下述形式的同余式组的求解：x≡a1(modm1)………x≡ak(modmk)因此，秦九韶定理即是求解最简单的同余式组的方法，也是解高次同余式组的基础。结论：设n是任意正整数，A为modn的任意剩余类，aA。若a和n互质，则A中任意数和n互质。证明：任取bA，则ba(modn)，即，n|b-a，故有q，使得a=b+qn。反证。若b和n不互质，则b和n有大于1的公因数d，即d|b,d|n，故d|b+qn，即d|a。因此，d为a,n的公因数，且d1，这与a和n互质矛盾。§5.4.3Euler函数可见，若A中有一个数和n互质，则其中所有的数都和n互质。故A中的数或者都和n互质，或者都和n不互质。例.mod62，8，16，…,与6都不互质。5，11，17，…,与6都互质。定义.设A为modn的一个剩余类，若对aA，a与n互质，则称剩余类A与n互质。Euler函数Euler函数定义和n互质的剩余类的个数称为Euler(欧拉)函数,记为(n)。定义从和n互质的每一个剩余类中取出一个数，这样得到的(n)个数称之为作成modn的一个简化剩余系。显然，从modn的一个非负最小完全剩余系中取出与n互质的那些数,就得到modn的一个简化剩余系，因而(n)等于n的正数中和n互质的数的个数。例n=10，则modn的一个完全剩余系为0，1，…，9，一个简化剩余系为1，3，7，9，(10)=4。例n=12，则modn的一个完全剩余系为0，1，…，11，一个简化剩余系为1，5，7，11，(12)=4。如何求Euler函数定理5.4.5设m=m1…mk，而m1,…,mk两两互质。则(m)=(m1)(m2)…(mk)(9)例.(2646)=(2×27×49)=(2)×(27)×(49)定理5.4.6设是n的质因数分解式，p1,…,pk都不同，于是)11)...(11()(1kppnnkrkrppn...11例(2646)=(2×33×72)=2646×(1-1/2)(1-1/3)(1-1/7)=756证明：首先考虑最简单情形:n=p为质数，则(n)=p-1=p(1-1/p)，结论成立。其次考虑n=pr，p为质数，而求(pr)。因为一个数a和pr互质等于说a不是p的倍数，所以(pr)就是从1到pr的pr个数中找出不是P倍数的数的个数。而从1到pr的pr个数中，是p的倍数的共pr-1个，即p，2p，…，pr-1p因而和p互质的共pr-pr-1个，故(n)=(pr)=pr-pr-1=pr(1-1/p)结论成立。证明：第三考虑一般情况，，p1,…,pk互不相同，则(pi,pj)=1(ij)。从而。由定理5.4.5及上述第二种情形证明有krkrppn...11)(1),(jippjirjri)11)...(11)(11()11()...11()11()()()()(212211212121kkrkrrrkrrpppnpppppppppnkk定理5.4.7(Fermat-Euler定理,Euler1760年提出)若a和n互质，则a(n)1(modn)（证明见下页）例：a=3,n=10,3与10互质,(10)=4,则341(mod10)a=5,n=12,5与12互质,(12)=4,则541(mod12)推论1(Fermat小定理Ⅰ)若p是质数而p|a，则ap-11(modp)。--1640年Fermat提出,1736年Euler证明推论2（Fermat小定理Ⅱ）若p为质数，则对任意整数a,都有apa(modp)。例:p=3,23-11(mod3)232(mod3)Fermat-Euler定理若a和n互质，则a(n)1(modn)证明：设r1，…，r(n)是modn的一个简化剩余系，则(ri,n)=1，i=1，…，(n)，从而(r1…r(n)，n)=1。再看ar1,…,ar(n)(1)当i≠j时，往证ariarj(modn)。反证。若ariarj(modn)，则因a和n互质，得rirj(modn)，矛盾。(2)往证ari一定属于某简化剩余类，i=1，…，(n)。因为(a,n)=1，(ri,n)=1，所以(ari,n)=1。必有r1，…，r(n)中某个rj，使得arirj(modn)。因此，ar1，…,ar(n)也作成modn的一个简化剩余系（即是说，如果把剩余类中元素看成同一个元素的话，ar1,…,ar(n)是r1，…，r(n)的一个重新排列）。因此，ar1…ar(n)r1…r(n)(modn)。而(r1…r(n)，n)=1，故消去律成立，于是a(n)1(modn)。例.取n=12，a=7，则(12)=4，模12的一个简化剩余系为r1=1，r2=5，r3=7，r4=11，ari构成的简化剩余系为ar1=7，ar2=35，ar3=49，ar4=77。按照模12合同两个简化剩余系对应关系如下：ri：15711ari：7354977即77(mod12)3511(mod12)ar1…ar(12)r1…r(12)(mod12)。故，741(mod12)Note:由Fermat-Euler定理，知若a和m互质，则a(m)1(modm)。因此，若a和m互质，则ax1(modm)的一个解为a(m)-1，从而axb(modm)的一个解为ba(m)-1，即，若a和m互质，则axb(modm)存在解----用另一种方法证明解的存在性。求解一次合同方程的方法方法三:利用Fermat-Euler定理。例.解合同式7x5(mod10)。解：因为7和10互质，由Fermat-Euler定理有7(10)1(mod10)，因(10)=4，所以741(mod10)。由合同的性质7，在7x5(mod10)两边乘以73，有73×7x73×5(mod10)，而73×7x=74xx(mod10)，ba(m)-1=5×73=72×7×5（-1）×7×55(mod10)，所以所给合同式的解为x5(mod10)。补充习题1设p是一个奇质数，则（1）1p-1+2p-1+…+(p-1)p-1-1(modp)。（2）1p+2p+…+(p-1)p0(modp)。证明：（1）因为p为质数，故对于任意的1kp-1，k|p.由Fermat小定理Ⅰ知，有kp-11(modp)。因此，1p-1+2p-1+…+(p-1)p-11+1+…+1=p-1-1(modp)。（2）1p+2p+…+(p-1)p0(modp)。证明：由Fermat小定理Ⅱ知，对于任意的1kp-1，有kpk(modp)。故1p+2p+…+(p-1)p1+2+…+(p-1)p(p-1)/2(modp)。因为p是奇数，所以（p-1）/2是整数，故p(p-1)/20(modp)。因此，1p+2p+…+(p-1)pp(p-1)/20(modp)。2求7355的个位数（最后一位数）。解：求7355的个位数，只需求7355被10除的余数。因(10)=(2)(5)=4，7与10互质，由Fermat-Euler定理有：741（mod10），所以735574×88+3733（mod10）。因此，7355的个位数是3。3求7355的最后两位数。解：因100=2252，所以由定理5.4.6知，(100)=100×（1-1/2）（1-1/5）=40。又,7与100互质,于是,由Fermat-Euler定理有：7401（mod100），所以7355740×8+35735（mod100）。而741(mod100),故73574×8+37343(mod100)，即735543（m