初等數(shù)論最大公因數(shù)演示文稿目前一頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)優(yōu)選初等數(shù)論最大公因數(shù)目前二頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)定義：若=1，則稱互素。若對(duì),則稱兩兩互素。顯然兩兩互素可推出互素，反之不行。例（2，3，4）=1，但（2，4）=2。下面主要討論兩個(gè)數(shù)的最大公因數(shù)的性質(zhì).目前三頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)性質(zhì)：1、=2、(0,b)=|b|,b≠0.3、(a,b)=(b,a)前3條比較簡(jiǎn)單.4、若a=bq+c，則（a，b）=（b，c）分析:(1)可證(a,b)和(b,c)相互整除.(2)利用集合知識(shí)說(shuō)明a,b和b,c的公因子集相同.目前四頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)證：設(shè)d是a，b的任一公因數(shù)，則有d|a，d|b，則有d|c=a-bq，說(shuō)明d也是b，c的公因數(shù)，反之設(shè)d是b，c的任一公因數(shù)，則d|b，d|c，則有d|a，說(shuō)明d也是a，b的公因數(shù)。所以a，b的全體公因數(shù)的集合就是b，c的全體公因數(shù)的集合。則最大的一個(gè)也相等即（a，b）=（b，c）注：這個(gè)性質(zhì)是后繼知識(shí)的基礎(chǔ)，很重要,因?yàn)閮蓚€(gè)較大的數(shù)的最大公因數(shù)可轉(zhuǎn)化為較小的兩個(gè)數(shù)的最大公因數(shù),從而為求大公因數(shù)找到了方法.目前五頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)為求兩個(gè)數(shù)的最大公因數(shù)，引進(jìn)輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法

：下面的一組帶余數(shù)除法稱為輾轉(zhuǎn)相除法。設(shè)a，b為正整數(shù)，依次做帶余除法目前六頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)5、a，b為整數(shù)，則（a，b）=即最后一個(gè)不為零的余數(shù)證：由性質(zhì)4知(a,b)=推論：a，b的公因數(shù)與（a，b）的因數(shù)相同。證：由輾轉(zhuǎn)相除法d|a，d|b，則有d|（a，b），反之也對(duì)目前七頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)例1、

求24871與3468的最大公因數(shù)解：24871=3468*7+595，3468=595*5+493，595=493*1+102，493=102*4+85，102=85*1+17，85=17*5,所以(24871,3468)=17.目前八頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)例2：求(21n+4，14n+3)解：原式=(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,7n+2)=(7n+1,1)=1目前九頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)6、m>0.則（am，bm）=m（a，b）證：由輾轉(zhuǎn)相除法兩邊同乘m即得。推論1：則證：只要c乘即得。推論2：證：取c=（a，b）即得推論2推論2給出了兩個(gè)整數(shù)的常用設(shè)法,即可設(shè)目前十頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)7、若(a,b)=1,則(ac,b)=(c,b)證：(ac,b)|ac,(ac,b)|bc,(ac,b)|(ac,bc)從而有(ac,b)|(a,b)c(a,b)|c又(ac,b)|b,(ac,b)|(b,c)。反之，(c,b)|ac,(c,b)|b(c,b)|(ac,b),注：證明兩個(gè)最大公因數(shù)相等，可用相互整除的方法目前十一頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)8、(a,b)=1,b|acb|c證：因?yàn)閎|ac,所以(ac,b)=|b|,由7知(ac,b)=(c,b)=|b|,即b|c.9、a|c,b|c,(a,b)=1,ab|c

證：由已知有又(a,b)=1,所以有,所以有ab|c.

目前十二頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)10、(a,c)=1,(b,c)=1,則有(ab,c)=1證：因?yàn)?a,c)=1,由性質(zhì)7有(ab,c)=(b,c)=1.11、若對(duì)i=1，2，..n;j=1,2,…m.有,則目前十三頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)證：因?yàn)閷?duì)任意的j有

1.目前十四頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)12、設(shè)(a,b)=d,則一定存在整數(shù)x,y使得ax+by=d證：由輾轉(zhuǎn)相除法倒過(guò)來(lái)即可得。因?yàn)?()a+()b令第一個(gè)括號(hào)里的數(shù)為x,第二個(gè)括號(hào)里的數(shù)為y,即得。目前十五頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)推論：(a,b)=1存在整數(shù)x,y使得ax+by=1證：顯然。設(shè)ax+by=1，又設(shè)d=(a,b)，則有d|a,d|b,有d|1,即d=1注:以上給出了證明(a,b)=1的一種常規(guī)方法.即先設(shè)d=(a,b)，然后證明d|1,即得d=1目前十六頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)下面我們給出n個(gè)整數(shù)的最大公因數(shù)的求法13、為n個(gè)整數(shù)，又設(shè)則有注：性質(zhì)13說(shuō)明了n個(gè)數(shù)的最大公因數(shù)可兩個(gè)兩個(gè)地求目前十七頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)證：由已知得說(shuō)明了是的公因數(shù)。又設(shè)d是的任一公因數(shù)，則有又有

這說(shuō)明了是的最大公因數(shù)。目前十八頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)例1：若17|2a+3b,試證17|9a+5b證：因?yàn)?*(9a+5b)=9(2a+3b)-17b,由已知，有17|2*（9a+5b)因?yàn)?17,2)=1,由性質(zhì)有17|9a+5b.目前十九頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)例2：設(shè)k為正奇數(shù)，試證證：設(shè),則則有,又所以又有即有9|2s,10|2s,由(9,10)=1,有90|2s.故目前二十頁(yè)\總數(shù)二十二頁(yè)\編于十九點(diǎn)例3：設(shè)n,a是正整數(shù)，試證若不是整數(shù)，則一定是無(wú)理數(shù).證：若是非整數(shù)的有理數(shù)，則可設(shè),,于是有因?yàn)?p,q)=1,所以有,但,所以有?所以假設(shè)錯(cuò)誤，若不是整