What is the upper bound on the solution we get from Extended Euclidean algo?

Revision en1, by Electr0, 2022-03-21 21:21:48

Lets say we have some equation ax+by = gcd(a,b) . I know that there are infinite number of tuples (x0,y0) such that a*x0 + b*y0 = gcd(a,b). But what is the upper bound on the values of x0 and y0 we get from the Extended Euclidean Algo?

The Extended Euclidean algo i am talking about is

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Electr0 2022-03-21 21:21:48 631 Initial revision (published)