Extended Euclidean Algorithm
Author: Benjamin Qi
?
Prerequisites
Euclidean Algorithm
Resources | ||||
---|---|---|---|---|
cp-algo |
The original Euclidean Algorithm computes and looks like this:
ll euclid(ll a, ll b) {while (b > 0) {ll k = a / b;a -= k * b;swap(a, b);}return 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!
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)}
Recursive Version
ll euclid(ll a, ll b) {if (b == 0) { return a; }return euclid(b, a % b);}
becomes
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};}
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, .
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;}
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!