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 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{Z},\forall b\in \mathbb{Z}\setminus \{0\},\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$$

Let $x^{\prime }$ and $y^{\prime }$ be integers such that

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

then applying the lemma yields

$$\begin{array}{rl}b{x}^{\prime }+(a\mathrm{mod}b)y^{\prime }& =\gcd (a,b)\end{array}$$

Since

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

it follows that if $x=y^{\prime }\wedge y=x^{\prime }-\lfloor \frac{a}{b}\rfloor y^{\prime }$, $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.

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

Proof

It is easy to prove that, since the third recursion, $a,b\in \mathbb{N}$ and $a\ge b$.

If $a\in \mathbb{N}$ and $b\in {\mathbb{Z}}^{+}$,

$$\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}$$