[轉(zhuǎn)載于] https://thiscute.world/posts/mathematics-in-euclidean-gcd/

很早就學(xué)過歐幾里得算法，但是一直不知道它的原理。幾乎每本算法書都會(huì)提到它，但是貌似只有數(shù)學(xué)書上才會(huì)見到它的原理。。。前段時(shí)間粗粗看了點(diǎn)數(shù)論（《什么是數(shù)學(xué)》），驚訝于這個(gè)原理的奇妙?，F(xiàn)在把它通俗地寫下來，以免自己忘記。歐幾里得算法是求兩個(gè)數(shù)的最大公約數(shù)(Greatest Common Divisor (GCD))的算法，我們首先假設(shè)有兩個(gè)數(shù) 和 ，其中 是不小于 的數(shù)，記 被 除的余數(shù)為 ，那么 可以寫成這樣的形式：
其中 是整數(shù)（我們不需要去管 到底是多少，這和我們的目標(biāo)無(wú)關(guān)）?，F(xiàn)在假設(shè) 和 的一個(gè)約數(shù)為 ，那么 和 都能被 整除，即
和 都是整數(shù)（同樣的，我們只需要知道存在這樣的整數(shù) 和 就行）。這樣可以得出
所以 也能被 整除，一般規(guī)律如下

和 的約數(shù)也整除它們的余數(shù) ，所以 和 的任一約數(shù)同時(shí)也是 和 的約數(shù)。 —— 條件一

反過來可以得出

和 的任一約數(shù)同時(shí)也是 和 的約數(shù)。 ——條件二

這是因?yàn)閷?duì) 和 每一個(gè)約數(shù) ，有
于是有
由條件一和條件二可知

和 的約數(shù)的集合，全等于 和 的約數(shù)的集合。

于是

和 的最大公約數(shù)，就是 和 的最大公約數(shù)。

接下來用遞推法，
余 ，現(xiàn)在設(shè)
余
余
……
余
余

因?yàn)?，可以看出余數(shù) 會(huì)越來越小，最終變成 .
當(dāng) 且 時(shí)，可知 可被 整除（余數(shù)為 嘛）
此時(shí) 和 的約數(shù)就只有： 和 的因數(shù)，
所以他們的最大公約數(shù)就是 ！
所以 就是 和 的最大公約數(shù)。（若 ，則 為最大公約數(shù)）

這個(gè)遞推法寫成c語(yǔ)言函數(shù)是這樣的（比推導(dǎo)更簡(jiǎn)潔…）:

unsigned int Gcd(unsigned int M,unsigned int N){
    unsigned int Rem;
    while(N){
        Rem = M % N;
        M = N;
        N = Rem;
    }
    return Rem;
}

可以發(fā)現(xiàn)這里沒有要求 M>=N，這是因?yàn)槿绻菢?，循環(huán)會(huì)自動(dòng)交換它們的值。

P.S. 此外，還有最小公倍數(shù)(Least Common Multiple (LCM))算法，詳見 GCD and LCM calculator