《互质质因数分解课件》由会员分享，可在线阅读，更多相关《互质质因数分解课件（34页珍藏版）》请在金锄头文库上搜索。
1、5.2 互质互质 质因数分解质因数分解 5.2.1 整数互质整数互质 定义定义5.2.1 若若a，b除除1外无其它公因数，则外无其它公因数，则称称a和和b互质互质。结论：结论：1、a和和b互质，必要而且只要互质，必要而且只要a、b的最高公的最高公因数为因数为1(通常只考虑通常只考虑+1)。2、1和和任意任意整数整数(包括包括0)互质。互质。定理定理5.2.1 a和和b互质，当且仅当互质，当且仅当1可表示为可表示为a和和b的倍数的倍数和形式，即存在整数和形式，即存在整数s和和t使使1=sa+tb。 证明：证明：必要性必要性；由；由a和和b互质知，互质知，a和和b的最的最高公因数为高公因数为1，从
2、而根据定理，从而根据定理5.1.3，存在，存在s，t，使使sa+tb=1。充分性充分性；只需证：若存在；只需证：若存在s，t，使使sa+tb=1，则则a和和b的最高公因数的最高公因数d=(a,b)为为1。假设。假设d=(a,b) 1，则则d|a，d|b，从而从而d整除整除sa+tb=1的左端，因此的左端，因此d|1，矛盾。矛盾。 定理定理5.2.2 若若a和和b互质，而互质，而a bc，则则a c。证明：证明：因为因为a，b互质，故有互质，故有s，t使使1=sa+tb，从而从而c=sac+tbc (1)今因今因abc，a|ac，故故a整除整除(1)右边每一项，右边每一项，因而因而ac。 定理定
3、理5.2.3 若若b和和a1,a2,an都都互质，则互质，则b和和a1a2an互互质。质。证明：证明：由题设，对由题设，对i=1,2,n，有有si，ti使使sib+tiai=1把所有这把所有这n个式子乘起来，右边得个式子乘起来，右边得1，左边，左边有有2n项，其中有一项包含项，其中有一项包含a1a2an，而其余而其余各项都包含各项都包含b，所以，乘起来的式子如下：所以，乘起来的式子如下：S b+T a1a2an=1由定理由定理5.2.1得，得，b和和a1a2an二者互质。二者互质。 定理定理5.2.4若若m1,m2,mk两两互质而都整除两两互质而都整除a，则则m1m2mk|a。证明：证明：对对
4、k用数学归纳法。用数学归纳法。当当k=1时，结论显然。时，结论显然。当当k=2时，由于时，由于m1|a，所以存在整数所以存在整数q使得使得a=m1q。又又m2|a，即即m2|m1q，而而(m1, m2)=1，故故m2|q(定理定理5.2.2)，于是存在，于是存在p，使使q=m2p。从而从而a=m1m2p，即即 m1m2|a。 定理定理5.2.4假定对假定对i(1ik) 有有 m1m2mi|a (2)我们证明我们证明 m1m2mimi+1|a(3)由由(2)知有知有q使使 a=m1m2miq (4) 今今mi+1|a，且且由由定定理理5.2.3知知mi+1和和m1m2mi互互质质，故故由由定定理
5、理5.2.2，mi+1|q。据据此此及及(4)可可以以得得到到(3)成立。归纳证毕。成立。归纳证毕。 例例5.2.1试证相继三个整数之积能被试证相继三个整数之积能被6整除。整除。证明：证明：三个相继整数必有一个为偶数，且三个相继整数必有一个为偶数，且必有一个为必有一个为3的倍数，即的倍数，即2|n(n+1)(n+2)，3| n(n+1)(n+2)。而而(2，3)=1，故根据定理，故根据定理5.2.4有，有，6|n(n+1)(n+2)。 例例5.2.2试证相继三个整数的立方和是试证相继三个整数的立方和是9的倍数。的倍数。证明：证明：设设 n-1，n，n+1为三个相继整数，为三个相继整数，则则 (
6、n-1)3+n3+(n+1)3=3n3+3n2-3n2+6n-1+1 =3(n3+2n)=3(n3+3n-n)=3(3n+n(n2-1)=9n+3(n-1)n(n+1)而由上例而由上例5.2.1知知3|(n-1)n(n+1)，故故9|(n-1)3+n3+(n+1)3)。 例例5.2.3试证试证2p-1和和2q-1互质的充要条件是互质的充要条件是p和和q互质。互质。证明：必要性：证明：必要性：假若假若p和和q不互质，不互质，(p,q)=a 1，记记p=ap1，q=aq1，则则2p-1=2ap1-1，2q-1=2aq1-1。有公有公因数因数2a-1 1，矛盾。矛盾。充分性：充分性：已知已知 (p,
7、q)=1，设设(2p-1,2q-1)=d，往证往证d=1。不妨设不妨设 p q，辗转相除得辗转相除得 p=ql1+r1，q=r1l2+r2，rn-2=rn-1ln+rn，rn-1=rnln+1。由于由于(p,q)=1，故故rn=1。因为因为 2p-1=2ql1+r1-1 =2r1(2ql1-1)+2r1-1 =(2q-1)N+(2r1-1)，所所以，以，(2q-1,2r1-1)=d。同理推得同理推得 d=(2r1-1,2r2-1)= = 。 例例5.2.4若若(ai,bj) = 1，1 i n，1 j m，则则 (a1a2an,b1b2bm)=1。特别当特别当(a,b) = 1时，时，(an,
8、bm) = 1，n,m为任意正整数。为任意正整数。证明：证明：由由(ai,bj)=1， 1 j m ，得得( (ai, b1b2bm) )=1， 1 i n ，进而进而(a1a2an,b1b2bm) = 1。取取ai=a，bj=b，则则（an,bm）=1。 更正更正P161, 定理定理5.2.1中中“充分性充分性”证明的第二个证明的第二个sa+td=1(“从而从而d整除整除sa+td=1的左端的左端”),应该是应该是sa+tb=1.P161, 定理定理5.2.3中中“若若b和和a1, a2, , ak都互质都互质”的的ak应该是应该是an.P162, 例例5.2.3 倒数第二行最后倒数第二行最
9、后:改为改为例例5.2.5 设设a,b为大于为大于1的自然数，的自然数，b a，且且(a,b)=1，则则logab 是无理数。是无理数。证明：反证法。若不然，假设证明：反证法。若不然，假设logab=p/q为有理数。为有理数。因因b a，不妨设不妨设p，q是是正整数正整数，且（，且（p,q）=1。从而得从而得 ap/q=b，即即ap=bq。因为因为 (a,b)=1，由上例由上例5.2.4知知（ap,bq）=1，与与ap=bq矛矛盾。盾。 设设f(x)=anxn+an-1xn-1+a0是整系数多项式，是整系数多项式，若若10|f(2)，10|f(5)，则则10|f(10)。证明：证明：注意到注意
10、到 f(10) =an10n+an-110n-1+a1101+a0，所以所以10|f(10)当且仅当当且仅当10|a0。因为因为10|f(2)，所以所以2|f(2)，于是于是2|a0，同样同样5|a0。由（由（2，5）=1和定理和定理5.2.4得得10| a0。 例例5.2.6 5.2.2 质数与合数质数与合数算术基本定理算术基本定理 一个一个正整数正整数，如果，如果不等于不等于1而且除了自己而且除了自己和和1没有其它正因数，则称其为一个没有其它正因数，则称其为一个质数质数(也称为也称为素数素数)；否则称其为；否则称其为合数合数。 这样，正整数分为这样，正整数分为1, 质数，合数质数，合数 例
11、如：例如：2，3，5，7，11，都是质数。都是质数。1既不是质数也不是合数。既不是质数也不是合数。1之所以要摒于质之所以要摒于质数之外，是因为它完全没有质数所具备的数之外，是因为它完全没有质数所具备的那些重要的数论性质。那些重要的数论性质。 定义定义5.2.2结论：质数结论：质数p和和a互质，必要而且只要互质，必要而且只要p|a。充分性。充分性。若若p|a，则则p当然就不是当然就不是p,a的公因的公因数；数；而而p是质数，除了是质数，除了p，只有只有1才可能是才可能是p的的因数，因数，所以只有所以只有1才可能是才可能是p,a的公因数，即二者的公因数，即二者互质。互质。结论：任意两个不同的质数互
12、质。结论：任意两个不同的质数互质。 证明：必要性。证明：必要性。反证，若反证，若p|a，则则p和和a除除1外还有公因数外还有公因数p，故二者不互质，与二故二者不互质，与二者互质矛盾。者互质矛盾。设设p为质数为质数,若若p整除整除a1a2an，则则p整除整除a1，a2，an之一。之一。证明：反证。证明：反证。假若假若a1，a2，an都不能被都不能被质数质数p整除，则整除，则p和它们都互质，故由定理和它们都互质，故由定理5.2.3，p和它们的乘积互质，因而和它们的乘积互质，因而p将不能将不能整除此乘积整除此乘积a1a2an，矛盾。，矛盾。 定理定理5.2.5 任意任意正整数正整数n（n 1）恰有一
13、法恰有一法写成质数的写成质数的乘积（不计因数乘积的顺序）。乘积（不计因数乘积的顺序）。 证明：证明：先证先证n可以可以写成质数的乘积。写成质数的乘积。用数学归纳法，用数学归纳法， n=2时时, ,显然成立，因为显然成立，因为2是质数，算是已经写成了质数的乘积。是质数，算是已经写成了质数的乘积。假定假定na时时n可以写成质数的乘积，可以写成质数的乘积，试证试证n=a时也可以这样写。时也可以这样写。定理定理5.2.6 ( (算术基本定理算术基本定理) ) 若若a是质数，则是质数，则a算是已经写成了质数的乘算是已经写成了质数的乘积。积。若若a不是质数，于是，不是质数，于是，a有因数有因数b，1ba。
14、使使 a=bc，1ca。既然既然b和和c都都a，故由归故由归纳假定，纳假定，b和和c都可以写成质数的乘积。又都可以写成质数的乘积。又a=bc，只要把这两个乘积连接起来就把只要把这两个乘积连接起来就把a写写成了质数的乘积。归纳法已经完成，所以成了质数的乘积。归纳法已经完成，所以任意正整数任意正整数n（n 1）可以写成质数的乘积。可以写成质数的乘积。 再证再证n只有一法只有一法写成质数的乘积，写成质数的乘积，如果如果n=p1ph=q1qk (5)而而p1,ph，q1,qk都是质数，往证都是质数，往证h=k，而且而且p1,ph和和q1,qk完全一样，最多次序完全一样，最多次序不同。不同。由由(5)，
15、p1|q1qk，故由定理故由定理5.2.5，p1应整应整除除q1,qk之一，颠倒后者的次序，可假定之一，颠倒后者的次序，可假定p1|q1。今今q1是质数，只有是质数，只有q1和和1两个正因数，两个正因数，而而p1 1，故故p1必等于必等于q1。由由(5)消去消去p1而得而得p2ph=q2qk由此同上可证由此同上可证p2应整除应整除q2,qk之一。如此之一。如此类推，可见类推，可见p1,ph和和q1,qk完全一样，最完全一样，最多次序不一样。不可能一边已经消完而另多次序不一样。不可能一边已经消完而另一边还剩下质数，因为，那样则一个质数一边还剩下质数，因为，那样则一个质数或一些质数之积等于或一些质
16、数之积等于1，这不可能。，这不可能。 推论推论1 任意整数任意整数( 0， 1)恰好有一法写恰好有一法写成下面的形式：成下面的形式：p1pk (6)其中其中p1,pk都是质数。都是质数。推论推论2 任意整数任意整数( 0， 1)恰好有一法写恰好有一法写成下面的形式：成下面的形式：p1r1pnr n (7)其中其中p1, , ,pn是不同的质数，是不同的质数，r1,rn是正是正整数。整数。 定理定理5.2.6 ( (算术基本定理算术基本定理) ) Note：1 若若a 写成写成p1r1pnrn的形式，则的形式，则a有有 2(r1+1) (rn+1)个因数。个因数。2 若若a =p1r1pnrn，
17、 b =p1s1pnsn 其中其中r1,rn ，s1,sn是非负整数是非负整数, , p1,pn是不同的质数。是不同的质数。 则则a,b的最高公因为的最高公因为p1min(r1,s1)pnmin(rn,sn) a,b的最低公倍为的最低公倍为p1max(r1,s1)pnmax(rn,sn)质数无穷多。质数无穷多。证明：假定质数只有有限的几个，设为证明：假定质数只有有限的几个，设为p1, , pn。试看试看N=p1p2pn+1则则p1, , ,pn都不能整除都不能整除N，否则若否则若pi|N，则，则因因pi|p1p2pn，故故pi|1，与，与pi为为质数矛盾。质数矛盾。故故N无质因数，即无质因数，
18、即N为质数。而为质数。而N不同于不同于p1, , ,pn，与质数只有与质数只有p1, , ,pn矛盾。矛盾。 定理定理5.2.7（Euclid 欧几里得欧几里得 公元前三世纪）公元前三世纪）欧几里得（活动于约公元前欧几里得（活动于约公元前330）古希腊数学家，以所著的古希腊数学家，以所著的几何原本几何原本闻名于世。将公元前闻名于世。将公元前7世纪以来希腊几何积累起来的既丰富又纷纭庞杂的结果整世纪以来希腊几何积累起来的既丰富又纷纭庞杂的结果整理在一个严密统一的体系中，从最原始的定义开始，列出理在一个严密统一的体系中，从最原始的定义开始，列出5条公理和条公理和5条公设为基础通过逻辑推理，演绎出一系
19、列定条公设为基础通过逻辑推理，演绎出一系列定理和推论，从而建立了被称为欧几里得几何的第一个公理化理和推论，从而建立了被称为欧几里得几何的第一个公理化的数学体系。的数学体系。除了除了几何原本几何原本之外，还有不少著作，可惜大都失传。之外，还有不少著作，可惜大都失传。 已知数已知数是除是除原本原本之外惟一保存下来的希腊文纯粹几之外惟一保存下来的希腊文纯粹几何著作，包括何著作，包括94个命题个命题,指出若图形中某些元素已知指出若图形中某些元素已知,则另外则另外一些元素也可以确定。一些元素也可以确定。 图形的分割图形的分割现存拉丁文本与阿拉伯文本，论述用直线将现存拉丁文本与阿拉伯文本，论述用直线将已知
20、图形分为相等的部分或成比例的部分。已知图形分为相等的部分或成比例的部分。 光学光学是早期几何光学著作之一，研究透视问题，叙述光是早期几何光学著作之一，研究透视问题，叙述光的入射角等于反射角，认为视觉是眼睛发出光线到达物体的的入射角等于反射角，认为视觉是眼睛发出光线到达物体的结果。结果。关于他的生平，现在知道的很少。早年大概就学于雅关于他的生平，现在知道的很少。早年大概就学于雅典，深知柏拉图的学说。在托勒密王（公元前典，深知柏拉图的学说。在托勒密王（公元前364前前283）的邀请下，来到亚历山大，长期在那里工作。他）的邀请下，来到亚历山大，长期在那里工作。他是一位温良敦厚的教育家，对有志数学之士
21、，总是循是一位温良敦厚的教育家，对有志数学之士，总是循循善诱。但反对不肯刻苦钻研、投机取巧的作风，也循善诱。但反对不肯刻苦钻研、投机取巧的作风，也反对狭隘实用观点。反对狭隘实用观点。 据普罗克洛斯（约据普罗克洛斯（约410485）记载，托勒密王曾经问）记载，托勒密王曾经问欧几里得，除了他的欧几里得，除了他的几何原本几何原本之外，还有没有其之外，还有没有其它学习几何的捷径。欧几里得回答说：它学习几何的捷径。欧几里得回答说：“在几何里，在几何里，没有专为国王铺设的大道。没有专为国王铺设的大道。”这句话后来成为传诵千这句话后来成为传诵千古的学习箴言。古的学习箴言。 斯托贝乌斯（约斯托贝乌斯（约500
22、）记述了另一则故事）记述了另一则故事,说一个学生说一个学生才开始学第一个命题，就问学了几何学之后将得到些才开始学第一个命题，就问学了几何学之后将得到些什么。欧几里得说：给他三个钱币，因为他想在学习什么。欧几里得说：给他三个钱币，因为他想在学习中获取实利。中获取实利。1601年年8月月20日生於法国，日生於法国， 父亲是一个皮革商。父亲是一个皮革商。1665年年1月月12日逝世。日逝世。职业为律师职业为律师. 业余数学家：业余数学家： 近三十岁才开始认真专研近三十岁才开始认真专研 数学，但是他对数学的贡献数学，但是他对数学的贡献 使他赢得业余王子（使他赢得业余王子（the prince of a
23、mateurs）之美称。这个头）之美称。这个头衔正足以表彰他在数学领域的一级成就。衔正足以表彰他在数学领域的一级成就。在笛卡儿之前引进解析几何，而且在微积分的发展上有重大的在笛卡儿之前引进解析几何，而且在微积分的发展上有重大的贡献。贡献。和和Pascal被公认是概率论的先驱。被公认是概率论的先驱。用业余时间玩整数玩出了许多重要的结果。他很少有自己正式用业余时间玩整数玩出了许多重要的结果。他很少有自己正式的稿件和笔记，所得到的结果大多数都是在别人书或文章的边的稿件和笔记，所得到的结果大多数都是在别人书或文章的边角处。角处。 猜测几乎全被证实。猜测几乎全被证实。费马费马(Pierre de Fer
24、mat）错误猜测：错误猜测：形如形如Fn=的数必为质数。的数必为质数。形如形如Fn=的数称为的数称为Fermat素数。素数。 前五个数是前五个数是 F0=3，F1=5，F2=17，F3=257，F4=65537 都是都是质质数数 Euler举举出了出了F5=641 6700417非非质质数。数。 有趣的是到目前为止，人们再也没有找到第有趣的是到目前为止，人们再也没有找到第6个形如个形如 的数为质数，相反地，倒的数为质数，相反地，倒证明证明了了46个个这种数不这种数不为质数。因此，又有人为质数。因此，又有人猜测猜测Fermat素数仅有上述素数仅有上述5个，但这一点也未个，但这一点也未证实。证实。
25、 Fermat大定理大定理(约约1637年年,又称费马最后定理又称费马最后定理)是这样提出来的：在希腊数学家是这样提出来的：在希腊数学家Diophantos（丢番图）的文章底页上，在谈（丢番图）的文章底页上，在谈到整数解的勾股玄定理之后，到整数解的勾股玄定理之后，Fermat写着：写着：“相反地，要把一个立方数分为两个立方数，相反地，要把一个立方数分为两个立方数，一个四次方数分为两个四次方数，一般地，一个四次方数分为两个四次方数，一般地，把一个大于把一个大于2次方的乘方数分为同样指数的次方的乘方数分为同样指数的两个乘方数，都是不可能的；我确实发现了两个乘方数，都是不可能的；我确实发现了这个奇妙
26、的证明，因为这里的篇幅不够，我这个奇妙的证明，因为这里的篇幅不够，我不能写在这底页上。不能写在这底页上。”用一句简单的语言就用一句简单的语言就是：方程是：方程 xn+yn=zn，对于大于，对于大于0的整数的整数x，y，z，当，当n 2时无解。时无解。Euler证明了证明了n=3的情形，且对的情形，且对3的任何倍数成立的任何倍数成立-对无穷多个对无穷多个n值成立。值成立。 对任意对任意n是否成立，成为了当时世界上悬赏最是否成立，成为了当时世界上悬赏最高的难题。高的难题。 后来的数学家称这个问题的解决是一只能够下后来的数学家称这个问题的解决是一只能够下金蛋的鸡金蛋的鸡. Fermat大定理经过数学
27、家们大定理经过数学家们350多年的努力，于多年的努力，于1995年被英国数学家怀尔斯证明了，他因此荣年被英国数学家怀尔斯证明了，他因此荣获了沃尔夫奖。获了沃尔夫奖。怀尔斯：谨慎的屠龙者怀尔斯：谨慎的屠龙者因解决了因解决了350 年来悬而未决的费马大定律而闻名世界。年来悬而未决的费马大定律而闻名世界。 1953年年4 月月11日生于英国剑桥，日生于英国剑桥，1971年入牛津大学学习，年入牛津大学学习， 1980 年获该校博士学位。年获该校博士学位。在在10岁读贝尔的著作最后的难题，开始被费马大定岁读贝尔的著作最后的难题，开始被费马大定理迷住。曾一理迷住。曾一 度着手证明，但由于毫无进展而转向了度
28、着手证明，但由于毫无进展而转向了椭圆曲线问题。椭圆曲线问题。1986年，肯年，肯.里贝证明：里贝证明： 有一个尚未被证明的猜想，即有一个尚未被证明的猜想，即所谓的谷山所谓的谷山- 志村猜想，能够导出费马大定理，可要证志村猜想，能够导出费马大定理，可要证明这个猜想也决非易事。明这个猜想也决非易事。怀尔斯得知后，潜心怀尔斯得知后，潜心 7 年，终于在年，终于在1993年年6 月月23日上午日上午10点半左右在英国剑桥大学牛顿研究所，在连点半左右在英国剑桥大学牛顿研究所，在连 续三天续三天的讲演的最后，概述证明了谷山志村猜想的一大部分，的讲演的最后，概述证明了谷山志村猜想的一大部分，从而证明了费马从
29、而证明了费马 大定理。大定理。怀尔斯：谨慎的屠龙者怀尔斯：谨慎的屠龙者这一结论立刻震动了世界，有人称他为这一结论立刻震动了世界，有人称他为“ “世界的世界的屠龙者屠龙者” ”，尽管只有极少的数学家能够理解这个，尽管只有极少的数学家能够理解这个技术性很强的证明。但数月后，怀尔斯的证明逐技术性很强的证明。但数月后，怀尔斯的证明逐渐被发现有问题。渐被发现有问题。怀尔斯继续进行非常艰苦的多种证明尝试，在一怀尔斯继续进行非常艰苦的多种证明尝试，在一位同事的帮助下，位同事的帮助下，19941994年年9 9月怀尔斯最终完成了月怀尔斯最终完成了历史性长篇论文历史性长篇论文“ “模椭圆曲线和费马大定理模椭圆曲线和费马大定理” ”。论文于论文于19951995年发表在数学年刊上。怀尔斯年发表在数学年刊上。怀尔斯的论文迅速得到国际数学界的承认，他因此于的论文迅速得到国际数学界的承认，他因此于19961996年获得沃尔夫奖，成为最年轻的沃尔夫奖年获得沃尔夫奖，成为最年轻的沃尔夫奖获得者。获得者。 作业：习题作业：习题5.29,10
