二進制都有介紹歐氏算法 (Extended Euclidean Algorithm) 找GCD 最大公因素
http://hkgalden.com/view/299783

這個帖需要MathJax for HKGalden: http://hkgalden.com/view/179024

事實上，歐氏算法並不一定找到GCD, 還需要看環境。而這條理論就是 Bézout identity，而這些環境必須是 Bézout domain。
一般上Bézout domain很大，包含 `ZZ`，但就無包括了如`ZZ[2, sqrt(5)]`

Bézout identity 就係講明
如果 `R` 係Bézout domain, `a and b in R`, `gcd(a, b) = d`, 就會有`x and y` 令到 `ax + by = d`。

當然若`R = ZZ_{ > 0 }`, 而 `a = k b + c`, 所以`a(mod b) = c`
上面那條公式一樣是 ` c x +b (k x + y) = d`, 所以在這個domain 中, `gcd( a, b) = gcd( c, b )`, 又可以以繼續計落去。

用Python 來計算`gcd，例 `gcd(100, 20, 80, 200)` :

def gcd(*num):
    import functools
     
    def g(a, b):
        return a if b==0 else g(b, a%b)
    
    return functools.reduce(g, num)

gcd(100, 20, 80, 200)

講到最大公因素，當然有人想計LCM 最細公倍數。但就有以下identity 計到LCM, 就係`gcd(a, b)*lcm(a,b) = |a*b|`。假設 `d = gcd(a, b)`, 所以`a = d*m and b = d*n`，m, n 皆是一個`R`中的元素。明顯見到 `gcd(m, n) = d/d = 1`, 而問題就去到`lcm(m,n)`。
因為`m | lcm(m, n) implies lcm(m, n) = k*m` 以及 `n | lcm(m, n) implies lcm(m, n) = h*n`, 即是 `k*m = h * n`, 我們就得知 `k = h*n/m`。之前已經講明`gcd(m,n) = 1`，唯一可能就只有`h = m, k=n`，所以`lcm(m,n) = |m*n|`。

所以我們可以用Python 來計`lcm`，例 `lcm(100, 20, 80, 200)` :

def lcm(*num):
    import functools
    
    def l(a, b):
        return (a*b)//gcd(a, b)
        
    return functools.reduce(l, num)

lcm(100, 20, 80, 200)



在此提一下幾個特別情況：

`max(a, b) + min(a, b) = a + b`
`max(a, b) - min(a, b) = |a - b|`
`lcm(a, b) * gcd(a, b) = |a*b|`