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} 1:
\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*}
The notation \(m \lvert n\) means that \(m\) evenly divides \(n\). ↩︎