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