欧几里得算法与扩展

求最大公因子

Python代码：

def gcd(a, b):
    if b > a:
        return gcd(b, a)
    if b == 0:
        return a
    return gcd(b, a % b)

原理：

1. 设a > b，a和b的最大公因子为c
2. 如果b为0，则c=a
3. 令a = k*b + r，由于c|a，c|b，故c|r（r=a%b）
4. 可以得出c是b与r的最大公因子，令a, b = b, r，返回第一步

扩展欧几里得算法

定义：ax + by = gcd(a, b)

Python代码：

def ex_gcd(a, b, xa=1, ya=0, xb=0, yb=1):
    if b > a:
        return ex_gcd(a, b)
    if b == 0:
        return a, xa, ya
    k = a // b
    x = xa - k*xb
    y = ya - k*yb
    return ex_gcd(b, a % b, xb, yb, x, y)

原理：

1. 设a>b
2. 根据(a, b)->(b, r1)->(r1, r2)...(rn, 0)，得ri-2 = ki-2 * ri-1 + ri
3. 得ri = ri-2 - ki-2 * ri-1，ki-2 = ri-2 // ri-1
4. 设ri = xi*a + yi*b，根据上一步得xi = xi-2 - ki-2 * xi-1，yi = yi-2 - ki-2 * yi-1
5. 当计算到rn时，xn和yn即为所求的x，y