Extended Euclidean Algorithm

It’s well known that, the Euclidean algorithm can compute the greatest common divisor of integers a and b, gcd(a,b). The extended Euclidean algorithm is able to compute the coefficients of Bézout’s identity, besides gcd(a,b). The Bézout’s identity is the integer solution (x, y) to the equation ax + by = gcd(a,b).

Standard Euclidean Algorithm

This algorithm reads a and b as input, and computes a quotient sequence q_1,\cdots, q_k as well as a remainder sequence r_0,\cdots, r_{k+1}. Let r_0=a, r_1=b, then these sequences meet that

r_{i-1}=q_i r_i + r_{i+1} \quad \text {and} \quad 0\le r_{i+1} < |r_i|

The computation stops when r_{k+1}=0, and gcd(a, b)=r_{k}.

Extended Euclidean Algorithm

Feature gcd(r_0, r_1) = gcd(r_i, r_{i+1}), for i \le k-1.

Let gcd(a,b) = gcd(a_1, b_1) = gcd(b, a\%b), where a_1 = b, b_1 = a%b. Initially we have ax+by=gcd(a,b). When we look into a_1x_1 + b_1y_1 = gcd(a_1, b_1), we know that
a_1x_1 + b_1y_1 = bx_1 + (a\%b)y_1 = gcd(a,b)

As a%b = a – a/b*b, arrange the variables, we obtain that
a_1x_1 + b_1y_1 = ay_1 + b(x_1-a/b\cdot y_1) = gcd(a,b)

So
x=y_1, y=x_1-a/b\cdot y_1.

Use this knowledge, we can easily write a Recursive program as the following:

int gcdEx(int a, int b, int *x, int *y) 
{
    if(b==0)
    {
        *x = 1,*y = 0;
        return a;
    }
    else
    {
        int r = gcdEx(b, a%b, x, y);
        int t = *x;
        *x = *y;
        *y = t - a/b * *y;
        return r;
    }
}

Leave a Reply

Time limit is exhausted. Please reload CAPTCHA.