Implement the Extended Euclid Algorithm and output a b and c

Implement the Extended Euclid Algorithm and output a, b and c = gcd(u,v) for the following inputs: u = 40902 and v = 24149

Solution

here a,b and c is g, x and y .

int gcdExtended(int u, int v, int *x, int *y)
{
    // Base Case
    if (u == 0)
    {
        *x = 0;
        *y = 1;
        return v;
    }

    int x1, y1; //for storing results of recursive call
    int gcd = gcdExtended(v%u, u, &x1, &y1);

    // Updating x and y using results of recursive
    // call
    *x = y1 - (v/u) * x1;
    *y = x1;

    return gcd;
}

int main()
{
    int x, y;
    int u = 40902 , v = 24149;
    int g = gcdExtended(u, v, &x, &y);
    printf(\"gcd(%d, %d) = %d, x = %d, y = %d\",
           u, v, g, x, y);
    return 0;
}