扩展欧几里德定理 - 两个数字 A 和 B 是否可以有不止一对 x 和 y

Question

GCD(A,B) 是 Ax + By。那么是否可以有不止一对x和y。如果是，我怎样才能找到它们？我使用以下代码查找 x 和 y :

pair< int ,  int>* extendedeuclid( int a,  int b){
    if(b == 0){
        pair< int,  int>* newpair = new pair< int, int>;
        newpair->first = 1;
        newpair->second = 0;
        return newpair;
    }
    pair< int, int>* oldpair = extendedeuclid(b , a%b);
    pair< int, int>* newpair = new pair< int, int>;
    newpair->first = oldpair->second;
    newpair->second = oldpair->first - ((a/b) * oldpair->second);
    return newpair; 
}

当我尝试运行此示例输入代码时 a =10 , b = 9 它给出的答案 x = 1,y = -1 是正确的，但在这种情况下有没有办法找到其他解决方案，如 x = -8 和 y = 9 .

Answer 1

这个关系对应于 Bézout 的身份。

所有解都由(x + k*b/gcd(a,b), y -k*a/gcd(a,b))给出，如果(x,y)是一个特解，其中k是一个任意整数。
例如，特定的 (x,y) 解决方案由扩展欧几里得算法提供。

对 (b/gcd(a,b), -a/gcd(a,b)) 是 'smallest' (u,v) 对 ua + vb = 0.

来源：维基百科！

扩展欧几里德定理 - 两个数字 A 和 B 是否可以有不止一对 x 和 y

Extended Euclid Theorem - Can there be more than one pair of x and y for two numbers A and B

c++

math

number-theory