§1.2 最大公因数和最小公倍数定义1 设是个整数。如果整数是它们中每一个数的因数，那么就称为的一个公因数。当不全为零时，称它们的所有公因数中最大的一个正整数为整数的最大公因数，记作，即
特别地，当时，称互素。
由定义可以看出对任意非零整数，有。
定义2 设是个整数。如果整数是它们中每一个数的倍数，那么就称为的一个公倍数。当都不为零时，称它们的所有公倍数中最小的一个正整数为整数的最小公倍数，记作，即
由最大公因数和最小公倍数的定义，很容易发现他们具有如下性质性质1 （ⅰ）；
（ⅱ）设是三个不全为零的整数，如果，其中是整数，则；
（ⅲ）对任意整数，必有；
例1 设是一个素数，为整数。如果，则与互素。
从上面例题可以看出若是一个素数，则对于任意整数，或者
由性质1（ⅱ）可由下述辗转相除法具体求出两个整数的最大公因数：
,；
,；
,；
,；
,
因为是一个单调有界非负序列，所以必然存在有限步达到上述最后一个等式。
例2 （1）设，计算；
（2）设，计算。
上面计算过程可以总结为如下算法：
求任意两个整数和最大公因数算法：
算法1.2.1 （1）如果，则，如果，则；
（2）如果，则输出“整数和无最大公因数”，结束程序；
（3）令，；
（4），；
（5）如果，返回到第（4）步；
（6）。
上述算法被称为广义欧几里得除法。
由性质1（ⅰ）和（ⅱ）我们知道，在步骤（4）中可以使用绝对值最小余数，这种方法在都比较大时，算法的复杂性会降低。我们可以看看例2（2）使用绝对值最小余数的另一种解法,此解法的运算次数比算法1.2.1少了3次。
在辗转相除法具体求两个整数的最大公因数的过程中，从倒数第二个式子开始把所有的等式移项后可得
……
,
,
逐次消除，则可以找到整数使得
例3 运用上述方法求整数，使得
（1） （2）
上述求解过程可以归结为如下定理。
定理1 设是任意两个整数，则存在，使得
这里由下面等式递归得到
其中为（1）式中的不完全商。
如果记，注意到，则我们只需要用数学归纳法证明等式
成立即可。由上述定理可知，求整数，使得可以归结为如下算法：
算法1.2.2 （1）令，，；
（2）如果，则令，结束程序；
（3）令，，，；
（4），返回到（2）；
关于定理1，我们需要注意以下三点：
1,满足等式成立的整数不惟一，例如，若有整数，使得，则整数同样可以满足条件；
2,存在整数，使得，必要性由定理1直接可得，充分性由式子可得；
3,若是正整数，则。首先注意到如果被除的最小正余数是，则被除的最小正余数是，所以由广义的欧几里得除法知。
由定理1我们很容易得到最大公约数和最小公倍数具有如下性质：
性质2 （ⅳ）若，则；
（ⅴ）设是三个整数，且不同时为零。如果，则
。
进一步，若，，则；
（ⅵ）若，，则，；
若，则；
（ⅶ）若，则；
（ⅷ）若，则；
（ⅸ）。
例4 设是两个整数，是素数，若，则。
上述性质对于我们研究整数的性质很有帮助。由性质2（ⅸ）我们可以得到求任意两个整数和最小公倍数算法：
算法1.2.3 （1）若或，则整数和无最小公倍数；
（2）按照求任意两个整数和最大公因数算法计算出；
（3）计算。
例5 证明：如果整数满足，那么或者。
对于个整数的最大公约数和最小公倍数，我们有如下递归方法：
定理2 设,是个整数，则
；
。
上述定理可以归结为如下算法：
求个整数的最大公因数算法算法1.2.4 （1）按照求任意两个整数最大公因数算法计算，令；
（2），；
（3）如果，返回到第（2）步；
（4）。
求个整数的最小公倍数算法算法1.2.5 （1）按照求任意两个整数最小公倍数算法计算，令；
（2），；
（3）如果，返回到第（2）步；
（4）。
利用整除理论，我们很容易判断不定方程（其中是整数且）是否有解？
定理3 不定方程（其中是整数且）有解的充分必要条件是。如果是该不定方程的一组解，那么它所有的解为
其中
当不定方程有解时，求出其全部解的关键是寻找某一组特解，定理1保证了这样的特解总是可以找到的。
求不定方程（其中是整数且）的整数解的算法算法1.2.6 （1）按照求任意两个整数和最大公因数算法计算出；
（2）判断是否整除？如果，则不定方程无解，结束程序；
（3）按照算法1.2.2计算整数和，使得；
（4）不定方程的一切解可以表示为
，其中。
特别地，当时，称互素。
由定义可以看出对任意非零整数，有。
定义2 设是个整数。如果整数是它们中每一个数的倍数，那么就称为的一个公倍数。当都不为零时，称它们的所有公倍数中最小的一个正整数为整数的最小公倍数，记作，即
由最大公因数和最小公倍数的定义，很容易发现他们具有如下性质性质1 （ⅰ）；
（ⅱ）设是三个不全为零的整数，如果，其中是整数，则；
（ⅲ）对任意整数，必有；
例1 设是一个素数，为整数。如果，则与互素。
从上面例题可以看出若是一个素数，则对于任意整数，或者
由性质1（ⅱ）可由下述辗转相除法具体求出两个整数的最大公因数：
,；
,；
,；
,；
,
因为是一个单调有界非负序列，所以必然存在有限步达到上述最后一个等式。
例2 （1）设，计算；
（2）设，计算。
上面计算过程可以总结为如下算法：
求任意两个整数和最大公因数算法：
算法1.2.1 （1）如果，则，如果，则；
（2）如果，则输出“整数和无最大公因数”，结束程序；
（3）令，；
（4），；
（5）如果，返回到第（4）步；
（6）。
上述算法被称为广义欧几里得除法。
由性质1（ⅰ）和（ⅱ）我们知道，在步骤（4）中可以使用绝对值最小余数，这种方法在都比较大时，算法的复杂性会降低。我们可以看看例2（2）使用绝对值最小余数的另一种解法,此解法的运算次数比算法1.2.1少了3次。
在辗转相除法具体求两个整数的最大公因数的过程中，从倒数第二个式子开始把所有的等式移项后可得
……
,
,
逐次消除，则可以找到整数使得
例3 运用上述方法求整数，使得
（1） （2）
上述求解过程可以归结为如下定理。
定理1 设是任意两个整数，则存在，使得
这里由下面等式递归得到
其中为（1）式中的不完全商。
如果记，注意到，则我们只需要用数学归纳法证明等式
成立即可。由上述定理可知，求整数，使得可以归结为如下算法：
算法1.2.2 （1）令，，；
（2）如果，则令，结束程序；
（3）令，，，；
（4），返回到（2）；
关于定理1，我们需要注意以下三点：
1,满足等式成立的整数不惟一，例如，若有整数，使得，则整数同样可以满足条件；
2,存在整数，使得，必要性由定理1直接可得，充分性由式子可得；
3,若是正整数，则。首先注意到如果被除的最小正余数是，则被除的最小正余数是，所以由广义的欧几里得除法知。
由定理1我们很容易得到最大公约数和最小公倍数具有如下性质：
性质2 （ⅳ）若，则；
（ⅴ）设是三个整数，且不同时为零。如果，则
。
进一步，若，，则；
（ⅵ）若，，则，；
若，则；
（ⅶ）若，则；
（ⅷ）若，则；
（ⅸ）。
例4 设是两个整数，是素数，若，则。
上述性质对于我们研究整数的性质很有帮助。由性质2（ⅸ）我们可以得到求任意两个整数和最小公倍数算法：
算法1.2.3 （1）若或，则整数和无最小公倍数；
（2）按照求任意两个整数和最大公因数算法计算出；
（3）计算。
例5 证明：如果整数满足，那么或者。
对于个整数的最大公约数和最小公倍数，我们有如下递归方法：
定理2 设,是个整数，则
；
。
上述定理可以归结为如下算法：
求个整数的最大公因数算法算法1.2.4 （1）按照求任意两个整数最大公因数算法计算，令；
（2），；
（3）如果，返回到第（2）步；
（4）。
求个整数的最小公倍数算法算法1.2.5 （1）按照求任意两个整数最小公倍数算法计算，令；
（2），；
（3）如果，返回到第（2）步；
（4）。
利用整除理论，我们很容易判断不定方程（其中是整数且）是否有解？
定理3 不定方程（其中是整数且）有解的充分必要条件是。如果是该不定方程的一组解，那么它所有的解为
其中
当不定方程有解时，求出其全部解的关键是寻找某一组特解，定理1保证了这样的特解总是可以找到的。
求不定方程（其中是整数且）的整数解的算法算法1.2.6 （1）按照求任意两个整数和最大公因数算法计算出；
（2）判断是否整除？如果，则不定方程无解，结束程序；
（3）按照算法1.2.2计算整数和，使得；
（4）不定方程的一切解可以表示为
，其中。
