文档介绍：§ 最大公因数和最小公倍数
定义1 设是个整数。如果整数是它们中每一个数的因数,那么就称为的一个公因数。当不全为零时,称它们的所有公因数中最大的一个正整数为整数的最大公因数,记作,即
特别地,当时,称互素。
由定义可以看出对任意非零整数,有。
定义2 设是个整数。如果整数是它们中每一个数的倍数,那么就称为的一个公倍数。当都不为零时,称它们的所有公倍数中最小的一个正整数为整数的最小公倍数,记作,即
由最大公因数和最小公倍数的定义,很容易发现他们具有如下性质
性质1 (ⅰ);
(ⅱ)设是三个不全为零的整数,如果,其中是整数,则;
(ⅲ)对任意整数,必有;
例1 设是一个素数,为整数。如果,则与互素。
从上面例题可以看出若是一个素数,则对于任意整数,或者
由性质1(ⅱ)可由下述辗转相除法具体求出两个整数的最大公因数:
, ;
, ;
, ;
, ;
,
因为是一个单调有界非负序列,所以必然存在有限步达到上述最后一个等式。
例2 (1)设,计算;
(2)设,计算。
上面计算过程可以总结为如下算法:
求任意两个整数和最大公因数算法:
(1)如果,则,如果,则;
(2)如果,则输出“整数和无最大公因数”,结束程序;
(3)令,;
(4),;
(5)如果,返回到第(4)步;
(6)。
上述算法被称为广义欧几里得除法。
由性质1(ⅰ)和(ⅱ)我们知道,在步骤(4)中可以使用绝对值最小余数,这种方法在都比较大时,算法的复杂性会降低。我们可以看看例2(2)使用绝对值最小余数的另一种解法: 。
在辗转相除法具体求两个整数的最大公因数的过程中,从倒数第二个式子开始把所有的等式移项后可得
……
,
,

逐次消除,则可以找到整数使得
例3 运用上述方法求整数,使得
(1) (2)
上述求解过程可以归结为如下定理。
定理1 设是任意两个整数,则存在,使得
这里由下面等式递归得到
其中为(1)式中的不完全商。
如果记,注意到,则我们只需要用数学归纳法证明等式
成立即可。由上述定理可知,求整数,使得可以归结为如下算法:
(1)令,,;
(2)如果,则令,结束程序;
(3)令,,,;
(4),返回到(2);
关于定理1,我们需要注意以下三点:
1. 满足等式成立的整数不惟一,例如,若有整数,使得,则整数同样可以满足条件;
2. 存在整数,使得,必要性由定理1直接可得,充分性由式子可得;
3. 若是正整数,则。首先注意到如果被除的最小正余数是,则被除的最小正余数是,所以由广义的欧几里得除法知。
由定理1我们很容易得到最大公约数和最小公倍数具有如下性质:
性质2 (ⅳ)若,则;
(ⅴ)设是三个整数,且不同时为零。如果,则
。
进一步,若,,则;
(ⅵ)若,,则,;
若,则;
(ⅶ)若,则;
(ⅷ)若,则;
(ⅸ)。
例4 设是两个整数,是素数,若,则。
上述性质对于我们研究整数的性质很有帮助。由性质2(ⅸ)我们可以得到
求任意两个整数和最小公倍数算法