What’s the greatest common divisor (gcd) of X and Y? It turns out there’s a nice algorithm for calculating this – the Euclidean Algorithm.

Common Divisor Divides Integer Combination

Let $$(D, +, \cdot)$$ be an integral domain.

Let $$c$$ be a common divisor of two elements $$a$$ and $$b$$ of $$D$$, i.e.:

$$ a, b, c \in D: c|a \wedge c|b $$

Then:

$$ \forall p, q \in D: c|(pa + qb) $$

Proof:

$$ \begin{aligned} c|a \implies & \exists x \in D: a = xc\ c|b \implies & \exists y \in D: b = yc\ & \forall p, q \in D: pq + qb = pxc + qyc = (px + qy)c\ \implies & \exists z \in D: pa + qb = zc\ \implies & c | pa + qb \end{aligned} $$

GCD with Remainder

Let $$a, b \in \mathbb{Z}$$.

Let $$p, r, \in \mathbb{Z}$$ such that $$a = qb + r$$.

Then $$\gcd{a, b} = \gcd{b, r}$$.

Proof:

$$ \begin{aligned} \gcd{a, b} & \implies gcd{a, b}|a \land \gcd{a, b}|b\ & \implies \gcd{a, b} | a – qb\ & \implies \gcd{a, b} | r\ & \implies \gcd{a, b} \le \gcd{b, r }\ \ \gcd{b, r} & \implies \gcd{b, r}|b \land \gcd{b, r}|r\ & \implies \gcd{b, r} | qb – r\ & \implies \gcd{b, r} | a\ & \implies \gcd{b, r} \le \gcd{a, b} \end{aligned} $$

And so $$\gcd{a, b} = \gcd{b, r}$$.