1

我在 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？

伊恩

4

1 回答 1

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 这失败了 Bezout 的身份 ax+by 是 gcd(a,b)"

此外，如果您正在尝试实现算法的特定语句，您能否在此处链接或复制它。

OP回复：“ http://mvngu.wordpress.com/2009/08/25/elementary-number-theory-using-maxima/的代码”

一件可能的事情：该mod函数的行为是否符合您的预期？

OP 回复：“mod(5,7) 是，mod(5,-7) 是 -2”

于 2014-07-08T23:27:25.773 回答