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

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

Lemma

$$a{y}^{\prime }+b\left(x^{\prime }-\lfloor \frac{a}{b}\rfloor y^{\prime }\right)=\gcd \{a,b\}$$

Proof

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

1. Applying the lemma yields 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> exgcd(int a, int b) {
	return [&](this 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}$$