Implementation of Extended Euclidian theorem
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; }
Here is what the above code is Doing:
1. It’s finding the GCD of a and b.
2. It’s finding the x and y such that ax + by = GCD(a, b).
3. It’s returning the GCD of a and b.