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讨论.