4　最大公約數(shù)理論

本節(jié)將通過三個途徑來建立最大公約數(shù)理論.以便我們較全面、深入地理解初等數(shù)論中有關(guān)整除的思想、概念與方法，并能較靈活熟練地掌握.這三個途徑都需要利用帶余數(shù)除法.應(yīng)該指出的是在2中證明的有關(guān)最大公約數(shù)與最小公倍數(shù)的性質(zhì)均與帶余數(shù)除法無關(guān)，而本節(jié)證明的性質(zhì)都與它有關(guān).首先，我們來列出組成最大公約數(shù)理論的主要的八個常用的定理，可能除了定理8之外，其他七個定理中小學生都是知道且經(jīng)常應(yīng)用的.但是，他們大概都不會證明這些定理，認為它們是當然成立的，不需要證明.這八個定理是：

定理1a_j|c（1≤j≤k）的充分必要條件是［a₁，…，a_k］|c.這就是說，公倍數(shù)一定是最小公倍數(shù)的倍數(shù).這是最小公倍數(shù)的本質(zhì)屬性.

定理2設(shè)D是正整數(shù)，那么D=（a₁，…，a_k）的充分必要條件是：

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

這就是說，公約數(shù)一定是最大公約數(shù)的約數(shù).這是最大公約數(shù)的本質(zhì)屬性.

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

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

這就是說，若干個數(shù)乘以相同的數(shù)m（m>0）后的最大公約數(shù)等于它們的最大公約數(shù)乘以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））.

結(jié)論（i）就是說，求若干個數(shù)的最大公約數(shù)可以歸結(jié)為求兩個數(shù)的最大公約數(shù)的情形（為什么）.定理表明，求若干個數(shù)的最大公約數(shù)，可以先將這些數(shù)任意分組，分別求出各組數(shù)的最大公約數(shù)，然后再求這些最大公約數(shù)的最大公約數(shù)（為什么）.

定理5設(shè)（m，a）=1，則有（m，ab）=（m，b）.這就是說，求m與另一個數(shù)的最大公約數(shù)時，可以把另一個數(shù)中與m互素的因數(shù)去掉.

定理6設(shè)（m，a）=1，那么，若m|ab，則m|b.這就是說，若一個數(shù)被m整除，則把這個數(shù)中與m互素的因數(shù)去掉后仍被m整除.

定理7［a₁，a₂］（a₁，a₂）=|a₁a₂|.這就是說，兩個數(shù)的最小公倍數(shù)乘以它們的最大公約數(shù)就等于這兩個數(shù)的乘積的絕對值.

定理8設(shè)a₁，…，a_k是不全為零的整數(shù).我們有

（i）（a₁，…，a_k）=min｛s=a₁x₁+…+a_kx_k：x_j∈Z（1≤j≤k），s＞0｝，即a₁，…，a_k的最大公約數(shù)等于a₁，…，a_k的所有整系數(shù)線性組合組成的集合S中的最小正整數(shù).

（ii）一定存在一組整數(shù)x_1，0，…，x_k，0，使得

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

這就是說，若干個數(shù)的最大公約數(shù)一定等于這些數(shù)的整系數(shù)線性組合.

應(yīng)該指出，在這八個定理中，只有定理8與加法運算有關(guān)，而其他七個定理僅與乘法和除法運算有關(guān).