extended euclidean algorithm to find x and y
#include <stdio.h>
int extended_gcd(int a, int b, int x, int y) {
if (a == 0) {
*x = 0;
*y = 1;
return b;
}
int x1, y1;
int gcd = extended_gcd(b % a, a, &x1, &y1);
x = y1 - (b / a) x1;
*y = x1;
return gcd;
}
int main() {
int a = 35, b = 15, x, y;
int gcd = extended_gcd(a, b, &x, &y);
printf("GCD of %d and %d is %d\n", a, b, gcd);
printf("x = %d, y = %d\n", x, y);
return 0;
}
Explanation: The extended Euclidean algorithm is a recursive algorithm that finds the greatest common divisor (GCD) of two integers, along with the coefficients x and y such that ax + by = GCD(a, b).
extended_gcd Function: 1. If a is 0, set x to 0, y to 1, and return b. 2. Otherwise, recursively call extended_gcd with arguments (b % a, a, &x1, &y1). 3. Calculate x and y using the values of x1 and y1 obtained from the recursive call. 4. Return the GCD.
Main Function: 1. Declare variables a, b, x, y. 2. Call extended_gcd with arguments a, b, &x, &y and store the result in gcd. 3. Print the GCD and the values of x and y.