裴蜀定理 #

裴蜀定理（Bézout 等式（定理）），又称贝祖定理，是一个关于最大公约数的定理

一定存在整数x, y，使ax + by = d成立

推论：

1. 即在所有 ax+by 的整数组合里，那个最小的正数就是 gcd(a,b)
2. a, b互质的充分必要条件是存在整数x, y使ax + by = 1

欧几里得算法 #

欧几里得算法 (Euclidean algorithm) 是数论中最古老、最有用的算法之一。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法（第七卷的命题2中），所以被命名为欧几里得算法。它的特点之一是，它允许我们通过辗转相除法计算最大公约数（gcd），而无需分解因式。

其依赖的核心定理是：

证明：

设 d 为 a 和 b的公约数，即 \( d | a, d | b \)。

根据 \( a = qb + r\)，可得 \( r = a - cb \)。\( d | a , d | b \)可得 \( d | r \)。因此，d也是b和r的公约数。

反向同理，若d是b和r的公约数，同理可证d能整除a。因此，d也是a和b的公约数。

结论：a和b的公约数集合，与b和r的公约数集合完全相同，因此它们的最大公约数必然相等。

计算方法

gcd(a, b) = gcd(b, a mod b) = ... = gcd(?, 0) = ?

求 1997 和 615 两个正整数的最大公约数：
1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1

def gcd(a, b):
    if a == 0:
        return b
 
    return gcd(b % a, a)
 
if __name__ == "__main__":
  a = 10
  b = 15
  print(gcd(a, b)) # 5
 
  a = 1997
  b = 615
  print(gcd(a, b)) # 1
 
  a = 5
  b = 7
  print(gcd(a, b)) # 1

扩展欧几里得算法 #

扩展欧几里得算法是在原有求出最大公约数基础上进行了扩展，根据裴蜀定理：一定存在整数x, y，使ax + by = gcd(a,b)成立），扩展在于不但能求出 d = gcd(a,b)，而且能求出这个特解 x 和 y 。

计算方法

gcd(a, b) = ax1 + by1  
gcd(b, a mod b) = bx2 + (a mod b)y2
...
gcd(?, 0) = ?

ax1 + by1 = bx2 + (a%b) y2
ax1 + by1 = bx2 + (a-(a/b)*b) y2 = ay2 + bx2 -(a/b)*by2

令 [a/b] = k
ax1 + by1 = bx2 + (a-k*b)y2 = ay2 + b(x2-k*y2) = ay2 + b(x2-a/b*y2)
根据恒等定理得：
x1 = y2, y1 = x2 - [a/b]y2，即x1，y1的值基于x2，y2
上面的思想是以递归定义的，递归基为x = 1, y = 0
（即a = gcd(?, 0), b = 0，此a b为x y的系数，gcd = 1*a + 0*b）

求二元一次不定方程252x + 198y = 18的整数解，gcd(252, 198) = 18
252 ÷ 198 = 1 (余 54)
198 ÷ 54 = 3 (余 36)
54 ÷ 36 = 1 (余 18)
36 ÷ 18 = 2 (余 0)
得出gcd(252, 198) = 18

根据递归关系得到以下式子，注意对角线/方向，体现 x1 = y2
18 = [1]*18 + [0]*0
   = [0]*36 + [1 - (36/18)*0]*18        简化0*36 + 1*18
   = [1]*54 + [0 - (54/36)*1]*36        简化1*54 + (-1)*36
   = [-1]*198 + [1 - (198/54)*(-1)]*54  简化(-1)*198 + 4*54
   = [4]*252 + [-1 - (252/198)*4]       简化4*252 + (-5)*198
得出特解x = 4, y = -5

注意x = 4为 252/18 关于模 198/18 的逆元，所以扩展欧几里得算法也可以用来求模逆元
给定整数a,m，若gcd(a,m)=1，则存在且仅存在一个模逆元
扩展欧几里得算法能求出整数x,y 使 ax + my = gcd(a,m) = 1，对 m 取模，得 ax ≡ 1(mod m)，故 x mod m 即为所求逆元

def gcdExtended(a, b):
 
    # Base Case
    if a == 0:
        return b, 0, 1
 
    gcd, x1, y1 = gcdExtended(b % a, a)
 
    # Update x and y using results of recursive call
    x = y1 - (b//a) * x1
    y = x1
 
    return gcd, x, y
 
if __name__ == "__main__":
    a, b = 252, 198
    g, x, y = gcdExtended(a, b)
    print(g, x, y) # (18, 4, -5)