4　最大公约数理论

本节将通过三个途径来建立最大公约数理论.以便我们较全面、深入地理解初等数论中有关整除的思想、概念与方法，并能较灵活熟练地掌握.这三个途径都需要利用带余数除法.应该指出的是在2中证明的有关最大公约数与最小公倍数的性质均与带余数除法无关，而本节证明的性质都与它有关.首先，我们来列出组成最大公约数理论的主要的八个常用的定理，可能除了定理8之外，其他七个定理中小学生都是知道且经常应用的.但是，他们大概都不会证明这些定理，认为它们是当然成立的，不需要证明.这八个定理是：

定理1a_j|c（1≤j≤k）的充分必要条件是［a₁，…，a_k］|c.这就是说，公倍数一定是最小公倍数的倍数.这是最小公倍数的本质属性.

定理2设D是正整数，那么D=（a₁，…，a_k）的充分必要条件是：

（i）D|a_j（1≤j≤k）；（ii）若d|a_j（1≤j≤k），则d|D.

这就是说，公约数一定是最大公约数的约数.这是最大公约数的本质属性.

定理3设m＞0.我们有

m（b₁，…，b_k）=（mb₁，…，mb_k）.（1）

这就是说，若干个数乘以相同的数m（m>0）后的最大公约数等于它们的最大公约数乘以m.

定理4（i）（a₁，a₂，a₃，…，a_k）=（（a₁，a₂），a₃，…，a_k）；

（ii）（a₁，…，a_k+r）=（（a₁，…，a_k），（a_k+1，…，a_k+r））.

结论（i）就是说，求若干个数的最大公约数可以归结为求两个数的最大公约数的情形（为什么）.定理表明，求若干个数的最大公约数，可以先将这些数任意分组，分别求出各组数的最大公约数，然后再求这些最大公约数的最大公约数（为什么）.

定理5设（m，a）=1，则有（m，ab）=（m，b）.这就是说，求m与另一个数的最大公约数时，可以把另一个数中与m互素的因数去掉.

定理6设（m，a）=1，那么，若m|ab，则m|b.这就是说，若一个数被m整除，则把这个数中与m互素的因数去掉后仍被m整除.

定理7［a₁，a₂］（a₁，a₂）=|a₁a₂|.这就是说，两个数的最小公倍数乘以它们的最大公约数就等于这两个数的乘积的绝对值.

定理8设a₁，…，a_k是不全为零的整数.我们有

（i）（a₁，…，a_k）=min｛s=a₁x₁+…+a_kx_k：x_j∈Z（1≤j≤k），s＞0｝，即a₁，…，a_k的最大公约数等于a₁，…，a_k的所有整系数线性组合组成的集合S中的最小正整数.

（ii）一定存在一组整数x_1，0，…，x_k，0，使得

（a₁，…，a_k）=a₁x_1，0+…+a_kx_k，0.（2）

这就是说，若干个数的最大公约数一定等于这些数的整系数线性组合.

应该指出，在这八个定理中，只有定理8与加法运算有关，而其他七个定理仅与乘法和除法运算有关.