algorithm - 极大值丢番图分析

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，但是如果 a-b=c 我得到除数算法返回的 -1 但 gcd(a,- b) 和以前一样。是我的算法错了，还是可以用于a-b=c？

伊恩

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 这失败了 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”