[转载于] 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
