2.3　最大公約數與最小公倍數

現在來引進最大公約數與最小公倍數的概念，并討論它們最基本的性質.

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

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

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

（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.

由定義立即推出以下性質：

定理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）對任意的整數x，（a₁，a₂）=（a₁，a₂，a₁x），

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

（iv）對任意整數x，（a₁，a₂）=（a₁，a₂+a₁x），

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

（v）若p是素數，則

證根據公約數的定義及整除性質推出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.由此及最大公約數的定義就分別證明了（i），（iii），（iv）當k=2時成立，k＞2的情形同樣證明.

（ii）由2定理1的（vi）推出.（v）由素數的定義及（ii）推出.證畢.

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

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

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

下面舉例說明，如何用定理8來求最大公約數.請讀者自己指出，在每一步推導中用到了定理8的哪一個性質.

例5（i）對任意的整數n，有

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

（ii）對任意整數n，有

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

（iv）對任意整數n，有

一組數的最大公約數等于1是刻畫這組數之間關系的一個重要性質.為此引進表述刻畫這一特性的術語.

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

例如：2和2n+1既約；對任意的n，21n+4和14n+3既約；6，10，-15是既約的，但它們中任意兩個數不既約，因為（6，10）=2，（10，-15）=5，（-15，6）=3.下面的定理對判斷一組數是否既約是有用的.

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

證因為a₁，…，a_k的任一公約數d一定要整除1，所以，必有d=±1.這就證明了所要的結論.

以后將證明條件a₁x₁+…+a_kx_k=1也是a₁，…，a_k既約的必要條件.利用定理9也可證例5（i）的結論，因為

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

由定義還可推出最大公約數以下的性質.

定理10設正整數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的公約數，且是正的，所以由定義知

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）時，式（4）仍然成立（見4定理3）.下面來討論最小公倍數.

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

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

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

由最小自然數原理知，可引進以下的概念：

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

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

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

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

當k=1時，［a₁］就是a₁的最小正倍數，即|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）對任意的d|a₁，

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

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

證明留給讀者.

定理12設m＞0.我們有

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

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

最大公約數與最小公倍數的進一步的性質，需要利用3討論的帶余數除法，將在4討論.