Extended Euclid Algorithm Help

[Ocine]

I am trying to implement a code for Extended Euclid Algorithm that takes the input of two values (u,v) and provides the gcd as well as a and b. I think the code is right. I know that the gcd is right because I double checked it against a gcd code, but I'm unsure if my a and b outputs are right. Does this look right?

#include <iostream>
#include <tuple>		
using namespace std;


tuple<int, int, int> extended_gcd(int u, int v)
{
	if (u == 0)
		return make_tuple(v, 0, 1);

	int gcd, x, y;

	
	tie(gcd, x, y) = extended_gcd(v % u, u);

	return make_tuple(gcd, (y - (v/(u * -1)) * x), x);
}


int main()
{
	int u = 612898;
	int v = 765051;

	tuple<int, int, int> t = extended_gcd(u, v );
	
	int gcd = get<0>(t);
	int x = get<1>(t);
	int y = get<2>(t);
	
	cout << "GCD is " << gcd << endl;
	cout << "a = " << x << " b = " << y << endl;

	cout << u << "*" << x << " + " << v << "*" << y << " = " << gcd;
printf("\n");

	return 0;
}

	

[Ganado]

It isn't correct, I mean just look at it:

612898*176 + 765051*141 = 2143

However, it's been a while since I did this in my math class, but I think you're close. It turns out that 215742239 is in fact a multiple of 2143. You're getting a solution (mod 2143) but it's not the solution that satisfies the following:
ax + by = gcd(a, b)
|x| < |b / gcd(a, b)|
|y| < |a / gcd(a, b)|

My hint would be that x or y could be negative in order to make the equality ux + vy == gcd be true.

Have you tried doing the extended euclidean algorithm on paper first, with smaller numbers? That's how I learned it (and then subsequently forgot after 2 years of not using it).

Note that the following does satisfy this:

612898*(-176) + 765051*(141) = 2143

[Ocine]

Thank you for looking at it. I had -176 at first, but I thought both numbers had to be positive (or, well absolute values). I will try it on paper to make sure of the answer.

Thank you again.