离散数学ii(李占山)5-4秦九韶定理euler函数

§5.4 秦九韶定理

Euler函数

1精选课件ppt§5.4.1一次同余式组秦九韶定理定理5.4.1设[m1,m2]为m1，m2的最低公倍数。则同余式组

xa1(modm1)xa2(modm2)……………..(1)在mod[m1,m2]下有唯一解的充要条件为(m1,m2)|(a1-a2)……….(2)2精选课件ppt证明：必要性。记m1，m2的最高公因数和最低公倍数分别为d，m，即d=(m1,m2)，m=[m1,m2]。若(1)有解x0，则x0a1(modd)，x0a2(modd)，从而d|(a1-a2)。充分性。若d|(a1-a2)，往证(1)在模m下有唯一解。3精选课件ppt证明：因为xa1(modm1)解的形式为x=a1+m1y，代入(1)的二式中，得a1+m1ya2(modm2)，即m1ya2-a1(modm2)。于是(m1/d)y(a2-a1)/d(modm2/d)，且(m1/d,m2/d)=1。由上节的定理5.3.1知，关于模m2/d，y有唯一解y1。因此，x有解x1=a1+m1y1。若x’，x”都是(1)的解，则x’-x”0(modm1)，x’-x”0(modm2)。即

m1|(x’-x”)，m2|(x’-x”)。从而m|(x’-x”)，即

x’x”(mod[m1,m2])。

4精选课件ppt定理5.4.2(秦九韶定理)设m1,m2,…,mk两两互质。a1,a2,…,ak为k个整数，则下列同余式组有解，且在模m1m2…mk下解唯一：

xa1(modm1)，

xa2(modm2)，

..........，

xak(modmk)。(3)5精选课件ppt证明:先不讨论普遍情形而先求li，i=1,…,k，使适合下列特殊的合同式：

li1(modmi)，

li0(modmj)，ji (4)今ji时，mi和mj互质，故mi和互质，从而由上节定理5.3.1，有ci使6精选课件ppt证明:取，则li适合(4)。今取

x=a1l1+…+aklk(5)则模mi， ，故x适合(3)。

7精选课件ppt证明:现在证唯一性。若x，x都适合(3)，则x≡x(modmi)，i=1,…,k，故由§5.2定理5.2.4，x≡x(modm1…mk)使用了构造性证明方法，先构造一些满足局部合同式的局部解，再把这些局部解合起来构造成整体解。8精选课件ppt证明:这里的局部合同式就是(3)中每一个同余式，即构造yi，使得yi≡ai(modmi)，而yi对其余合同式无影响，即yi≡0(modmj)，ji。特别构造li使得(4)成立。若li已得到，则令yi=aili，于是yi满足

yi≡ai(modmi)

yi≡0(modmj)ji再令

x=y1+…+yk，则x为所求。

9精选课件ppt例5.4.1求x满足同余式组：

x≡1(mod4)

x≡2(mod5)

x≡3(mod7)解：因为模4，5，7两两互质，所以可以用上述定理的构造性证明过程求解。先求l1，l2，l3使得

10精选课件ppt例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=1105+256+3120=577≡17(mod140)。

11精选课件ppt§5.4.2一元高次同余式的化简

不讲12精选课件ppt§5.4.3 剩余系遍历Euler函数在(5)中，让a1经过modm1的一个完全剩余系变化，…，ak经过modmk的一个完全剩余系统变化，这样，我们共得到m1…mk个x。设x=a1l1+…+aklk，x

=a1l1+…+aklk。是两个这样的x

。13精选课件ppt§5.4.3 剩余系遍历Euler函数于是，

x

a1(modm1)

………………，

x

ak(modmk)；

x

a1(modm1)，

……，

x

ak(modmk)。所以，若a1,…,ak和a1,…,ak不全同，则

x

x

(modm1…mk)14精选课件ppt§5.4.3 剩余系遍历Euler函数这就是说，我们得到的m1…mk个xmodm1…mk

在不同的剩余类内，但modm1…mk只有m1…mk个剩余类，所以下面的定理成立。

15精选课件ppt定理5.4.4（遍历定理）

设m=m1…mk，而m1,…,mk两两互质。在(5)中，使a1,…,ak分别遍历modm1,…,

modmk的各一个完全剩余系，则x遍历modm的一个完全剩余系。

16精选课件pptEuler函数

