最大公约数

两个正整数r0和r1的最大公约数表示为： $\gcd(r_0, r_1)$
他指的是被r0和r1同时整除的最大正整数，例如：

$\begin{align} r_0 & = 84, r_1 = 30; \\ \\ r_0 & = 84 = 2*2*3*7 \\ r_1 & = 30 = 2*3*5 \\ \\ \gcd 是所有公共质因子&的乘积：\\ 2*3 & = 6 = \gcd(r_0, r_1) \end{align}$

欧几里得算法

定义

在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。

$假设r_0>r_1：\gcd(r_0, r_1) = \gcd(r_0-r_1, r_1)$

证明

$\begin{align} 假设 \ &\gcd(r_0, r_1) = g \\ \therefore \ &r_0 = g*x,\ r_1 = g*y \\ 易证得 \ &x和y互素 \\ 易证得 \ &x-y和y互素(x>y) \\ \therefore \ &\gcd(r_0-r_1, r_1) = \gcd(g(x-y), gy) = g = \gcd(r_0, r_1) \end{align}$

补充说明

上述r0 = g*x，r1 = g*y；如果x和y不互素，r0和r1的公约数就不是g，而是g*d(d为x和y的公约数)
如果x-y和x不互素，根据反证法得： $\begin{align} 假设md&=(x-y) \\ nd&=y \\ \therefore \ x-y+y&= md+nd \\ x&=(n+m)d \\ \therefore \ x和y不互素，&与上述条件相悖 \\ \therefore \ x-y和y互素，&即\gcd(x-y,y)=1 \end{align}$
扩展定义

根据欧几里得定义可得：

$\gcd(r_0,r_1)=\gcd(r_0-r_1,r_1)=\gcd(r_0-2r_1,r_1)=···=\gcd(r_0-mr_1,r_1)$

只要r0-mr1>0，上述等式依然成立，为了减少计算步骤，每次都可以取使得r0-mr1>0成立的最大的m的值来计算，此时r0-mr1=r0 mod r1，所以欧几里得定理也可以表示为：

$\gcd(r_0,r_1)=\gcd(r_1,r_0 \bmod r_1)$

案例

$\begin{align} \gcd(973, 301) &= \gcd((3*301+70),301) = \gcd(301,70) \\ \gcd(301, 70) &= \gcd((4*70+21), 70) = \gcd(70, 21) \\ \gcd(70, 21) &= \gcd((3*21+7), 21) = \gcd(7, 21) \\ \gcd(21, 7) &= \gcd((7*3+0), 7) = \gcd(7, 0) \\ \gcd(7, 0) & = 7 \\ \\ \therefore \ \gcd(973, 301) &= 7 \end{align}$

实现

def gcd(a, b):
    while a != 0:
        a, b = b % a, a

    return b

扩展欧几里得算法

定义

已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，找到整数x、y（其中一个可能是负数），使它们满足貝祖等式：ax+by=gcd(a,b)

原理

递归原理

$\begin{align} 设 \ ax_1+by_1 & = \gcd(a,b) \\ \ bx_2+(a\%b)y_2 &= \gcd(b, a \% b) \\ \because \ \gcd(a,b) &= \gcd(b, a \% b) \\ \therefore \ ax_1+by_1 & = bx_2+(a\%b)y_2 \\ \because \ a\%b &= a-(a/b)*b \\ 设 \ a/b &= q \quad (整除) \\ \therefore \ ax_1+by_1 & = bx_2+(a-qb)y_2 \\ ax_1+by_1 & = ay_2 + b(x_2-qy_2) \\ \\ 根据恒等定理(a，b前面的&系数相等)： \\ &\begin{cases} x_1 = y_2 \\ y_1 = x_2-qy_2 \\ \end{cases} \\ \vdots \\ 同理可得: \ &\begin{cases} x_{n-1} = y_n \\ y_{n-1} = x_n - qy_n\\ \end{cases} \\ 根据欧几里得定理可得，&\gcd(a,b)经过辗转相除之后, \\ 最终一定会转换为\gcd(a_n,0)&形式，并且此时的a_n=\gcd(a,b) \\ \because \ \gcd(a_n,0) &= a*1+0 \\ \therefore \ &\begin{cases} y_n = 0 \\ x_n = 1 \\ \end{cases} \\ 根据上述x_n和y_n的值，利用&递归可以推出x1和y1的值 \end{align}$

非递归原理

$\begin{align} 根据欧几里得定理： \gcd(a,b)&=\gcd(b,a\bmod b) = gcd(b,a-qb) = \cdots \\ &= gcd(a_n,0) = a_n \\ 我们将上述推导&过程中的gcd中的值抽象出来 \\ 设当x_0=1，y_0=0；&x_1=0，y_1=1时，有如下行列式：\\ &\begin{cases} ax_0 + by_0 = a \\ ax_1 + by_1 = b \\ \end{cases} \\ 根据上述行列&式，带入(b,a-qb) \\ 可推出： &\begin{cases} b = ax_1 + by_1 \\ a-qb = ax_0 + by_0-q(ax_1 + by_1) \\ \end{cases} \\ \implies &\begin{cases} b = ax_1 + by_1 \\ a-qb = a(x_0-qx_1) + b(y_0-qy_1) \\ \end{cases} \\ &\cdots \\ 依次类推：gcd(a_n,0) = a_n &= a(x_{n-2}-qx_{n-1}) + b(y_{n-2}-qy_{n-1}) \\ \\ 所以使用x_0=1，&y_0=0；x_1=0，y_1=1顺序迭代，\\ 每一次迭代利用上&述结论更新a，b前的系数即可， \\ 当b_n = 0的时候停&止，即欧几里得算法结束。 \end{align}$

实现

# 递归的实现方式，利用Xn和Yn的关系正向推导
def ext_euclid(a, b):    
    if b == 0:        
        return 1, 0, a    
    else:        
        # q = gcd(a, b) = gcd(b, a%b)
        x, y, q = ext_euclid(b, a % b)
        x, y = y, (x - (a // b) * y)
        # x*a + y*b = gcd(a,b) = q
        return x, y, q


# 参考资料:
# https://zh.wikipedia.org/zh/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
# https://oi-wiki.org/math/number-theory/gcd/#%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
# 非递归的实现方式
def ext_euclid(a, b):
    old_x, x = 1, 0
    old_y, y = 0, 1
    old_r, r = a, b
    if b == 0:
        # 可省略
        return 1, 0, a
    else:
        while(r!=0):
            q = old_r // r
            old_r, r = r, old_r-q*r
            old_x, x = x, old_x-q*x
            old_y, y = y, old_y-q*y
    # old_x*a + old_y*b = gcd(a,b) = old_r
    return old_x, old_y, old_r