# Extended Euclidean algorithm (C Plus Plus)

Other implementations: C++ | Python

Given a,b, Find x,y,g that solve the equation:

ax + by = g = gcd(a,b)

The algorithm is better described in the Python version.

## Source

```<<eea>>=
void eea (int a, int b,
int& gcd, int& x, int& y) {
x=0, y=1;
int u=1, v=0, m, n, q, r;
gcd = b;
while (a!=0) {
q=gcd/a; r=gcd%a;
m=x-u*q; n=y-v*q;
gcd=a; a=r; x=u; y=v; u=m; v=n;
}
}
```

The test driver is also given.

```<<eea.cpp>>=
#include <iostream>
using namespace std;
eea
int main() {
int gcd, x, y;
eea(352, 168, gcd, x, y);
cout << x << " " << y << " " << gcd << endl;
eea(168, 352, gcd, x, y);
cout << x << " " << y << " " << gcd << endl;
eea(3458, 4864, gcd, x, y);
cout << x << " " << y << " " << gcd << endl;
return 0;
}
```

## Execution result

```\$ g++ eea.cpp; ./a.out
-10 21 8
21 -10 8
-45 32 38
```
• The first test case shows that -10 *352 + 21 * 168 = 8 and 8 is gcd(352, 168).
• The second result means that the order of input numbers has no significant meaning.
• The last result shows that -45 * 3458 + 32 * 4864 = 38 and 38 is gcd(3458, 4864).