2.3　最大公約數(shù)與最小公倍數(shù)

現(xiàn)在來引進(jìn)最大公約數(shù)與最小公倍數(shù)的概念，并討論它們最基本的性質(zhì).

定義3設(shè)a₁，a₂是兩個(gè)整數(shù).如果d|a₁且d|a₂，那么d就稱為a₁和a₂的公約數(shù).一般地，設(shè)a₁，a₂，…，a_k是k個(gè)整數(shù).如果d|a₁，…，d|a_k，那么d就稱為a₁，…，a_k的公約數(shù).（注：有的書上是這樣定義最大公約數(shù)的，先是按定義3定義了兩個(gè)數(shù)的最大公約數(shù)，然后，利用數(shù)學(xué)歸納法來定義多個(gè)數(shù)的最大公約數(shù)，即（a₁，…，a_k-1，a_k）=（（a₁，…，a_k-1），a_k），k>2.這樣的定義在邏輯上看來是不科學(xué)的.）

例如：a₁=12，a₂=18.它們的公約數(shù)是±1，±2，±3，±6.a₁=6，a₂=10，a₃=-15.它們的公約數(shù)是±1.n和n+1的公約數(shù)是±1.當(dāng)a₁，…，a_k中有一個(gè)不為零時(shí)，由定理1（vi）知它們的公約數(shù)的個(gè)數(shù)有限.因此，可引進(jìn)：

定義4設(shè)a₁，a₂是兩個(gè)不全為零的整數(shù).我們把a(bǔ)₁和a₂的公約數(shù)中的最大的稱為a₁和a₂的最大公約數(shù)，記做（a₁，a₂）.一般地，設(shè)a₁，…，a_k是k個(gè)不全為零的整數(shù).我們把a(bǔ)₁，…，a_k的公約數(shù)中的最大的稱為a₁，…，a_k的最大公約數(shù)，記做（a₁，…，a_k）.當(dāng)k=1時(shí)，（a₁）就表示a₁的約數(shù)中的最大的.我們用D（a₁，…，a_k）表a₁，…，a_k的所有公約數(shù)組成的集合，當(dāng)k=1時(shí)，D（a₁）就表示a₁的所有約數(shù)組成的集合.這樣就有

（a₁）=max（d：d∈D（a₁））=|a₁|，

（a₁，a₂）=max（d：d∈D（a₁，a₂）），

（a₁，…，a_k）=max（d：d∈D（a₁，…，a_k））.（2）

前面所舉的例子表明：

D（12，18）=｛±1，±2，±3，±6｝，（12，18）=6；

D（6，10，-15）=｛±1｝，（6，10，-15）=1，（n，n+1）=1.

由定義立即推出以下性質(zhì)：

定理8（i）（a₁，a₂）=（a₂，a₁）=（-a₁，a₂）=（｜a₁｜，|a₂|）.

一般地，有

（a₁，a₂，…，a_i，…，a_k）=（a_i，a₂，…，a₁，…，a_k）=（-a₁，a₂，…，a_k）=（|a₁|，…，|a_i|，…，|a_k|）.

（ii）若a₁|a_j，j=2，…，k，則

（a₁，a₂）=（a₁，a₂，…，a_k）=（a₁）=|a₁|.

（iii）對(duì)任意的整數(shù)x，（a₁，a₂）=（a₁，a₂，a₁x），

（a₁，…，a_k）=（a₁，…，a_k，a₁x）.

（iv）對(duì)任意整數(shù)x，（a₁，a₂）=（a₁，a₂+a₁x），

（a₁，a₂，a₃，…，a_k）=（a₁，a₂+a₁x，a₃，…，a_k）.

（v）若p是素?cái)?shù)，則

證根據(jù)公約數(shù)的定義及整除性質(zhì)推出D（a₁，a₂）=D（a₂，a₁）=D（-a₁，a₂）=D（｜a₁｜，|a₂|），

D（a₁，a₂）=D（a₁，a₂，a₁x），x∈Z，

D（a₁，a₂）=D（a₁，a₂+a₁x），x∈Z.由此及最大公約數(shù)的定義就分別證明了（i），（iii），（iv）當(dāng)k=2時(shí)成立，k＞2的情形同樣證明.

（ii）由2定理1的（vi）推出.（v）由素?cái)?shù)的定義及（ii）推出.證畢.

應(yīng)該指出的是：由定理1（iii）可清楚地看出，由a₁，…，a_k的全體公約數(shù)組成的有限集合D（a₁，…，a_k），與確定的無限集合

｛a₁x₁+…+a_kx_k：x₁∈Z，…，x_k∈Z｝（3）

的全體公約數(shù)組成的集合是相同的.因此，可以用這個(gè)無限集合來刻畫“最大公約數(shù)”.這種聯(lián)系是十分重要的，是近代數(shù)論的重要思想.在4定理8將給出有關(guān)這種聯(lián)系的一個(gè)重要結(jié)論.

下面舉例說明，如何用定理8來求最大公約數(shù).請(qǐng)讀者自己指出，在每一步推導(dǎo)中用到了定理8的哪一個(gè)性質(zhì).

例5（i）對(duì)任意的整數(shù)n，有

（21n+4，14n+3）=（7n+1，14n+3）=（7n+1，1）=1.

（ii）對(duì)任意整數(shù)n，有

（iii）（30，45，84）=（30，15，84）=（0，15，84）=（15，84）=（15，-6）=（3，-6）=3.

（iv）對(duì)任意整數(shù)n，有

