Extended Euclidean Algorithm

The Extended Euclidean Algorithm is an algorithm that finds a pair of integers $x$ and $y$ such that $ax+by=\gcd \{a,b\}$ for non-negative integers $a$ and $b$ in $\mathcal{O}(\log a+\log b)$ time and $\mathcal{O}(\log a+\log b)$ space.

Algorithm

Lemma

$$\forall a\in \mathbb{N},\forall b\in {\mathbb{Z}}_{+},\gcd \{a,b\}=\gcd \{b,a\mathrm{mod}b\}$$

0. Solve for $b{x}^{\prime }+(a\mathrm{mod}b)y^{\prime }=\gcd \{b,a\mathrm{mod}b\}$ recursively.

1. $x=y^{\prime },y=x^{\prime }-\lfloor \frac{a}{b}\rfloor y^{\prime }$ is a solution for $ax+by=\gcd \{a,b\}$.

Proof

Applying the lemma yields

$$b{x}^{\prime }+(a\mathrm{mod}b)y^{\prime }=\gcd \{a,b\}$$

Since

$$\begin{array}{rl}b{x}^{\prime }+(a\mathrm{mod}b)y^{\prime }& =b{x}^{\prime }+\left(a-\lfloor \frac{a}{b}\rfloor b\right)y^{\prime }\\ & =a{y}^{\prime }+b\left(x^{\prime }-\lfloor \frac{a}{b}\rfloor y^{\prime }\right)\end{array}$$

it follows that $x=y^{\prime },y=x^{\prime }-\lfloor \frac{a}{b}\rfloor y^{\prime }$ is a solution for $ax+by=\gcd \{a,b\}$.

This algorithm solves the problem in $\mathcal{O}(\log a+\log b)$ time and $\mathcal{O}(\log a+\log b)$ space.

std::pair<int, int> extended_euclidean(int a, int b) {
	return y_combinator([&](auto &&self, int a, int b) -> std::pair<int, int> {
		if (!b) {
			return {1, 0};
		}
	 
		auto [x, y] = self(b, a % b);
		return {y, x - a / b * y};
	})(a, b);
}

Proof

If $b>0$,

$$\begin{array}{rl}a\ge b& ⟺\lfloor \frac{a}{b}\rfloor b>a\mathrm{mod}b\\ & ⟺a-a\mathrm{mod}b>a\mathrm{mod}b\\ & ⟺a\mathrm{mod}b<\frac{a}{2}\end{array}$$