數(shù)的整除性最大公因數(shù)

1、初 等 數(shù) 論 （4）（第一章 數(shù)的整除性 第四節(jié) 最大公因數(shù)（1）定義1 整數(shù)a1，a2，L，ak的公共因數(shù)稱為a1，a2，L，ak的公因數(shù)。不全為零的整數(shù)a1，a2，L，ak的公因數(shù)中最大的一個(gè)叫做a1，a2，L，ak的最大公因數(shù)，記為（a1，a2，L，ak）。由于每個(gè)非零整數(shù)的因數(shù)的個(gè)數(shù)是有限的，所以最大公因數(shù)是存在的，并且是正整數(shù)。如果（a1，a2，L，ak） = 1，則稱a1，a2，L，ak是互質(zhì)的；如果 （ai , a j） = 1，1 £ i £ k，1 £ j £ k， i ¹ j，則稱a1，a2，L，ak是兩兩互質(zhì)的。顯然，由

2、a1，a2，L，ak兩兩互質(zhì)可以推出（a1，a2，L，ak） = 1，反之則不然，例如（2，6，15） = 1，但（2，6）= 2。定理1 下面的等式成立：（） （a1，a2，L，ak） =（|a1|， |a2|，L，|ak|）；（） （a，1） = 1，（a，0） = |a|，（a，a） = |a|；（） （a，b） = （b，a）；（） 若p是質(zhì)數(shù)，a是整數(shù)，則（p，a） = 1或p½a；（） 若a = bq + r，則（a，b） =（b，r）。證明（） 我們先證明a1，a2，L，ak與|a1|， |a2|，L，|ak|的公因數(shù)相同。設(shè)d是a1，a2，L，ak 任一公因數(shù)，由定義

3、d½ ai ，i = 1，2，n。 因而d½| ai | ，i = 1，2，n。故d是|a1|， |a2|，L，|ak|的一個(gè)公因數(shù),同樣的方法可證|a1|， |a2|，L，|ak|的任一個(gè)公因數(shù)都是a1，a2，L，ak的一個(gè)公因數(shù).即a1，a2，L，ak與|a1|， |a2|，L，|ak|的公因數(shù)相同。由此可直接得（a1，a2，L，ak） =（|a1|， |a2|，L，|ak|）；（）、（）、（）顯然。（）如果d½a，d½b，則有d½r = a - bq，反之，若d½b，d½r，則d½a = bq + r。因此a

4、與b的全體公因數(shù)的集合就是b與r的全體公因數(shù)的集合，這兩個(gè)集合中的最大正數(shù)當(dāng)然相等，即（a，b） = （b，r）。由定理1可知，在討論（a1，a2，L，ak）時(shí)，不妨假設(shè)a1，a2，L，ak是正整數(shù)，以后我們就維持這一假設(shè)。例1 求 （27，15）解 27 = 1×15 + 12 （27，15）=（15，12）15 =1×12 + 3 （15，12）=（12，3）12 = 4×3 （12，3）=（3，0）其中a = 27，b = 15， q1 = 1，r1 = 12，q2 = 1，r2 = 3，q3 = 4。以上步驟可以寫為下面的式子例2 大廈公司銷售某種貨物，去

5、年總收入為36963元，今年某種貨物的售價(jià)（單價(jià)）不變，總收入59570元。如果單價(jià)（以元為單位）是大于1的整數(shù)，問(wèn)今年與去年各售這種貨物多少件？解 單價(jià)是36963與59570的公約數(shù)，由輾轉(zhuǎn)相除得（33963，59570）=37因?yàn)?7只有約數(shù)1與本身，所以單價(jià)為37元。例3 證明：若n是正整數(shù)，則是既約分?jǐn)?shù)。證明 由定理1得到（21n + 4，14n + 3） = （7n + 1，14n + 3） = （7n + 1, 1）= 1。定理2 設(shè)a1, a2, L, akÎZ，記A = y½y = a1x1 + L + akxk，xiÎZ，1 £ i

