不定方程求解py

不定方程是指形如 ax + by = c 的方程，其中 a、b、c 为已知整数，而 x、y 为未知整数。求解不定方程的一种常用方法是通过扩展欧几里得算法。

下面是求解不定方程的 Python 代码实现：

def gcd_extended(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = gcd_extended(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

def solve_diophantine(a, b, c):
    gcd, x1, y1 = gcd_extended(a, b)
    if c % gcd != 0:
        return None
    else:
        x0 = x1 * (c // gcd)
        y0 = y1 * (c // gcd)
        return x0, y0

其中，gcd_extended 函数用于求解 a 和 b 的最大公约数，并返回扩展欧几里得算法中的 x1 和 y1；solve_diophantine 函数则用于解不定方程。如果方程有解，该函数返回 x0 和 y0，否则返回 None。

例如，假设我们要求解方程 21x + 15y = 9，可以调用 solve_diophantine 函数：

>>> solve_diophantine(21, 15, 9)
(-8, 12)

因此，方程的一组解为 x = -8，y = 12。