David Xia

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