# 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;
}
}