解线性丢番图方程

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个辅助变量。用笔和纸测试后，使用以下值：

^{pr2}$

我明白了

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

但是，当我运行它时：

solve_Dioph(65,14,4)

它返回：

(-227/9, 16393/126)

Answer 1

我猜您使用的是python3（而不是python2）。在python3中，整数除法返回浮点结果。但是，您可以通过使用//操作符来强制python2的行为。尝试更改以下行：

q=r1/r2

收件人：

^{pr2}$