PrevNext
Rare
 0/3

Extended Euclidean Algorithm

Author: Benjamin Qi

?

Edit This Page

Prerequisites

Euclidean Algorithm

Resources
cp-algo

The original Euclidean Algorithm computes gcd(a,b)\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

The extended Euclidean algorithm computes integers xx and yy such that

ax+by=gcd(a,b)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[2] > 0) {
// keep subtracting multiple of one equation from the other
ll k = x[2] / y[2];
for (int i = 0; i < 3; i++) { x[i] -= k * y[i]; }
swap(x, y);
}
return x; // x[0] * a + x[1] * b = x[2], x[2] = 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[2] > 0) {
// keep subtracting multiple of one equation from the other
long k = x[2] / y[2];
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[1], p[0] - a / b * p[1]};
}

Python

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

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 aa and bb are distinct positive integers, the returned pair (x,y)(x,y) will satisfy xb2gcd(a,b)|x|\le \frac{b}{2\gcd(a,b)} and ya2gcd(a,b)|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,ba,b are quite large (say, 260\approx 2^{60}) and we won't wind up with overflow issues.

Application - Modular Inverse

Resources
cp-algo
StatusSourceProblem NameDifficultyTags
KattisN/A

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

C++

ll inv_general(ll a, ll b) {
array<ll, 3> x = extend_euclid(a, b);
assert(x[2] == 1); // gcd must be 1
return x[0] + (x[0] < 0) * b;
}

Java

static long invGeneral(long a, long b) {
long[] x = extendEuclid(a, b);
assert (x[2] == 1); // gcd must be 1
return x[0] + (x[0] < 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[2] == 1, "GCD must be 1."
return arr[0] + (arr[0] < 0) * b

Application - Chinese Remainder Theorem

StatusSourceProblem NameDifficultyTags
KattisN/A
KattisN/A

Module Progress:

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!

PrevNext