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 .

### Standard Euclidean Algorithm

This algorithm reads *a* and *b* as input, and computes a quotient sequence as well as a remainder sequence . Let , then these sequences meet that

The computation stops when , and .

### Extended Euclidean Algorithm

**Feature** , for .

Let , where . Initially we have . When we look into , we know that

As *a%b = a – a/b*b*, arrange the variables, we obtain that

So

.

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