求解线性丢番图方程

Question

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

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

我的代码：

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)

它returns:

(-227/9, 16393/126)

Answer 1

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

q=r1/r2

收件人：

q=r1//r2

求解线性丢番图方程

Solving linear Diophantine equation

python

diophantine