Rare
0/3

# Extended Euclidean Algorithm

Author: Benjamin Qi

?

## Euclidean Algorithm

Resources
cp-algo

The original Euclidean Algorithm computes $\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

Resources
cp-algo
Wikipedia
cp-algo

The extended Euclidean algorithm computes integers $x$ and $y$ such that

$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=b4    for (;y;swap(x,y)) { // run extended Euclidean algo5        ll k = x/y;6        F0R(i,3) x[i] -= k*y[i];7        // keep subtracting multiple of one equation from the other8    }9    return x; // x*a+x*b=x, x=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 $a$ and $b$ are distinct positive integers, the returned pair $(x,y)$ will satisfy $|x|\le \frac{b}{2\gcd(a,b)}$ and $|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,b$ are quite large (say, $\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, $n^2 < \texttt{LLONG\_MAX}$.

C++

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