Решение линейного диофантова уравнения

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 (as o Python 2). В Python 3 целочисленное деление возвращает результат поплавка. Однако вы можете заставить поведение Python 2 использовать оператор //. Попробуйте изменить следующую строку:

q=r1/r2 

To:

q=r1//r2