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) {	while (b > 0) {		ll k = a / b;		a -= k * b;		swap(a, b);	}	return a;}

Java

static long euclid(long a, long b) {	while (b > 0) {		long k = a / b;		a -= k * b;
long temp = b;		b = a;		a = temp;	}	return a;}

Python

def euclid(a: int, b: int) -> int:	assert (		int(a) > 0 and int(b) > 0	), "Arguments must be positive, non-zero numeric values."
while b > 0:		k = a // b		# subtract multiples of one equation from the other.		a -= b * k		a, b = b, a
return a

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

Java

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

Python

def extend_euclid(a: int, b: int) -> list[int]:	assert (		int(a) > 0 and int(b) > 0	), "Arguments must be positive, non-zero numeric values."
# we know that 1 * a + 0 * b = a and 0 * a + 1 * b = b.	x_arr = [1, 0, int(a)]	y_arr = [0, 1, int(b)]	q = -1


### Recursive Version

C++

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

Java

static long euclid(long a, long b) {	if (b == 0) { return a; }	return euclid(b, a % b);}

Python

def euclid(a: int, b: int) -> int:	"""Recursive Euclidean GCD."""	return a if b == 0 else euclid(b, a % b)

becomes

C++

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

Java

static long[] extendEuclid(long a, long b) {  // returns {x,y}	if (b == 0) { return new long[] {1, 0}; }	long[] p = extendEuclid(b, a % b);	return new long[] {p, p - a / b * p};}

Python

def extend_euclid(a: int, b: int) -> list[int]:	if not b:		return [1, 0]	p = extend_euclid(b, a % b)	return [p, p - (a // b) * p]

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 inv_general(ll a, ll b) {	array<ll, 3> x = extend_euclid(a, b);	assert(x == 1);  // gcd must be 1	return x + (x < 0) * b;}

Java

static long invGeneral(long a, long b) {	long[] x = extendEuclid(a, b);	assert (x == 1);  // gcd must be 1	return x + (x < 0 ? 1 : 0) * b;}

Python

def inv_general(a: int, b: int) -> int:	"""Returns the modular inverse of two positive, non-zero integer values."""	arr = extend_euclid(a, b)	assert arr == 1, "GCD must be 1."	return arr + (arr < 0) * 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!