Extended Euclidean Algorithm

Description:

Extended Euclidean algorithm finds integer coefficients x and y such that: ax + by = gcd(a, b)

Implementation:

#include <stdio.h>

int gcdExtended(int a, int b, int *x, int *y) {
    // Base Case
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    int x1, y1; // To store results of recursive call
    int gcd = gcdExtended(b % a, a, &x1, &y1);
    // Update x and y using results of recursive
    // call
    *x = y1 - (b / a) * x1;
    *y = x1;
    return gcd;
}
// Example Program
int main() {
    int x, y;
    int a = 35, b = 15;
    int g = gcdExtended(a, b, &x, &y);
    printf("gcd(%d, %d) = %d, x = %d, y = %d", a, b, g, x, y);
    return 0;
}