一組數(shù)的最大公約數(shù)等于1是刻畫這組數(shù)之間關(guān)系的一個(gè)重要性質(zhì).為此引進(jìn)表述刻畫這一特性的術(shù)語.

定義5若（a₁，a₂）=1，則稱a₁和a₂是既約的，或是互素的.一般地，若（a₁，…，a_k）=1，則稱a₁，…，a_k是既約的，或是互素的.

例如：2和2n+1既約；對(duì)任意的n，21n+4和14n+3既約；6，10，-15是既約的，但它們中任意兩個(gè)數(shù)不既約，因?yàn)椋?，10）=2，（10，-15）=5，（-15，6）=3.下面的定理對(duì)判斷一組數(shù)是否既約是有用的.

定理9如果存在整數(shù)x₁，…，x_k，使得a₁x₁+…+a_kx_k=1，則a₁，…，a_k是既約的.

證因?yàn)閍₁，…，a_k的任一公約數(shù)d一定要整除1，所以，必有d=±1.這就證明了所要的結(jié)論.

以后將證明條件a₁x₁+…+a_kx_k=1也是a₁，…，a_k既約的必要條件.利用定理9也可證例5（i）的結(jié)論，因?yàn)?/p>

3·（14n+3）+（-2）（21n+4）=1.

由定義還可推出最大公約數(shù)以下的性質(zhì).

定理10設(shè)正整數(shù)m|（a₁，…，a_k）.我們有

m（a₁/m，…，a_k/m）=（a₁，…，a_k）.（4）

特別地，有

證記D=（a₁，…，a_k）.由m|D，D|a_j（1≤j≤k）知

m|a_j（1≤j≤k），

因而有

（D/m）|（a_j/m），j=1，…，k，即D/m是a₁/m，…，a_k/m的公約數(shù)，且是正的，所以由定義知

D/m≤（a₁/m，…，a_k/m）.（6）

另一方面，若d|（a_j/m），1≤j≤k，則mda_j，j=1，…，k，由定義知

md≤D，即d≤D/m.

取d=（a₁/m，…，a_k/m），由此及式（6）即得式（4）.在式（4）中取m=（a₁，…，a_k）即得式（5）.

以后將證明：以條件ma_j（1≤j≤k）代替條件m（a₁，…，a_k）時(shí)，式（4）仍然成立（見4定理3）.下面來討論最小公倍數(shù).

定義6設(shè)a₁，a₂是兩個(gè)均不等于零的整數(shù).如果a₁l且a₂l，則稱l是a₁和a₂的公倍數(shù).一般地，設(shè)a₁，…，a_k是k個(gè)均不等于零的整數(shù).如果a₁|l，…，a_k|l，則稱l是a₁，…，a_k的公倍數(shù).此外，以L（a₁，…，a_k）記a₁，…，a_k的所有公倍數(shù)組成的集合.當(dāng)k=1時(shí)，就是a₁的所有倍數(shù)組成的集合.

例如：a₁=2，a₂=3.它們的公倍數(shù)集合（為什么）

L（2，3）=｛0，±6，±12，…，±6k，…｝.

由最小自然數(shù)原理知，可引進(jìn)以下的概念：

定義7設(shè)整數(shù)a₁，a₂均不為零.我們把a(bǔ)₁和a₂的正的公倍數(shù)中的最小的稱為a₁和a₂的最小公倍數(shù)，記做［a₁，a₂］，即

［a₁，a₂］=min｛l：l∈L（a₁，a₂），l＞0｝.（7）

一般地，設(shè)整數(shù)a₁，…，a_k均不等于零.我們把a(bǔ)₁，…，a_k的正的公倍數(shù)中的最小的稱為a₁，…，a_k的最小公倍數(shù)，記做［a₁，…，a_k］，即

［a₁，…，a_k］=min｛l：l∈L（a₁，…，a_k），l＞0｝.（8）

當(dāng)k=1時(shí)，［a₁］就是a₁的最小正倍數(shù)，即|a₁|.

例如：［2，3］=6.由定義立即推得

定理11（i）［a₁，a₂］=［a₂，a₁］=［-a₁，a₂］=［｜a₁｜，|a₂|］.一般地，有

［a₁，a₂，…，a_i，…，a_k］=［a_i，a₂，…，a₁，…，a_k］=［-a₁，a₂，…，a_i，…，a_k］=［|a₁|，…，｜a_i｜，…，|a_k|］.

（ii）若a₂a₁，則［a₁，a₂］=|a₁|；若a_j|a₁（2≤j≤k），則

［a₁，…，a_k］=|a₁|.

（iii）對(duì)任意的d|a₁，

［a₁，a₂］=［a₁，a₂，d］；

［a₁，…，a_k］=［a₁，…，a_k，d］.

證明留給讀者.

定理12設(shè)m＞0.我們有

［ma₁，…，ma_k］=m［a₁，…，a_k］.（9）

證設(shè)L=［ma₁，…，ma_k］，L′=［a₁，…，a_k］.由ma_j|L（1≤j≤k）推出a_j|L/m（1≤j≤k），進(jìn)而由最小公倍數(shù)定義知L′≤L/m.另一方面，由a_j|L′（1≤j≤k）推出ma_j|mL′（1≤j≤k），進(jìn)而由最小公倍數(shù)定義推出L≤mL′.這就證明了式（9）.

最大公約數(shù)與最小公倍數(shù)的進(jìn)一步的性質(zhì)，需要利用3討論的帶余數(shù)除法，將在4討論.