CODEWITHSUNDEEP
pythondiophantine
Oscar Martinez
Oscar Martinez

Reputation: 621

Solving linear Diophantine equation

I am trying to code an algorithm in Python in order to solve linear Diophantine equations.

I think my algorithm is correct because I have tested it on a paper, however when I run it, it returns strange values.

My code:

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;

It uses 7 variables and 3 auxiliar variables. After testing it with a pen and a paper, with this values:

a=65 b=14 c=4

I get

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

However, when I run it:

solve_Dioph(65,14,4)

It returns:

(-227/9, 16393/126)

Upvotes: 3

Views: 4329

Answers (1)

Tom Karzes
Tom Karzes

Reputation: 24062

I'm guessing you're using Python 3 (as opposed to Python 2). In Python 3, dividing two integers with / produces a float result. However, you can force the Python 2 behavior by using the // operator. Try changing the following line:

q=r1/r2

To:

q=r1//r2

Upvotes: 4

Related Questions