设n是任意正整数，试看modn的任意剩余类A。设aA。若a和n互质，则A中任意数和n互质。此时我们称剩余类A和n互质。事实上，若ba(modn)，则a=b+qn，倘若b和n有一个大于1的公因数d，则d也是a的因数，因而是a和n的公因数，此为矛盾。可见，若A中有一个数和n互质，则其中所有的数都和n互质。故A中的数或者都和n互质，或者都和n不互质。

17精选课件pptEuler函数

和n互质的剩余类的个数记为(n)，称为Euler(欧拉)函数。从和n互质的每一个剩余类中取出一个数，这样得到的(n)个数便称之为作成modn的一个简化剩余系。显然，从modn的一个完全剩余系中取出与n互质的那些数就得到modn的一个简化剩余系，因而(n)等于n的正数中和n互质的数的个数。例如，n=10，则modn的一个完全剩余系为0，1，…，9，一个简化剩余系为1，3，7，9，(10)=4。

18精选课件ppt定理5.4.5设m=m1…mk，而m1,…,mk两两互质。则

(m)=(m1)(m2)…(mk) (9)这个结论实质是说在秦九韶定理证明中构造的

x=a1l1+…+aklk，若每个ai各自遍历modmi(i=1,…,k)的一个简化剩余系，则x遍历modm的一个简化剩余系。因为ai有(mi)个取法，所以得x有(m1)…(mk)个取法。

19精选课件ppt证明：设modmi的一个简化剩余系为Di(i=1,…,k)，modm的一个简化剩余系为D，我们证明：D1D2…Dk与D可以建立1-1映射。定义映射如下:

(a1,…,ak)

x=a1l1+…+aklk

对任意(a1,…,ak)D1D2…Dk，有ai与mi(i=1,…,k)互质，而x

ai(modmi)，从而有x与mi互质，i=1,…,k，由定理5.2.3，x和m互质。即是D1D2…Dk到Ｄ内的一个映射，由遍历定理知是单射。

20精选课件ppt证明：再证为满射，对任意xＤ，则由遍历定理知，存在a1,…,ak分别属于modm１，…，modmk的完全剩余系，使得x=a1l1+…+aklk

。下面证明(a1,…,ak)D1D2…Dk，由于x与m互质，所以x与mi互质。而xai(modmi)，因而ai与mi互质，即(a1,…,ak)D1D2…Dk。因此为1-1映射。于是D的元素个数与D1D2…Dk的元素数相同。注意到D1D2…Dk的元素数为(m1)…(mk)，Ｄ的元素数为(m)，故(m)＝(m1)…(mk)。21精选课件ppt定理5.4.6设

是n的质因数分解式，p1,…,pk都不同，于是22精选课件ppt证明：首先考虑最简单情形；n=p为质数，则(n)=p-1=p(1-1/p)，结论成立。其次考虑n=pr，p为质数，而求(pr)。一个数a和pr互质等于说a不是p的倍数。今在从1到pr的pr个数中，是p的倍数的共pr-1个，即 p，2p，…，pr-1p

因而和p互质的共pr-pr-1个，故

(n)=(pr)=pr-pr-1=pr结论成立。

23精选课件ppt证明：第三考虑一般情况，，p1,…,pk互不相同，则(pi,pj)=1(ij)。从而

。由定理5.4.5及上述第二中情形证明有

24精选课件ppt根据定理5.3.1：若(a,m)=1，则axb(modm)有唯一解。用另一种方法证明解的存在性，只需考虑ax1(modm)。因为若x0是ax1(modm)的解，则可得x0b为axb(modm)的解。设r1，…，r(m)

是modm的一个简化剩余系，则(ri,m)=1，i=1，…，(m)，从而(r1…r(m)，m)=1。25精选课件ppt再看ar1,…,ar(n)，因为(a,m)=1，所以(ari,m)=1。又因为rirj(modm)，所以ariarj(modm)(ij)。也就是说ar1，…,ar(m)

也作成modm的一个简化剩余系。从而这两个简化剩余系中的数关于modm合同可以建立一个1-1映射关系。因此，ar1…ar(m)r1…r(m)(modm)。而(r1…r(m)，m)=1，故消去率成立，于是a(m)1(modm)。ax1(modm)的一个解为a(m)-1，从而axb(modm)的一个解为ba(m)-1。26精选课件ppt若a和n互质，则a(n)1(modn)定理5.4.7(Fermat-Euler定理)推论1(Fermat小定理Ⅰ)若p是质数而p|a，则ap-11(modp)。推论2（Fermat小定理Ⅱ）若p为质数，则对任意整数a都有apa(modp)。

