什么算法用于求解线性丢番图方程:ax + by = c

Question

我在这里寻找整数解决方案.我知道它有从第一对解和gcd(a,b)| c得到的无限多解.但是,我们怎样才能找到第一对解决方案？有没有算法来解决这个问题？

谢谢,
陈

Answer 1

请注意,并不总是有解决方案.事实上,只有一个解决方案,如果c是一个倍数gcd(a, b).

也就是说,你可以使用扩展的欧几里德算法.

这是一个实现它的C++函数,假设c = gcd(a, b).我更喜欢使用递归算法:

function extended_gcd(a, b)
    if a mod b = 0
        return {0, 1}
    else
        {x, y} := extended_gcd(b, a mod b)
        return {y, x-(y*(a div b))}

int ExtendedGcd(int a, int b, int &x, int &y)
{
    if (a % b == 0)
    {
        x = 0;
        y = 1;
        return b;
    }

    int newx, newy;
    int ret = ExtendedGcd(b, a % b, newx, newy);

    x = newy;
    y = newx - newy * (a / b);
    return ret;
}

现在,如果你有c = k*gcd(a, b)使用k > 0,该公式变为:

ax + by = k*gcd(a, b) (1)
(a / k)x + (b / k)y = gcd(a, b) (2)

所以,只要找到你的(2),或者找到(1)解决方案和繁殖的解决方案x,并y通过k.