python - 求解线性丢番图方程

Question

我正在尝试用 Python 编写算法来求解线性丢番图方程。

我认为我的算法是正确的，因为我已经在论文上对其进行了测试，但是当我运行它时，它会返回奇怪的值。

我的代码：

def solve_Dioph(a,b,c):
    m1=1
    m2=0
    n1=0
    n2=1
    r1=a
    r2=b
    while r1%r2!=0:
        q=r1/r2
        aux=r1%r2
        r1=r2
        r2=aux
        aux3=n1-(n2*q)
        aux2=m1-(m2*q)
        m1=m2
        n1=n2
        m2=aux2
        n2=aux3
    return m2*c,n2*c;

它使用 7 个变量和 3 个辅助变量。用笔和纸对其进行测试后，使用以下值：

a=65 b=14 c=4

我明白了

m2=-3*4 and n2=14*4

但是，当我运行它时：

solve_Dioph(65,14,4)

它返回：

(-227/9, 16393/126)

Answer 1

我猜你正在使用 Python 3（而不是 Python 2）。在 Python 3 中，将两个整数除以/产生浮点结果。但是，您可以使用//运算符强制 Python 2 行为。尝试更改以下行：

q=r1/r2

到：

q=r1//r2