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++

1ll euclid(ll a, ll b) {
2 for (;b;swap(a,b)) {
3 ll k = a/b;
4 a -= k*b;
5 }
6 return a; // gcd(a,b)
7}

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++

1array<ll,3> extendEuclid(ll a, ll b) {
2 array<ll,3> x = {1,0,a}, y = {0,1,b};
3 // we know that 1*a+0*b=a and 0*a+1*b=b
4 for (;y[2];swap(x,y)) { // run extended Euclidean algo
5 ll k = x[2]/y[2];
6 F0R(i,3) x[i] -= k*y[i];
7 // keep subtracting multiple of one equation from the other
8 }
9 return x; // x[0]*a+x[1]*b=x[2], x[2]=gcd(a,b)
10}

Recursive Version

C++

1ll euclid(ll a, ll b) {
2 if (!b) return a;
3 return euclid(b,a%b);
4}

becomes

C++

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

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 NameDifficultyTagsSolution
KattisView Solution

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

C++

1ll invGeneral(ll a, ll b) {
2 array<ll,3> x = extendEuclid(a,b);
3 assert(x[2] == 1); // gcd must be 1
4 return x[0]+(x[0]<0)*b;
5}
6
7int main() {
8 FOR(b,1,101) F0R(a,101) if (__gcd(a,b) == 1) {
9 ll x = invGeneral(a,b);
10 assert((a*x-1)%b == 0);

Application: Chinese Remainder Theorem

StatusSourceProblem NameDifficultyTagsSolution
KattisView Solution
KattisView Solution

Module Progress:

Give Us Feedback on Extended Euclidean Algorithm!

PrevNext