PrevNext
Rare
 0/3

Extended Euclidean Algorithm

Author: Benjamin Qi

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

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> 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[2];swap(x,y)) { // run extended Euclidean algo
ll k = x[2]/y[2];
F0R(i,3) x[i] -= k*y[i];
// keep subtracting multiple of one equation from the other
}
return x; // x[0]*a+x[1]*b=x[2], x[2]=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 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 NameDifficultyTagsSolutionURL
KattisView Solution

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

C++

ll invGeneral(ll a, ll b) {
array<ll,3> x = extendEuclid(a,b);
assert(x[2] == 1); // gcd must be 1
return x[0]+(x[0]<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 NameDifficultyTagsSolutionURL
KattisView Solution
KattisView Solution

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!

Give Us Feedback on Extended Euclidean Algorithm!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext