Extended Euclidean Algorithm
Author: Benjamin Qi
?
Prerequisites
Euclidean Algorithm
Resources | ||||
---|---|---|---|---|
cp-algo |
The original Euclidean Algorithm computes 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 * ka, b = b, areturn a
Extended Euclidean Algorithm
Resources | ||||
---|---|---|---|---|
cp-algo | ||||
Wikipedia | ||||
cp-algo |
The extended Euclidean algorithm computes integers and such that
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) = barray<ll, 3> x = {1, 0, a};array<ll, 3> y = {0, 1, b};// run extended Euclidean algowhile (y[2] > 0) {// keep subtracting multiple of one equation from the otherll 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 = blong[] x = {1, 0, a};long[] y = {0, 1, b};// run extended Euclidean algowhile (y[2] > 0) {// keep subtracting multiple of one equation from the otherlong 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 and are distinct positive integers, the returned pair will satisfy and . Furthermore, there can only exist one pair that satisfies these conditions!
Note that this works when are quite large (say, ) and we won't wind up with overflow issues.
Application - Modular Inverse
Resources | ||||
---|---|---|---|---|
cp-algo |
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
Kattis | N/A |
It seems that when multiplication / division is involved in this problem, .
C++
ll inv_general(ll a, ll b) {array<ll, 3> x = extend_euclid(a, b);assert(x[2] == 1); // gcd must be 1return 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 1return 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
Resources | ||||
---|---|---|---|---|
cp-algo | ||||
cp-algo |
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
Kattis | N/A | ||||
Kattis | N/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!