The Euclidean Algorithm

The Euclidean Algorithm is used to find the greatest common denominator (GCD) of two numbers.

Assume:

\[ \label{eqn:a} a = qb + r \tag{$\star$} \]

\begin{equation} \label{eqn:gcd} \begin{cases} \ gcd(a, 0) = a\\\ gcd(0, b) = b\\\ gcd(a, b) = gcd(b, r) \end{cases} \tag{$\dagger$} \end{equation}

The proof of the third equality in \ref{eqn:gcd} can be made by first proving that:

\begin{align*}\label{eqn:gcd-lemma} \tag{$\ddagger$} gcd(a, b) &= gcd(b, a - b) \\\ &= gcd(a - b, b) \end{align*}

Proof of \ref{eqn:gcd-lemma} ¹:

\begin{align*} gcd(a, b) \lvert a & \implies \exists x \in \mathbb{Z} \textrm{ such that } x \cdot gcd(a, b) = a \\\ gcd(a, b) \lvert b & \implies \exists y \in \mathbb{Z} \textrm{ such that } y \cdot gcd(a, b) = b \\\ \end{align*}

Let

\begin{align*} c &= a - b \\\ &= x \cdot gcd(a, b) - y \cdot gcd(a, b) \\\ &= (x - y) \cdot gcd(a, b) \\\ \end{align*}

which implies that:

\begin{equation} \label{eqn:abc} \tag{$\circ$} gcd(a, b) | c \end{equation}

Further:

\begin{align*} gcd(b, c) \lvert b & \implies \exists m \in \mathbb{Z} \textrm{ such that } m \cdot gcd(b, c) = b \\\ gcd(b, c) \lvert c & \implies \exists n \in \mathbb{Z} \textrm{ such that } n \cdot gcd(b, c) = c \\\ \end{align*}

So:

\begin{align*} c = a - b \iff a &= b + c \\\ &= m \cdot gcd(b, c) + n \cdot gcd(b, c) \\\ &= (m + n) \cdot gcd(b, c) \end{align*}

which implies that:

\begin{equation} \label{eqn:bca} \tag{$\diamond$} gcd(b, c) | a \end{equation}

By definition, \(gcd(a, b) \lvert b\), so together with \ref{eqn:abc} we get that \(gcd(a, b)\) is a common divisor of both \(b\) and \(c\). But since \(gcd(b, c)\) is the greatest such common divisor of \(b\) and \(c\) we must have:

\begin{equation} \label{eqn:leq} \tag{1} gcd(a, b) \leqslant gcd(b, c) \end{equation}

Also by definition, \(gcd(b, c) \lvert b\), so together with \ref{eqn:bca} we get that \(gcd(b, c)\) is a common divisor of both \(b\) and \(a\). But since \(gcd(a, b) = gcd(b, a)\) is the greatest such common divisor of \(b\) and \(a\) we must have:

\begin{equation} \label{eqn:geq} \tag{2} gcd(a, b) \geqslant gcd(b, c) \end{equation}

The inequalities \ref{eqn:leq} and \ref{eqn:geq} give:

\begin{equation} gcd(a, b) = gcd(b, c) = gcd(b, a - b) \end{equation}

thus finalizing the proof of \ref{eqn:gcd-lemma}.

Repeatedly applying \ref{eqn:gcd-lemma} gives:

\begin{align*} gcd(a, b) &= gcd(a - b, b) \\\ &= gcd(a - 2b, b) \\\ &= gcd(a - 3b, b) \\\ & \space \space \vdots \\\ &= gcd(a - qb, b) \\\ & \stackrel{(\ref{eqn:a})}{=} gcd(r, b) \\\ &= gcd(b, r) \qquad \square \end{align*}