[转载于] https://thiscute.world/posts/mathematics-in-euclidean-gcd/
很早就学过欧几里得算法,但是一直不知道它的原理。几乎每本算法书都会提到它,但是貌似只有数学书上才会见到它的原理。。。前段时间粗粗看了点数论(《什么是数学》),惊讶于这个原理的奇妙。现在把它通俗地写下来,以免自己忘记。欧几里得算法是求两个数的最大公约数(Greatest Common Divisor (GCD))的算法,我们首先假设有两个数 和 ,其中 是不小于 的数,记 被 除的余数为 ,那么 可以写成这样的形式:
其中 是整数(我们不需要去管 到底是多少,这和我们的目标无关)。现在假设 和 的一个约数为 ,那么 和 都能被 整除,即
和 都是整数(同样的,我们只需要知道存在这样的整数 和 就行)。这样可以得出
所以 也能被 整除,一般规律如下
和 的约数也整除它们的余数 ,所以 和 的任一约数同时也是 和 的约数。 —— 条件一
反过来可以得出
和 的任一约数同时也是 和 的约数。 ——条件二
这是因为对 和 每一个约数 ,有
于是有
由条件一和条件二可知
和 的约数的集合,全等于 和 的约数的集合。
于是
和 的最大公约数,就是 和 的最大公约数。
接下来用递推法,
余 ,现在设
余
余
……
余
余
因为 ,可以看出余数 会越来越小,最终变成 .
当 且 时,可知 可被 整除(余数为 嘛)
此时 和 的约数就只有: 和 的因数,
所以他们的最大公约数就是 !
所以 就是 和 的最大公约数。(若 ,则 为最大公约数)
这个递推法写成c语言函数是这样的(比推导更简洁…):
unsigned int Gcd(unsigned int M,unsigned int N){
unsigned int Rem;
while(N){
Rem = M % N;
M = N;
N = Rem;
}
return Rem;
}
可以发现这里没有要求 M>=N
,这是因为如果那样,循环会自动交换它们的值。
P.S. 此外,还有最小公倍数(Least Common Multiple (LCM))算法,详见 GCD and LCM calculator