# Extended Euclidean algorithm (C Plus Plus)

### From LiteratePrograms

**Other implementations**:**C++**| Python

This article describes a C++ implementation of Extended Euclidean algorithm.

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

*a**x*+*b**y*=*g*=*g**c**d*(*a*,*b*)

The algorithm is better described in the Python version.

## Source

<<eea>>=voideea (inta,intb,int& gcd,int& x,int& y){x=0, y=1;intu=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>usingnamespacestd; eeaintmain(){intgcd, 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;return0;}

## 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).

Download code |