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

Question

GCD(A,B) is Ax + By. So can there be more than one pair of x and y. If yes, how can I find them? I used the following code to find x and 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; 
}

When i tried to run this code for sample input a =10 , b = 9 it gives answer x = 1,y = -1 which is correct but is there any way to find other solution like x = -8 and y = 9 in this case .

Answer 1

This relation corresponds to the Bézout's identity.

All solutions are given by (x + k*b/gcd(a,b), y -k*a/gcd(a,b)), if (x,y) is a particular solution, where k is an arbitrary integer.
The particular (x,y) solution is for example provided by the extended Euclidian algorithm.

The pair (b/gcd(a,b), -a/gcd(a,b)) is the 'smallest' (u,v) pair such that ua + vb = 0.

Source: Wikipedia!