6、£ k 。如果y0是集合A中最小的正數(shù)，則y0 = （a1，a2,，L，ak）。證明 設(shè)d是a1，a2，L，ak的一個(gè)公因數(shù)，則d½y0= a1x1 + L + akxk，所以d £ y0。另一方面，由第二節(jié)例1知，y0也是a1，a2，L，ak的公因數(shù)。因此y0是a1，a2，L，ak的公因數(shù)中的最大者，即y0 = （a1，a2，L，ak）。證畢。例如 a1=18， a2=12， a3=10則18 x1+12 x2+10 x3中最小的正數(shù)是2。（此時(shí)x1=1， x2 = 2， x3= - 4）推論1 設(shè)d是a1，a2，L，ak的一個(gè)公因數(shù)，則d½（a1，a

7、2，L，ak）。這個(gè)推論對(duì)最大公因數(shù)的性質(zhì)做了更深的刻劃：最大公因數(shù)不但是公因數(shù)中的最大的，而且是所有公因數(shù)的倍數(shù)。推論2 （ma1，ma2，L，mak） = |m|（a1，a2，L，ak）。證明 記A = y½y = a1x1 + L + akxk，xiÎZ，1 £ i £ k 。中最小的正數(shù)是y0，則= y½y = m(a1x1 + L + akxk)， xiÎZ，1 £ i £ k 。中最小的正數(shù)是|m|y0，由定理2可得 （ma1，ma2，L，mak） = |m|（a1，a2，L，ak）。推論3 記d =（

8、a1，a2，L，ak），則特別地， 。定理3 （a1，a2，L，ak） = 1的充要條件是存在整數(shù)x1, x2, L, xk，使得a1x1 + a2x2 + L + akxk = 1。 （1） 證明 必要性 如果（a1，a2，L，ak） = 1，由定理2知y0 =1，所以，存在整數(shù)x1，x2，L，xk，使得a1x1 + a2x2 + L + akxk = 1。 充分性 若（1）式成立，如果（a1，a2，L，ak）= d > 1，那么由d½ai（1 £ i £ k）推出d½a1x1 + a2x2 + L + akxk = 1，這是不可能的。所以有（a

9、1，a2，L，ak） = 1。練 習(xí) 題1求（5767，4453） 初 等 數(shù) 論 （5）（第一章 數(shù)的整除性 第五節(jié) 最大公因數(shù)（2）裴蜀恒等式：我們將定理2、定理3中的k取2，再考慮（a1，a2）=d的一般情形即得定理2 設(shè)a1，a2ÎZ，記A = y½y = a1x1 +a2x2，x1，x2ÎZ，。如果y0是集合A中最小的正數(shù)，則y0 =（a1，a2）。定理3 （a1，a2）= d,則存在整數(shù)x1, x2，使得a1x1 + a2x2 =d。 證明 如果（a1，a2）= d，由定理2知y0= d，所以，存在整數(shù)x1, x2, 使得a1x1 + a2x2 = d

10、。 這就證明了課本的裴蜀恒等式。我們通過(guò)具體的例子看如何求x1，x2。例如 （213，60）=3，求x1，x2使213 x1+60 x2=3213=3×60+3360=1×33+2733=1×27+627=4×6+33=274×6=274×（3327）=5×274×33=5×（6033）4×33 =5×609×33=5×609×（2133×60）=32×609×213即x1= 9，x2=32記x1= u， x2= v，則3 =

11、 213×u + 60×v。例1 兩個(gè)容器，一個(gè)為27L，另一個(gè)為15L，如何利用它們從一桶油中倒出6L油來(lái)？解 由例2可知（27，15）=3，且27=1×15+1215=1×12+3從而3=15-1×12=15-1×（27-1×15）即3=2×15- 27 于是6 = 4×15- 2× 27例2 已知一個(gè)角的度數(shù)為，其中n是不能被3整除的正整數(shù)，證明這個(gè)角可以用圓規(guī)和直尺三等分。解 因?yàn)閚與3互質(zhì)，因此有1 = un - 3v其中u、v均為正整數(shù)，從而這表明先作角等于（60º角可以用

