离散数学5-4秦九韶定理euler函数课件.ppt

1、定理5.4.1 设m1,m2为m1，m2的最低公倍数。则同余式组 xa1(mod m1)xa2(mod m2).(1)在modm1,m2下有唯一解的充要条件为(m1,m2)|(a1-a2).(2)必要性。记m1，m2的最高公因数和最低公倍数分别为d，m，即d=(m1,m2)，m=m1,m2。若(1)有解x0，则 x0a1(mod d)，x0a2(mod d)，从而d|(a1-a2)。充分性。若d|(a1-a2)，往证(1)在模m下有唯一解。因为xa1(mod m1)解的形式为 x=a1+m1y，代入(1)的二式中，得 a1+m1ya2(mod m2)，即 m1ya2-a1(mod m2)。于是

2、(m1/d)y(a2-a1)/d(mod m2/d)，且(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”)。从而m|(x-x”)，即 x x”(mod m1,m2)。(3)jijm)(mod1ijijimmcjijiimcliijjijijjiiaaalaxla01不讲在在(5)中，让中，让a1经过经过mod m1的一个完全剩余的一个完全剩余系变化，系变化，ak经过经过mod mk的一个完全剩的一个

3、完全剩余系统变化，这样，我们共得到余系统变化，这样，我们共得到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个剩余类，所以下面个剩余类，所以下面的定理成立。的定理成立。l设

4、 是n的质因数分解式，p1,pk都不同，于是)11).(11()(1kppnnkrkrppn.11首先考虑最简单情形；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结论成立。第三考虑一般情况，第三考虑一般情况，p1,pk互不相同，则互不相同，则(pi,pj)=1(i j)。从而从而 。由定理由定理5.4.5及上述第二及上述第二中情形证明有中情形证明有

5、 krkrppn.11)(1),(1jippjirjr)11).(11)(11()11().11()11()()()()(212211212121kkrkrrrkrrpppnpppppppppnkk根据定理5.3.1：若(a,m)=1，则 axb(mod m)有唯一解。用另一种方法证明解的存在性，只需考虑ax1(mod m)。因为若x0是ax1(mod m)的解，则可得x0b为 axb(mod m)的解。设r1，r(m)是mod m 的一个简化剩余系，则(ri,m)=1，i=1，(m)，从而(r1r(m)，m)=1。再看再看ar1,ar(n)，因为因为(a,m)=1，所以所以(ari,m)=1

6、。又因为又因为ri rj(mod m)，所以所以ari arj(mod m)(i j)。也就是说也就是说ar1，,ar(m)也作成也作成mod m 的一个简化剩余系。从而这的一个简化剩余系。从而这两个简化剩余系中的数关于两个简化剩余系中的数关于mod m合同可合同可以建立一个以建立一个1-1映射关系。因此，映射关系。因此，ar1ar(m)r1r(m)(mod m)。而而(r1r(m)，m)=1，故消去率成立，于是故消去率成立，于是a(m)1(mod m)。ax 1(mod m)的一个解为的一个解为a(m)-1，从而从而ax b(mod m)的一个解为的一个解为ba(m)-1。若若a和和n互质，

7、则互质，则a(n)1(mod n)推论推论1(Fermat小定理小定理)若若p是质数而是质数而p|a，则则ap-1 1(mod p)。推论推论2（Fermat小定理小定理）若若p为质数，则为质数，则对任意整数对任意整数a都有都有ap a(mod p)。l费马是费马是17世纪最重要的数学家之一世纪最重要的数学家之一,从职业上从职业上来说是为律师来说是为律师.他是历史上最著名的业余数学他是历史上最著名的业余数学家家.费马的数学发现发表的很少费马的数学发现发表的很少.我们从他与其我们从他与其他数学家的通讯中了解他的工作他数学家的通讯中了解他的工作.费马是解析费马是解析几何的发明者之一几何的发明者之一

8、,并且发展了微积分的某些并且发展了微积分的某些基础思想基础思想.费马和帕斯卡尔费马和帕斯卡尔(Pascal)为概率论建为概率论建立了数学基础立了数学基础.费马提出了最有名的数学问题费马提出了最有名的数学问题.他断定在他断定在n大于大于2时时,方程方程xn+yn=zn没有平凡的正没有平凡的正整数解整数解.300多年来没有找到证明多年来没有找到证明(或反例或反例),后来后来的数学家称这个问题的解决是一只能够下金蛋的数学家称这个问题的解决是一只能够下金蛋的鸡的鸡.若想知道问题的最终结果请看下一页若想知道问题的最终结果请看下一页:谨谨慎的屠龙者慎的屠龙者l怀尔斯：谨慎的屠龙者怀尔斯：谨慎的屠龙者 怀尔

9、斯因解决了怀尔斯因解决了350 350 年来悬而年来悬而未决的费马大定律而闻名世界。未决的费马大定律而闻名世界。怀尔斯怀尔斯19531953年年4 4 月月1111日生于英国剑桥，日生于英国剑桥，19711971年入牛津大学学习，年入牛津大学学习，1980 1980 年获年获 该校博士学位。怀尔斯的一位导师认为他具有两个显著该校博士学位。怀尔斯的一位导师认为他具有两个显著的数学禀赋，一是他优先的数学禀赋，一是他优先 于一切地要去证明困难的具于一切地要去证明困难的具体定理，而不愿去作优美的无所不包的猜想。；二是体定理，而不愿去作优美的无所不包的猜想。；二是 他有惊人的能力去吸收大量的极高深极抽象

10、的机制，并他有惊人的能力去吸收大量的极高深极抽象的机制，并在脚踏实地的问题中贯彻在脚踏实地的问题中贯彻 直到得出巨大的成果。直到得出巨大的成果。费马费马大定理又称费马最后定理，是著名法国数学家费马在约大定理又称费马最后定理，是著名法国数学家费马在约16371637年写下的一年写下的一 个猜想：对于任意大于个猜想：对于任意大于2 2 的整数的整数n n，不可能有非零的整数不可能有非零的整数 a a，b b，c c满足满足.350 .350 多年很多数学多年很多数学家尝试过解决费马大定理，直到家尝试过解决费马大定理，直到19931993年终不能完全证年终不能完全证明。明。怀尔斯在怀尔斯在1010岁

11、读贝尔的著作最后的难题，开岁读贝尔的著作最后的难题，开始被费马达定律迷住。曾一始被费马达定律迷住。曾一 度着手证明，但由于毫无度着手证明，但由于毫无进展而转向了椭圆曲线问题。进展而转向了椭圆曲线问题。l1986年，肯.里贝证明：有一个尚未被证明的猜想，即所谓的谷山-志村猜想，能够导出费马大定理，可要证明这个猜想也决非易事。1986年怀尔斯得知里贝的结果后，重新燃起了研究费马大定律的热情。潜心 7 年，终于在1993年6 月23日上午10点半左右在英国剑桥大学牛顿研究所，在连 续三天的讲演的最后，概述证明了谷山志村猜想的一大部分，从而证明了费马 大定理。这一结论立刻震动了世界，有人称他为“世界的

12、屠龙者”，尽管只有极 少的数学家能够理解这个技术性很强的证明。但数月后，怀尔斯的证明逐渐被发现有问题。怀尔斯继续进行非常艰苦的 多种证明尝试，在一位同事的帮助下，1994年9 月怀尔斯最终完成了历史性长篇 论文“模椭圆曲线和费马大定理”。论文于19995 年发表在数学年刊上。怀 尔斯的论文迅速得到国际数学界的承认，他因此于1996年获得沃尔夫奖，成为最 年轻的沃尔夫奖获得者。l利用Fermat-Euler定理（教材中定理5.4.7），见下例。l解合同式7x5(mod 10)。l解：因为7和10互质，由Fermat-Euler定理有l7(10)1(mod 10)，l因(10)=4，所以741(m

13、od 10)。由合同的性质7，在7x5(mod 10)两边乘以73，有l737x735(mod 10)，l而l737x=74 x x(mod 10)，l735=7275（-1）75 5(mod 10)，l所以所给合同式的解为x 5(mod 10)。l 设p是一个奇质数，则l（1）1p-1+2 p-1+(p-1)p-1 -1(mod p)。l（2）1p+2 p+(p-1)p 0(mod p)。l（3）若2 m不合同于1模p，其中m是正整数，则l1m+2m+(p-1)m 0(mod p)。l证明：（1）因为p为质数，故对于任意的1kp-1，由Fermat小定理知，有lk p-1 1(mod p)。

14、l因此，l1p-1+2 p-1+(p-1)p-1 1+1+1=p-1-1(mod p)。l2）由Fermat小定理知，对于任意的1kp-1，有lk p k(mod p)。l故l1p+2 p+(p-1)p1+2+(p-1)p(p-1)/2(mod p)。l因为p是奇数，所以（p-1）/2是整数，故lp(p-1)/2 0(mod p)。l因此，1p+2 p+(p-1)p p(p-1)/2 0(mod p)。l（3）因为p为奇数，所以2与p互质，故又由1，2，（p-1）是模p的简化剩余系知，2，4，6，2（p-1）也是模p的简化剩余系，它的每个数必与且只与1，2，（p-1）中的一个数关于模p同余。故

15、由合同的性质知，l2m+4m+2(p-1)m 1m+2m+(p-1)m(mod p)。l故l（2m-1）(1m+2m+(p-1)m)0(mod p)。l由已知，2 m不合同于1模p，故2 m-1不合同于0模p，又因为p为质数，由教材中合同的性质12知，1m+2m+(p-1)m0(mod p)。l（1）求（12371170+34）28被243除的余数。l（2）求7355的个位数（最后一位数）。l解：l（1）因243=35，所以由定理5.4.6知，l(243)=243（1-）=162。l又12371221（mod 243）-2（mod 243），221与243互质，于是，由Fermat-Euler

16、定理有：l2211621（mod 243），l即123711621（mod 243）。l所以，l12371170123718l （123712）4l （-22）2）4l （-2）4l 16（mod 243），l因此，（12371170+34）28（16+34）285028（mod 243）。l而50270（mod 243），50440（mod 243），508142（mod 243），5016-5（mod 243），于是，l502840142（-5）115（mod 243）。l故（12371170+34）28被243除的余数为115。l（2）求7355的个位数，只需求7355被10除的余数。因(10)=(2)(5)=4，7与10互质，由Fermat-Euler定理有：l741（mod 10），l所以l73557488+3733（mod 10）。l因此，7355的个位数是3。