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;
}
