Диофантовый анализ в максимумах

Question

Я определил расширенный евклидов алгоритм в Maxima как

ext_euclid(a,b):=block(
                   [x,y,d,x_old,y_old,d_old],
                    if b = 0 then return([1,0,a])
                             else ([x_old,y_old,d_old]:ext_euclid(b,mod(a,b)),
                                  [x,y,d]:[y_old,x_old-quotient(a,b)*y_old,d_old],
                                  return([x,y,d])));

чтобы решить линейные диофантовы уравнения вида a+b=c, где gcd(a,b)=1, однако, если ab = c, я получаю -1, возвращаемый алгоритмом для делителя, но gcd(a,-b) как до. Мой алгоритм неверен или его можно использовать для ab = c?

Iain

Answer 1

Я не совсем понимаю, в чем проблема. Можете ли вы привести два примера: один, в котором результат соответствует ожидаемому, а другой - нет (и, пожалуйста, скажите, каков ваш ожидаемый результат в этом случае).

РЕДАКТИРОВАТЬ: OP отвечает: "для решения 5x+7y это 23 ext_euclid (5,7) возвращает [3,-2,1], где gcd (5,7) равен 1, но для 5x-7y равен 23 ext_euclid(5,-7) возвращает [-3,1,-1], но gcd (5, -7) по-прежнему равен 1, это не соответствует идентичности топора Безу + по gcd (a, b)"

Также, если вы пытаетесь реализовать конкретную формулировку алгоритма, можете ли вы дать ссылку на нее или скопировать ее здесь.

ОП отвечает: "код на http://mvngu.wordpress.com/2009/08/25/elementary-number-theory-using-maxima/"

Одна возможная вещь, чтобы посмотреть на: mod Функция ведет себя так, как вы ожидаете?

ОП отвечает: "мод (5,7), мод (5, -7) -2"