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.