初等數(shù)論最大公因數(shù)

1、 2 最大公因數(shù)定義1：n( )個(gè)不全為零的整數(shù) 的公共約數(shù)稱為 的公約數(shù).公約數(shù)中最大的一個(gè)稱為 的最大公約數(shù)。記成 最大公因數(shù)是數(shù)論中一個(gè)很重要的概念), 2 , 1( ,niai),(21naaa2n), 2 , 1(niai), 2 , 1(niai定義：若 =1，則稱 互素。 若對(duì) ,則稱 兩兩互素。顯然兩兩互素可推出互素，反之不行。例（2，3，4）=1，但（2，4）=2。下面主要討論兩個(gè)數(shù)的最大公因數(shù)的性質(zhì).),(21naaanaaa,211),(,jiaaji有naaa,21性質(zhì)：1、 =2、(0,b)=|b|, b0.3、(a,b)=(b,a) 前3條比較簡(jiǎn)單.4、若a=bq+

2、c，則（a，b）=（b，c）分析: (1)可證(a,b) 和(b,c)相互整除.(2)利用集合知識(shí)說(shuō)明a,b和b,c的公因子集相同.),(21naaa|)|,| |,(|21naaa證：設(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ù)找到了方法.為求

3、兩個(gè)數(shù)的最大公因數(shù)，引進(jìn)輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法 ：下面的一組帶余數(shù)除法稱為輾轉(zhuǎn)相除法。 設(shè)a，b為正整數(shù)，依次做帶余除法,11rbqa,221rqrbnnnnrqrr12br 10120rr 10nnrr111nnnnrqrr01nr5、a，b為整數(shù)，則（a，b）= 即最后一個(gè)不為零的余數(shù)證：由性質(zhì)4知(a,b)=nrnnnnrrrrrrrb)0 ,(),(),(),(1211推論：a，b的公因數(shù)與（a，b）的因數(shù)相同。證：由輾轉(zhuǎn)相除法 d|a，d|b，則有d|（a，b）， 反之也對(duì)例1、 求24871與3468的最大公因數(shù)解： 24871=3468*7+595，3468=595*5+493，5

4、95=493*1+102，493=102*4+85，102=85*1+17，85=17*5,所以(24871,3468)=17.例2：求(21n+4，14n+3)解：原式=(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,7n+2)=(7n+1,1)=16、m0.則（am，bm）=m（a，b）證：由輾轉(zhuǎn)相除法兩邊同乘m即得。推論1： 則 證：只要c乘 即得 。推論2：證：取c=（a，b）即得推論2推論2給出了兩個(gè)整數(shù)的常用設(shè)法,即可設(shè),|,|, 0bcacc cbacbca),(),(1),(),(),(babbaa),(cbcacba),(1),(),(,1111babadd

5、bbdaa7、若(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ù)相等，可用相互整除的方法8、(a,b)=1, b|ac b|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,所以有 ,所以有 a

6、b|c.2121,bcacbccacc2|bca2|ca32acc 32abcbcc 10、(a,c)=1, (b,c)=1, 則有 (a b,c)=1證：因?yàn)?a,c)=1,由性質(zhì)7有 (a b,c)=(b,c)=1.11、若對(duì)i=1，2，.n; j=1,2,m. 有 ,則1),(11mjjniiba1),(jibaji有證：因?yàn)閷?duì)任意的j有 1.1),),(),(221jnjnjnbabaabaaa（),(),(222121mnmnbbaabbbaaa),21mnbaaa （12、設(shè)(a,b)=d,則一定存在整數(shù)x,y使得ax+by=d證：由輾轉(zhuǎn)相除法倒過(guò)來(lái)即可得。 因?yàn)?=( )a+(

7、)b令第一個(gè)括號(hào)里的數(shù)為x,第二個(gè)括號(hào)里的數(shù)為y,即得。21nnnnrrqrd推論：(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下面我們給出n 個(gè)整數(shù)的最大公因數(shù)的求法13、 為n個(gè)整數(shù)，又設(shè) 則有注：性質(zhì)13說(shuō)明了n個(gè)數(shù)的最大公因數(shù)可兩個(gè)兩個(gè)地求naaa,21nnndaddaddaa),(),( ,),(1332221),(21naaand證：由已知得 說(shuō)明了 是 的公因數(shù)。 又設(shè)d是 的任一公因數(shù)，

8、則有 又有 這說(shuō)明了 是 的最大公因數(shù)。niadadddiniiii，2 , 1,|,|,|1ndnaaa,21naaa,21,|,|221ddadad,|33ddadndnaaa,21ndd|例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.例2：設(shè)k 為正奇數(shù)，試證證：設(shè) ,則則有 ,又所以又有 即有9|2s,10|2s,由(9,10)=1,有90|2s.故 kkk921 |921kkks921)19()82()91 (2kkkkkks)09()81 (

9、90(2kkkkkks）292Ns kkk921 |9211102Ns 例3：設(shè)n,a 是正整數(shù)，試證若 不是整數(shù)， 則一定是無(wú)理數(shù).na證：若 是非整數(shù)的有理數(shù)，則可設(shè) , , 于是有因?yàn)?p,q)=1,所以有 , 但 ,所以有 所以假設(shè)錯(cuò)誤，若 不是整數(shù)，則一定是無(wú)理數(shù).qpan1),( , 1qpqnannqpa 1),(nnqp1nqnpnqna注：對(duì)任意的正整數(shù)n,m有(a,b)=11),(mnba介紹兩個(gè)有名的數(shù)-梅森數(shù)和費(fèi)爾馬數(shù)梅森數(shù)：形如2n-1的數(shù)叫梅森數(shù)，記成Mn=2n-1。費(fèi)爾馬數(shù)：n為非負(fù)整數(shù)，形如 的數(shù)叫費(fèi)爾馬數(shù)，記成Fn= 122n122n例4： 證明對(duì)任意 m, n，mn, (Fn , Fm)=1。證：不妨設(shè)nm，則Fn-2= =(Fn-1-2) Fn-1 = Fn-1Fn-2Fm 設(shè)（Fn ,Fm）=d, 則d | Fn, d| Fm d|2但Fn為奇數(shù)，d=1, 即證。) 12)(12(1122nn01FF例5:證明