27精选课件ppt费马(PierredeFermat）费马是17世纪最重要的数学家之一,从职业上来说是为律师.他是历史上最著名的业余数学家.费马的数学发现发表的很少.我们从他与其他数学家的通讯中了解他的工作.费马是解析几何的发明者之一,并且发展了微积分的某些基础思想.费马和帕斯卡尔(Pascal)为概率论建立了数学基础.费马提出了最有名的数学问题.他断定在n大于2时,方程xn+yn=zn没有平凡的正整数解.300多年来没有找到证明(或反例),后来的数学家称这个问题的解决是一只能够下金蛋的鸡.若想知道问题的最终结果请看下一页:谨慎的屠龙者28精选课件ppt怀尔斯：谨慎的屠龙者怀尔斯：谨慎的屠龙者怀尔斯因解决了350年来悬而未决的费马大定律而闻名世界。怀尔斯1953年4月11日生于英国剑桥，1971年入牛津大学学习，1980年获该校博士学位。怀尔斯的一位导师认为他具有两个显著的数学禀赋，一是他优先于一切地要去证明困难的具体定理，而不愿去作优美的无所不包的猜想。；二是他有惊人的能力去吸收大量的极高深极抽象的机制，并在脚踏实地的问题中贯彻直到得出巨大的成果。费马大定理又称费马最后定理，是著名法国数学家费马在约1637年写下的一个猜想：对于任意大于2的整数n，不可能有非零的整数a，b，c满足.350多年很多数学家尝试过解决费马大定理，直到1993年终不能完全证明。怀尔斯在10岁读贝尔的著作《最后的难题》，开始被费马达定律迷住。曾一度着手证明，但由于毫无进展而转向了椭圆曲线问题。29精选课件ppt怀尔斯：谨慎的屠龙者1986年，肯.里贝证明：有一个尚未被证明的猜想，即所谓的谷山-志村猜想，能够导出费马大定理，可要证明这个猜想也决非易事。

1986年怀尔斯得知里贝的结果后，重新燃起了研究费马大定律的热情。潜心7年，终于在1993年6月23日上午10点半左右在英国剑桥大学牛顿研究所，在连续三天的讲演的最后，概述证明了谷山－志村猜想的一大部分，从而证明了费马大定理。这一结论立刻震动了世界，有人称他为“世界的屠龙者”，尽管只有极少的数学家能够理解这个技术性很强的证明。但数月后，怀尔斯的证明逐渐被发现有问题。。怀尔斯继续进行非常艰苦的多种证明尝试，在一位同事的帮助下，1994年9月怀尔斯最终完成了历史性长篇论文“模椭圆曲线和费马大定理”。论文于19995年发表在《数学年刊》上。怀尔斯的论文迅速得到国际数学界的承认，他因此于1996年获得沃尔夫奖，成为最年轻的沃尔夫奖获得者。30精选课件ppt习题利用Fermat-Euler定理（教材中定理5.4.7），见下例。解合同式7x5(mod10)。解：因为7和10互质，由Fermat-Euler定理有7(10)1(mod10)，因(10)=4，所以741(mod10)。由合同的性质7，在7x5(mod10)两边乘以73，有73×7x73×5(mod10)，而73×7x=74xx(mod10)，73×5=72×7×5（-1）×7×55(mod10)，所以所给合同式的解为x5(mod10)。31精选课件ppt习题设p是一个奇质数，则（1）1p-1+2p-1+…+(p-1)p-1-1(modp)。（2）1p+2p+…+(p-1)p0(modp)。（3）若2

m不合同于1模p，其中m是正整数，则1m+2m+…+(p-1)m0(modp)。证明：（1）因为p为质数，故对于任意的1kp-1，由Fermat小定理Ⅰ知，有kp-11(modp)。因此，1p-1+2p-1+…+(p-1)p-11+1+…+1=p-1-1(modp)。32精选课件ppt习题2）由Fermat小定理Ⅱ知，对于任意的1kp-1，有kpk(modp)。故1p+2p+…+(p-1)p1+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)。33精选课件ppt习题（3）因为p为奇数，所以2与p互质，故又由1，2，…，（p-1）是模p的简化剩余系知，2，4，6，…，2（p-1）也是模p的简化剩余系，它的每个数必与且只与1，2，…，（p-1）中的一个数关于模p同余。故由合同的性质知，2m+4m+…+[2(p-1)]m1m+2m+…+(p-1)m(modp)。故（2m-1）(1m+2m+…+(p-1)m)0(modp)。由已知，2

m不合同于1模p，故2

m-1不合同于