裴蜀定理python

裴蜀定理，也叫贝祖定理，是数论中的重要定理，它表明对于任意给定的整数a和b，存在整数x和y，使得ax + by = gcd(a, b)。其中gcd(a, b)表示a和b的最大公约数。

在Python中，可以使用扩展欧几里得算法来求解裴蜀定理。下面是一个示例代码：

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x, y = extended_gcd(b, a % b)
        return gcd, y, x - (a // b) * y

def bezout_coefficients(a, b):
    gcd, x, y = extended_gcd(a, b)
    return x, y

a = 14
b = 30
x, y = bezout_coefficients(a, b)

print(f"The coefficients of {a} and {b} in Bézout's identity are {x} and {y}")

运行以上代码，将输出：

The coefficients of 14 and 30 in Bézout's identity are -2 and 1

这说明14*(-2) + 30*1 = 2，其中2是14和30的最大公约数。

希望这个示例能够帮助你理解如何在Python中使用裴蜀定理。