12、尺規(guī)作出），然后再減去，（是已知角），就產(chǎn)生了的角。具體給出n即可求u、v。例3 已知ad - bc = 1，證明：是既約分?jǐn)?shù)。證明 由于a×( c+d ) - c×( a+b ) = ad- bc = 1于是c + d與a + b互質(zhì)。例如3×5-2×7=1，則3+2與5+7互質(zhì)。例7 證明：對(duì)于每個(gè)自然數(shù)n，為既約分?jǐn)?shù)。證明 由于（14n + 3）-2(7n + 1)=1所以14n + 3與7n + 1互質(zhì)，結(jié)論成立。例8 證明：存在一個(gè)有理數(shù)，其中0 < d <100，能使 對(duì)于k=1，2，99均成立，證明 首先注意到73與100互質(zhì)，

13、因此有c、 d存在，使73 d - 100 c = 1我們證明對(duì)于任一k1，2，99 ，都成立。事實(shí)上，設(shè)，由于k < 100，所以 0 < <得<由 得< n + 1 = 所以<£ = n + 1， 說(shuō)明 因?yàn)?，且k、c、d均為正整數(shù)，所以£。從而 。練 習(xí) 題用輾轉(zhuǎn)相除法求（125，85），以及u、v，使得125x + 85y = （125，85）。初 等 數(shù) 論 （6）（第一章 數(shù)的整除性 第六節(jié) 最大公因數(shù)（3）定理4 對(duì)于任意的整數(shù)a，b，c，下面的結(jié)論成立：（） 由b½ac及（a，b）= 1可以推出b½c；

14、例如 5½22×10，（22，5）=1可推出5½10。證明 （） 若（a，b）= 1，由定理2，存在整數(shù)x與y，使得ax + by = 1。因此acx + bcy = c。 （1）由上式及b½ac得到b½c。 （） 由b½c，a½c及（a，b） = 1可以推出ab½c。例如 3½60，5½60及（3，5） = 1可以推出3×5½60。證明 （） 若（a，b） = 1，則存在整數(shù)x，y使得ax + by =1成立，即acx + bcy = c （2）成立。由b½c與a

15、½c得到ab½ac，ab½bc，再由（2）式得到ab½c。推論1 若p是質(zhì)數(shù)，則下述結(jié)論成立：（） p½ab Þ p½a或p½b；即p½ab，若p½a，則結(jié)論成立，若p不能整除a，（p，a）=1，由定理4（）知p½b。例如 7½35×51，7½35×49（） p½a2 Þ p½a。推論2 若 （a，b） = 1，則（a，bc）=（a，c）。證明 設(shè)d是a與bc的一個(gè)公因數(shù)，則d½a，d½bc，由a

16、cx + bcy = c 得到，d½c, 即d是a與c的公因數(shù)。另一方面，若d是a與c的公因數(shù)，則它也是a與bc的公因數(shù)。因此，a與c的公因數(shù)的集合，就是a與bc的公因數(shù)的集合，所以 （a，bc）=（a，c）。證畢。定理5 對(duì)于任意的n個(gè)整數(shù)a1, a2, L, an，記（a1，a2） = d2， （d2，a3）= d3， L，（dn - 2，an - 1）= dn - 1，（dn - 1，an） = dn， 則dn =（a1，a2，L，an）。我們以3個(gè)整數(shù)a1，a2，a3 為例,記（a1，a2） = d2， （d2，a3） = d3，則d3 =（a1，a2，a3）。證明 先證明d

17、3是a1，a2，a3的一個(gè)公因數(shù)，我們有d3 =（d2，a3） Þ d3½a3，d3½d2，d2 =（a1，a2） Þ d2½a1，d2½a2Þ d3½a1，d3½a2即d3是a1，a2，a3的一個(gè)公因數(shù)。再證明對(duì)于a1，a2，a3的任何公因數(shù)d，有d½d3d½a1，d½a2 Þ d½d2，（a1，a2）= d2d½d2，d½a3 Þ d½d3，因此d3是a1，a2，a3 的公因數(shù)中的最大者，即d3 =（a1，a2，

18、a3 ）。例1 求（353430，530145，165186）解 （353430，530145，165186）=（353430，530145），165186）=（353430，176715），165186）=（0，176715），165186）=（176715，165186）=（11529，165186）=（11529，3780）=（189，3780）= 189（353430，530145，165186）= 189例2 證明：121n2 + 2n + 12，nÎZ。證明 由于121 = 112，n2 + 2n + 12 =（n + 1）2 + 11，所以，若112½（n +

