5.4 秦九韶定理秦九韶定理 Euler函数函数 5.4.1 一次同余式组一次同余式组 秦九韶定理秦九韶定理 定理定理5.4.1 设设m1,m2为为m1，m2的最低公倍数。则的最低公倍数。则同余式组同余式组 x a1 (mod m1) x a2 (mod m2) .(1)在在modm1,m2下有唯一解的充要条件为下有唯一解的充要条件为 (m1,m2)|(a1-a2) .(2) Note:当此定理中的当此定理中的(m1,m2)=1这种特殊情况种特殊情况时，则（1）有关于模）有关于模m1m2唯一解。推广此特殊情形即得到中唯一解。推广此特殊情形即得到中国剩余定理，也称国剩余定理，也称为孙子定理。后子定理。后经过秦九韶整理和解秦九韶整理和解法的推广，我法的推广，我们这里称之里称之为秦九韶定理。秦九韶定理。 证明：证明：必要性必要性。记记m1，m2的最高公因数和最低公的最高公因数和最低公倍数分别为倍数分别为d，m，即即d=(m1,m2)，m=m1,m2。若若(1)有解有解x0，则则 x0 a1(mod d)，x0 a2(mod d)，从而从而d|(a1-a2)。充分性充分性。若若d|(a1-a2)，往证往证(1)在模在模m下有唯下有唯一解。一解。证明：证明：存在性存在性. 因为因为x a1(mod m1)解的形式为解的形式为 x=a1+m1y，代入代入(1)的二式中，得的二式中，得a1+m1y a2(mod m2)，即即 m1y a2-a1 (mod m2)。 由由d=(m1,m2),知，知，d| m1, d| m2, 再由再由 d|(a1-a2)，及性质及性质9知，知，(m1/d)y (a2-a1)/d (mod m2/d)，由由d=(m1,m2),知，知，(m1/d,m2/d)=1，由上节的定理由上节的定理5.3.1知，关于模知，关于模m2/d，y有唯一解有唯一解y1。因因此，此，x有解有解 x1=a1+m1y1。唯一性唯一性. .若若x，x”都是都是(1)的解，则的解，则 x-x” 0(mod m1)，x-x” 0(mod m2)。即即 m1|(x-x”)，m2|(x-x”)， 亦即，亦即，x-x”为为m1和和m2的公倍，而的公倍，而m为为m1和和m2的最的最小公倍，故小公倍，故m|(x-x”)，即即 x x”(mod m1,m2)。定理定理5.4.2(秦九韶定理秦九韶定理) 设设m1, m2 , , mk两两互质。两两互质。a1, a2, , ak为为k个整数，则下列同余式组有解，且在个整数，则下列同余式组有解，且在模模m1 m2 mk下解唯一：下解唯一：x a1(mod m1)，x a2(mod m2)，. . .， x ak(mod mk)。 (3)证明证明 :存在性存在性. 先不讨论普遍情形而先求先不讨论普遍情形而先求li，i=1,k，使适合下列特殊的合同式：使适合下列特殊的合同式： li 1(mod mi)， li 0(mod mj)，j i (4)因因j i时时，mi和和mj互互质质，由由定定理理5.2.3知知，mi和和 互质，从而由定理互质，从而由定理5.3.1，有，有ci使使证明证明 :取取 ，则则li适合适合(4)。今取。今取x=a1l1+aklk (5)则模则模mi， ，故故x适合适合(3)。 证明证明 :唯一性唯一性. 若若x，x 都适合都适合(3)，则，则xx (mod mi)，i=1,k，即即mi| x-x ，再由，再由m1, m2 , , mk两两互质，两两互质，及定理及定理5.2.4，得，得m1m2 mk | x-x 故故xx (mod m1mk)Note:证明过程使用了构造性证明方法，先构证明过程使用了构造性证明方法，先构造一些满足局部合同式的局部解，再把这些造一些满足局部合同式的局部解，再把这些局部解合起来构造成整体解。局部解合起来构造成整体解。（1）对）对i=1,k解合同方程解合同方程求出求出Ci。（2）（3） x=a1l1+aklk 例例5.4.1求求x满足同余式组：满足同余式组：x1(mod 4)x2(mod 5)x3(mod 7) 解：解：因为模因为模4，5，7两两互质，所以可以用两两互质，所以可以用上述定理的构造性证明过程求解。先求上述定理的构造性证明过程求解。先求l1，l2，l3使得使得 例例5.4.1l11(mod 4) l21(mod 5) l31(mod 7) l10(mod 5)l20(mod 4)l30(mod 4) l10(mod 7) l20(mod 7) l30(mod 5) 得得l1=35c1，l2=28c2，l3=20c3，c1满足满足35c11(mod 4)，即即 3c11(mod 4)，从而从而 c13(mod 4)。故故l1=105。同理得同理得l2=56， l3=120。于是于是 x=1 105+2 56+3 120=57717(mod 140)。 南宋数学家南宋数学家 秦九韶（公元秦九韶（公元12021261年）年）1247年，著成年，著成数书九章数书九章十八卷，这是一部十八卷，这是一部划时代的巨著，它总结了前人在开方中所使用划时代的巨著，它总结了前人在开方中所使用的方法，将其整齐而有系统地应用到高次方程的方法，将其整齐而有系统地应用到高次方程的有理或无理根的求解上去。的有理或无理根的求解上去。秦九韶给出了解一次同余式组的一般方法以及秦九韶给出了解一次同余式组的一般方法以及理论上的证明，并将它定名为理论上的证明，并将它定名为“大衍求一术大衍求一术”，在世界数学史上占有崇高的地位。，在世界数学史上占有崇高的地位。对正负开方术对正负开方术高次方程的数值解法）等高次方程的数值解法）等也有十分深入的研究。也有十分深入的研究。定定理理5.4.3 设设f(x)是是整整系系数数多多项项式式,m=p1r1p2r2pnrn 为为m的质因数分解式，则同余式的质因数分解式，则同余式 f(x) 0(mod m) (6)与下述同余式组等价与下述同余式组等价 f(x) 0(mod p1r1) (7) f(x) 0(mod pnrn ) 证明：证明：（6）的解显然是（）的解显然是（7）的解。）的解。 反反之之，若若x1是是（7）的的解解，则则 piri|f(x1)。注注意意到到p1r1，p2r2，pnrn 两两两两互互质质，故故 p1r1p2r2pnrn|f(x1)，即即m|f(x1)。因此因此 f(x1)0(mod m)，即，即x1是（是（6）的解。）的解。5.4.2 一元高次同余式的化简一元高次同余式的化简 当求解的同余式模较大且是合数时，可以将原同余式转当求解的同余式模较大且是合数时，可以将原同余式转化为模较小的同余式组进行求解。化为模较小的同余式组进行求解。例例5.4.2 求解同余式求解同余式 37x55(mod 60) 解：注意到（解：注意到（37，60）=1，故完全可以用上节的定理，故完全可以用上节的定理5.3.1证明和辗转相除法求解。这里用同余式组来求解。因为证明和辗转相除法求解。这里用同余式组来求解。因为60=22 3 5，所以原同余式等价于，所以原同余式等价于37x55(mod 4) 37x55(mod 3) 37x55(mod 5)等价化简同余式组得等价化简同余式组得x3(mod 4) x1(mod 3) 2x0(mod 5)又因为（又因为（2，5）=1，所以又等价于，所以又等价于x3(mod 4) x1(mod 3) x0(mod 5)解此同余式组得解此同余式组得 x55(mod 60)秦九韶定理本身是解一种最简单的同余式组，较一般的秦九韶定理本身是解一种最简单的同余式组，较一般的情况是情况是f1(x)0(mod m1) (8) fk(x)0(mod mk)其中其中m1，mk两两互质，两两互质，fi (i=1, , k)为整系数多项为整系数多项式。假若（式。假若（8）中第）中第i个同余式有解个同余式有解ai，则（，则（8）式的求解）式的求解就转化为一系列下述形式的同余式组的求解：就转化为一系列下述形式的同余式组的求解：xa1 (mod m1) xak (mod mk) 因此，秦九韶定理即是求解最简单的同余式组的方法，因此，秦九韶定理即是求解最简单的同余式组的方法，也是解高次同余式组的基础。也是解高次同余式组的基础。5.4.3 剩余系遍历剩余系遍历 Euler函数函数在在x=a1l1+aklk 中，让中，让a1经过经过mod m1的的一个完全剩余系变化，一个完全剩余系变化，ak经过经过mod mk的一个完全剩余系统变化，这样，我们共的一个完全剩余系统变化，这样，我们共得到得到m1mk个个x 。设设x =a1 l1+ak lk，x =a1 l1+ak lk。是两个这样的是两个这样的x 。于是，于是， x a 1(mod m1)，x a k (mod mk)；x a1 (mod m1)，x a k (mod mk)。所以，若所以，若a1 ,ak 和和a1 , , ak 不全同，则不全同，则x x (mod m1m k)这就是说，我们得到的这就是说，我们得到的m1mk个个x mod m1m k 在不同的剩余类内，但在不同的剩余类内，但mod m1mk只有只有m1mk个剩余类，所以下面个剩余类，所以下面的定理成立。的定理成立。 定理定理5.4.4（遍历定理）（遍历定理） 设设m=m1mk，而而m1, , ,mk两两互质。在两两互质。在x=a1l1+aklk中，使中，使a1, , ,ak分别遍历分别遍历mod m1 , , ,mod mk的各一个完全剩余系，则的各一个完全剩余系，则x遍历遍历mod m的一个完全剩余系。的一个完全剩余系。结论：结论：设设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，即，即d|b,d|n，故，故d|b+qn，即即d|a。因此，因此，d为为a,n的公因数，且的公因数，且d1，这与，这与a和和n互质矛盾。互质矛盾。Euler函数函数可见，若可见，若A中有一个数和中有一个数和n互质，则其中互质，则其中所有的数都和所有的数都和n互质。故互质。故A 中的数或者都和中的数或者都和n互质，或者都和互质，或者都和n不互质。不互质。 例例.mod 6 2，8，16 ，,与与6都不互质。都不互质。 5，11，17，,与与6都互质。都互质。 定义定义.设设A 为为mod n的一个剩余类，若对的一个剩余类，若对a A，a与与n互质，则称互质，则称剩余类剩余类A与与n互质互质。Euler函数函数Euler函数函数 定义定义定义定义 和和和和n n互质的剩余类的个数称为互质的剩余类的个数称为互质的剩余类的个数称为互质的剩余类的个数称为Euler(Euler(欧拉欧拉欧拉欧拉) )函数函数函数函数, ,记记记记为为为为 ( (n)n)。定义定义定义定义 从和从和从和从和n n互质的每一个剩余类中取出一个数，这样互质的每一个剩余类中取出一个数，这样互质的每一个剩余类中取出一个数，这样互质的每一个剩余类中取出一个数，这样得到的得到的得到的得到的 ( (n)n)个数称之为作成个数称之为作成个数称之为作成个数称之为作成mod nmod n的一个的一个的一个的一个简化剩余系简化剩余系简化剩余系简化剩余系。显显显显然然然然，从从从从mod mod n n的的的的一一一一个个个个非非非非负负负负最最最最小小小小完完完完全全全全剩剩剩剩余余余余系系系系中中中中取取取取出出出出与与与与n n互互互互质质质质的的的的那那那那些些些些数数数数, ,就就就就得得得得到到到到mod mod n n的的的的一一一一个个个个简简简简化化化化剩剩剩剩余余余余系系系系，因因因因而而而而 ( (n)n)等于等于等于等于 n n的正数中和的正数中和的正数中和的正数中和n n互质的数的个数。互质的数的个数。互质的数的个数。互质的数的个数。例例 n=10，则则mod n的一个完全剩余系为的一个完全剩余系为0，1，9，一个简化剩余系为，一个简化剩余系为1，3，7，9， (10)=4。 例例 n=12，则则mod n的一个完全剩余系为的一个完全剩余系为0，1，11，一个简化剩余系为，一个简化剩余系为1，5，7，11， (12)=4。 如何求如何求Euler函数函数 定理定理5.4.5 设设m=m1mk，而而m1, , mk两两互质。则两两互质。则 (m)= (m1) (m2) (mk) (9)例例. (2646)= (22749) = (2) (27) (49)证明：证明：设设mod mi的一个简化剩余系为的一个简化剩余系为Di (i=1, , k)，mod m的一个简化剩余系为的一个简化剩余系为D，我们我们证明：证明：D1 D2 Dk与与D可以建立可以建立1-1映射。映射。 定义映射定义映射 如下如下:(a1,ak) x= a1l1+aklk 对任意对任意(a1,ak) D1 D2 Dk，有有ai与与mi (i=1, , k)互质，而互质，而x ai (mod mi)，从而从而有有x与与mi互质，互质，i=1, , k，由定理由定理5.2.3， x和和m互质。即互质。即 是是D1 D2 Dk到内的一到内的一个映射个映射，由遍历定理知，由遍历定理知 是单射是单射。 证明：证明：再证再证 为满射为满射，对任意，对任意x ，则由遍历定理知，则由遍历定理知，存在存在a1,ak分别属于分别属于mod m，mod mk的的完全剩余系，使得完全剩余系，使得x= a1l1+aklk 。下面证明下面证明(a1,ak) D1 D2 Dk，由于由于x与与m互质，所以互质，所以x与与mi互质。而互质。而x ai (mod mi)，因而因而ai与与mi互质，互质，即即(a1,ak) D1 D2 Dk。因此因此 为为1-1映射。映射。于是于是D的元素个数与的元素个数与D1 D2 Dk的元素数相同。的元素数相同。注意到注意到D1 D2 Dk的元素数为的元素数为 (m1) (mk)，的元素数为的元素数为 (m)，故故 (m) (m1) (mk)。下面方法更好下面方法更好 定理定理5.4.6 设设 是是n的的质质因因数数分分解解式式，p1, , pk都不同，于是都不同，于是例例 (2646)= (23372) = 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及上述第二种及上述第二种情形证明有情形证明有 定理定理5.4.7(Fermat-Euler定理定理,Euler1760年提出年提出) 若若a和和n互质，则互质，则a (n) 1(mod n)（证明见下页）（证明见下页）例：例：a=3,n=10,3与与10互质互质, (10)=4,则则34 1(mod 10) a=5,n=12,5与与12互质互质, (12)=4,则则54 1(mod 12) 推论推论1(Fermat小定理小定理) 若若p是质数而是质数而p| a，则则ap-1 1(mod p)。-1640年年Fermat提出提出,1736年年Euler证明证明推论推论2（Fermat小定理小定理） 若若p为质数，则对任意整数为质数，则对任意整数a,都有都有ap a(mod p)。 例例:p=3, 23-1 1(mod 3) 23 2(mod 3) Fermat-Euler定理定理 若若a和和n互质，则互质，则a (n) 1(mod n)证明：证明：设设r1，r (n) 是是mod n 的一个简化剩余系，则的一个简化剩余系，则 (ri, n)=1，i=1， (n)，从而从而(r1r (n)，n)=1。再看再看ar1,ar (n)(1)当当ij时，往证时，往证ari arj(mod n) 。 反证。若反证。若ari arj(mod n)，则因，则因a和和n互质，得互质，得ri rj(mod n)，矛盾。矛盾。(2)往证往证ari一定属于某简化剩余类，一定属于某简化剩余类， i=1， (n)。 因为因为(a, n)=1， (ri, n)=1，所以所以(ari, n)=1。必有必有r1，r (n) 中某中某个个r j，使得，使得ari rj (mod n)。因此，因此，ar1，,ar (n) 也作成也作成mod n 的一个简化剩余系（即是说，如的一个简化剩余系（即是说，如果把剩余类中元素看成同一个元素的话，果把剩余类中元素看成同一个元素的话， ar1,ar (n)是是r1，r (n)的的一个重新排列一个重新排列）。因此，）。因此，ar1ar (n) r1r (n) (mod n)。而而(r1r (n)，n)=1，故消去律成立，于是故消去律成立，于是a (n) 1(mod n)。例例. 取取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 ： 1 5 7 11 ari ： 7 35 49 77即即 7 7 (mod 12) 35 11(mod 12)ar1ar (12) r1r (12) (mod 12)。故，故，74 1(mod 12) Note:由由Fermat-Euler定理，知若定理，知若a和和m互质，互质，则则a (m) 1(mod m) 。 因此，若因此，若a和和m互质，互质， 则则ax 1 (mod m)的的一个解为一个解为a (m)-1，从而从而ax b (mod m)的一的一个解为个解为ba (m)-1，即，若，即，若 a和和m互质互质，则则 ax b (mod m)存在解存在解-用另一种方法证用另一种方法证明解的存在性明解的存在性。 求解一次合同方程的方法求解一次合同方程的方法方法三方法三:利用利用Fermat-Euler定理。定理。例例. 解合同式解合同式7x 5(mod 10)。解：因为解：因为7和和10互质，由互质，由Fermat-Euler定理有定理有7 (10) 1(mod 10)，因因 (10)=4，所以，所以74 1(mod 10)。由合同的性质由合同的性质7，在在7x 5(mod 10)两边乘以两边乘以73，有，有737x 735(mod 10)，而而737x=74 x x(mod 10)，ba (m)-1 =573=7275 （-1）75 5(mod 10)，所以所给合同式的解为所以所给合同式的解为x 5(mod 10)。补充习题补充习题1 设设p是一个奇质数，则是一个奇质数，则（1）1p-1+2 p-1+(p-1) p-1 -1(mod p)。（2）1p+2 p+(p-1) p 0(mod p)。证明：证明：（1）因因为为p为为质质数数，故故对对于于任任意意的的1 k p-1，k|p. 由由 Fermat小定理小定理知，有知，有k p-1 1(mod p)。因此，因此，1p-1+2 p-1+(p-1) p-1 1+1+1=p-1 -1(mod p)。 （2）1p+2 p+(p-1) p 0(mod p)。证明：证明：由由Fermat小定理小定理知，知， 对于任意的对于任意的1 k p-1，有有k p k(mod p)。故故1p+2 p+(p-1) p 1+2 +(p-1) p(p-1)/2 (mod p)。因为因为p是奇数，所以（是奇数，所以（p-1）/2是整数，故是整数，故p(p-1)/2 0 (mod p)。因此，因此，1p+2 p+(p-1) p p(p-1)/2 0(mod p)。2 求求7355的个位数（最后一位数）。的个位数（最后一位数）。解解：求求7355的的个个位位数数，只只需需求求7355被被10除除的的余余数数。因因 (10)= (2) (5)=4，7与与10互质，由互质，由 Fermat-Euler定理有：定理有：74 1（mod 10），），所以所以7355 7488+3 14*8873 3（mod 10）。）。因此，因此，7355的个位数是的个位数是3。3 求求7355的最后两位数。的最后两位数。解：解：因因100=2252，所以由定理，所以由定理5.4.6知，知， (100)=100（1-1/2）（）（1-1/5）=40。又又,7与与100互质互质,于是于是,由由Fermat-Euler定理有：定理有：740 1（mod 100），），所以所以7355 7408+35 735（mod 100）。）。而而74 1(mod 100),故故735 748+3 73 43(mod 100)，即即 7355 43（mod 100）。）。因此，因此，7355的最后两位数是的最后两位数是43。4 求求243402的最后三位数。的最后三位数。解：解：因因1000=2353，所以由定理，所以由定理5.4.6知，知， (1000)=1000（1-1/2）（）（1-1/5）=400。又，又，243与与1000互质，于是，由互质，于是，由Fermat-Euler定理定理有：有：243400 1（mod 1000），），所以所以243402 2432 49（mod 1000）。）。因此，因此，243402的最后三位数是的最后三位数是049。 5 今天是星期一，今天是星期一， 天后是星期几天后是星期几?解：解：需要求出需要求出 (mod 7) ? 7是质数，是质数，7 |10，由，由Fermat小定理小定理知知, 106 1(mod 7)，另外，由另外，由10 4(mod 6)有有102 4(mod 6)，104 4(mod 6)， 108 4(mod 6)，故，故 1010 4(mod 6)。所以。所以1010=6N+4，即，即 (mod 7)= 106N+4 (mod 7) = 106N104(mod 7) 104(mod 7)由由10 3(mod 7)有有 102 2(mod 7)，104 4(mod 7)，所以所以 (mod 7)=4，即，即 天后是星期五。天后是星期五。作业：习题作业：习题5.41,2