Rare
0/3

# Extended Euclidean Algorithm

Author: Benjamin Qi

?

## Euclidean Algorithm

Resources
cp-algo

The original Euclidean Algorithm computes $\gcd(a,b)$ and looks like this:

C++

ll euclid(ll a, ll b) {	for (;b;swap(a,b)) {		ll k = a/b;		a -= k*b;	}	return a; // gcd(a,b)}

## Extended Euclidean Algorithm

Resources
cp-algo
Wikipedia
cp-algo

The extended Euclidean algorithm computes integers $x$ and $y$ such that

$ax+by=\gcd(a,b)$

We can slightly modify the version of the Euclidean algorithm given above to return more information!

C++

array<ll,3> extendEuclid(ll a, ll b) {	array<ll,3> x = {1,0,a}, y = {0,1,b};	// we know that 1*a+0*b=a and 0*a+1*b=b	for (;y;swap(x,y)) { // run extended Euclidean algo		ll k = x/y;		F0R(i,3) x[i] -= k*y[i];		// keep subtracting multiple of one equation from the other	}	return x; // x*a+x*b=x, x=gcd(a,b)}

### Recursive Version

C++

ll euclid(ll a, ll b) {	if (!b) return a;	return euclid(b,a%b);}

becomes

C++

pl extendEuclid(ll a, ll b) { // returns {x,y}	if (!b) return {1,0};	pl p = extendEuclid(b,a%b); return {p.s,p.f-a/b*p.s};}

The pair will equal to the first two returned elements of the array in the iterative version. Looking at this version, we can prove by induction that when $a$ and $b$ are distinct positive integers, the returned pair $(x,y)$ will satisfy $|x|\le \frac{b}{2\gcd(a,b)}$ and $|y|\le \frac{a}{2\gcd(a,b)}$. Furthermore, there can only exist one pair that satisfies these conditions!

Note that this works when $a,b$ are quite large (say, $\approx 2^{60}$) and we won't wind up with overflow issues.

## Application - Modular Inverse

Resources
cp-algo
StatusSourceProblem NameDifficultyTags
Kattis

It seems that when multiplication / division is involved in this problem, $n^2 < \texttt{LLONG\_MAX}$.

C++

ll invGeneral(ll a, ll b) {	array<ll,3> x = extendEuclid(a,b);	assert(x == 1); // gcd must be 1	return x+(x<0)*b;}
int main() {	FOR(b,1,101) F0R(a,101) if (__gcd(a,b) == 1) {		ll x = invGeneral(a,b);		assert((a*x-1)%b == 0);		assert(0 <= x && x < b);	}}

## Application - Chinese Remainder Theorem

StatusSourceProblem NameDifficultyTags
Kattis
Kattis

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!