19、 1）2 + 11， （3）11½（n + 1） 2 + 11則11½（n + 1） 2，因此，由定理4的推論1得到 11½n + 1，112½（n + 1）2。再由（3）式得到 112½11，這是不可能的。所以（3）式不能成立。例3 設(shè)a，b是整數(shù)，且9½a2 + ab + b2， （4）則3½（a，b）。證明 由（4）式得到9½（a - b）2 + 3ab Þ 3½（a - b） 2 + 3abÞ 3½（a - b）2 Þ 3½a - bÞ

20、9½（a- b） 2。再由（4）式得到9½3ab Þ 3½ab。 因此，由定理4的推論1，得到3½a或3½b。若3½a，由3½a- b得到3½b；若3½b，由上式也得到3½a。因此，總有3½a且3½b。所以3½（a，b）。例4 設(shè)a和b是正整數(shù)，b > 2，則2b - 12a + 1。證明 （） 若a < b，且2b - 1½2a + 1。 （5） 成立，則2b - 1 £ 2a + 1 Þ 2b - 2a

21、63; 2 Þ 2a（2b - a - 1）£ 2，于是a = 1，b - a = 1，即b = 2，這是不可能的，所以（5）式不成立。（） 若a = b，且（5）式成立，則由（5）式得到2a - 1½（2a - 1） + 2 Þ 2a - 1½2 Þ 2a - 1 £ 2 Þ 2a £ 3，于是b = a = 1，這是不可能的，所以（5）式不成立。（） 若a > b，記a = kb + r，0 £ r < b，其中k是正整數(shù)，此時(shí)2kb - 1 = （2b - 1）（2(k - 1

22、)b + 2(k - 2)b + L+ 1） = （2b - 1）Q，其中Q是整數(shù)。所以2a + 1= 2kb + r + 1 = 2r（2kb - 1 + 1） + 1= 2r（2b - 1）Q + 1 + 1 = （2b - 1）Q ¢ +（2r + 1），其中Q¢是整數(shù)。因此2b - 1½2a + 1 Þ 2b - 1½2r + 1，在（）中已經(jīng)證明這是不可能的，所以（5）式不能成立。綜上證得2b - 12a + 1。 練 習(xí) 題 1 設(shè)x，yÎZ，17½（2x + 3y），證明：17½（9x + 5y）。

23、2 設(shè)a，b，cÎN，c無(wú)平方因子，a2½b2c，證明：a½b。 初 等 數(shù) 論 （7）（第一章 數(shù)的整除性 第七節(jié) 最小公倍數(shù)）內(nèi)容提要：最小公倍數(shù)的概念、性質(zhì)，求最小公倍數(shù)的方法。定義1 整數(shù)a1，a2，L，ak的公共倍數(shù)稱為a1，a2，L，ak的公倍數(shù)。 a1，a2，L，ak的正公倍數(shù)中的最小的一個(gè)叫做a1，a2，L，ak的最小公倍數(shù)，記為a1，a2，L，ak。定理1 下面的等式成立：（） a，1 = |a|，a，a = |a|； 例如 5，1 = 5 = |5|，-5，1 =5=|-5|（） a，b = b，a；（）和（）顯然； （） a1，a2，L，ak

24、 = |a1|， |a2|， L，|ak| ；（） 證明 我們只要證明a1，a2，L, ak的公倍數(shù)集合和|a1|，|a2|，L，|ak|的公倍數(shù)集合相等就可以了。設(shè)m1是a1，a2，L，ak的公倍數(shù)，則ai½m1，可推出|ai|½m1，所以m1是|a1|，|a2|，L，|ak|的公倍數(shù)。同理若m2是|a1|，|a2|，L，|ak|的公倍數(shù)，則m2是a1，a2，L，ak的公倍數(shù)。即a1，a2，L，ak的公倍數(shù)集合與 |a1|，|a2|，L，|ak|的公倍數(shù)集合相等，所以a1，a2，L，ak = |a1|， |a2|，L，|ak| 。例如 15，-26，22 = 15，26，

25、22 =2145() 若a½b，則a，b = |b|。() 證明 顯然a½|b|，b½|b|，即|b|是a，b的公倍數(shù)，又若有a½m¢，b½m¢，m¢ > 0，則|b| £ m¢，即a，b的任一正的公倍數(shù)都大于或等于|b|，故有|b|是a，b的最小公倍數(shù)，即a，b = |b|。例如 3½-15， 3，15 = 15 = |-15|由定理1中的結(jié)論（）可知，在討論a1，a2，L，ak的最小公倍數(shù)時(shí)，不妨假定它們都是正整數(shù)。以下假定a1，a2，L，ak都是正整數(shù)。最小公倍數(shù)和最大公約

26、數(shù)之間有一個(gè)很重要的關(guān)系，即下面的定理。定理2 對(duì)任意的正整數(shù)a，b，有證明 設(shè)m是a和b的一個(gè)公倍數(shù)，那么存在整數(shù)k1，k2，使得m = ak1，m = bk2， ak1 = bk2 。 （1） （1）式兩邊同除以（a，b）得。由于，即互質(zhì)，而整除，所以，即，其中t是某個(gè)整數(shù)。將上式代入m =ak1 = bk2 （1）式得到 （2）也就是a，b的任一公倍數(shù)m可以表示為上式；另一方面，對(duì)于任意的整數(shù)t，由（2）式所確定的m顯然是a與b的公倍數(shù)，因此a與b的公倍數(shù)必是（2）式中的形式，其中t是整數(shù)。當(dāng)t = 1時(shí)，得到最小公倍數(shù)。例如 （335，134） = 67推論1 兩個(gè)整數(shù)的任何公倍數(shù)可以

27、被它們的最小公倍數(shù)整除。證明 由（2）式可得證。 這個(gè)推論說(shuō)明：兩個(gè)整數(shù)的最小公倍數(shù)不但是最小的正倍數(shù)，而且是另外的公倍數(shù)的約數(shù)。例如 15，36 =180，則15和36的正的公倍數(shù)為180，360，540等。推論2 設(shè)m，a，b是正整數(shù)，則ma, mb = ma，b。證明 由定理2 得到 例如 60，75 = 15×4，15×5 = 15×4，5 =15×20=300定理3 對(duì)于任意的n個(gè)整數(shù)a1，a2，L，an，記a1，a2 = m2，m2，a3 = m3，L，mn-2，an-1 = mn-1，mn-1，an= mn則a1，a2，L，an = mn。

28、推論 若m是整數(shù)a1，a2，L，an的公倍數(shù)，則a1，a2，L，an½m 。我們以n=4為例說(shuō)明先證明m4是a1，a2，a3，a4的一個(gè)公倍數(shù)，m4= m3，a4 Þ m3½m4，a4½m4，m3=m2，a3 Þ m2½m3½m4，a4½m4，a3½m3½m4， m2 = a1，a2 Þ a1½m2½m3½m4，a2½m2½m3½m4，a4½m4，a3½m3½m4，即m4是a1，a2，a3，a4的

29、一個(gè)公倍數(shù)。另一方面，對(duì)于a1，a2，a3，a4的任何公倍數(shù)m應(yīng)是a1，a2的公倍數(shù)，由定理2的推論1及a1，a2 = m2知m2½m，所以m是m2，a3的公倍數(shù)，又m2，a3 = m3，即m3是m2，a3的最小公倍數(shù)，所以m3可以整除m2，a3的公倍數(shù)m，m3½m，所以m是m3，a4的公倍數(shù)，而由m4 = m3，a4知m4½m，即m4可以整除a1，a2，a3，a4的任何公倍數(shù)m，所以m4是a1，a2，a3，a4的最小公倍數(shù)。定理4 整數(shù)a1，a2，L，an兩兩互質(zhì)，即(ai，aj) = 1，1 £ i £ n，1 £ j £ n，i ¹ j的充要條件是a1，a2，L，an = a1a2Lan 。 這個(gè)定理我們分開(kāi)敘述為：整數(shù)a1，a2，L，an兩兩互質(zhì)，則a1，a2，L，an = a1a2Lan。例如 3，5，11，23，=3×5×11