Let \(a,b \in \mathbb{Z}\), not both zero. \(\gcd (a,b)\) is the greatest value \(d\) such that \(d|a\), \(d|b\).
greatest common divisor is a linear combination
We can write \(\gcd (a,b) = as+bt\) for some \(s,t \in \mathbb{Z}\).
Let us define:
\begin{equation} S = \{am + bn: m,n \in \mathbb{Z}, am+bn > 0\} \end{equation}
We will first check that \(S\) is non-empty. To do so, let \(a\) be negative and \(b\) be positive. Then, set \(m = -1\), \(n = 1\). We can see that \(am + bn > 0\), satisfying the conditions of the set. In a similar manner, we can demonstrate that regardless of the choice of \(a, b\), \(S\) is non-empty.
Furthermore, integral linear combinations are integers, so \(S\) is a non-empty subset of \(\mathbb{Z}\).
We can now invoke WOP. There is some smallest \(d \in S\). Let’s call \(d = as +dt\). We desire that \(d\) is actually \(\gcd (a,b)\).
\(d\) is a common divisor of \(a,b\)
WLOG write some:
\begin{equation} a = dq + r \end{equation}
using division algorithm. Because \(d \in S\), we can write now:
\begin{equation} a = (as+bt) q + r \end{equation}
We desire that now \(r = 0\) so that we can write \(d|a\). We can write:
\begin{equation} r = a-dq \end{equation}
(notice! \(a\) is a linear combination of \(a,b\), and \(d\) is given to be such)
\begin{equation} r = a-dq = (1a + 0b) - (as+bt)q = a(1-qs) + b(-tq) \end{equation}
Recall that \(r < d\) because \(r\) is a remainder. And of course \(r\) is defined to be positive or \(0\) by the division algorithm.
So:
\begin{equation} 0 \leq a(1-qs) + b(-tq) <d \end{equation}
Now, you will note this middle thing, which is equal to \(r\), is itself a positive linear combination of \(a,b\). Furthermore, it is smaller than \(d\). We already have that \(d\) is the smallest element of \(S\), which means the only other value \(r\) can take on is \(0\).
This leads to conclude:
\begin{equation} a = dq + 0 \end{equation}
so \(d|a\), WLOG \(d|b\).
\(d\) is the greatest common divisor
Proof:
Let \(d’\) be a common divisor of \(a,b\). This means there are some \(m’, n’\) such that:
\begin{align} a &= d’ m’ \\ b &= d’ n' \end{align}
Recall that \(d = as + bt\). This means:
\begin{equation} d = as + bt = (d’ m’)s + (d’ n’)t = d’ (m’ s + n’ t) \end{equation}
This means that \(d’ | d\). Now, \(d \in S\), and everything in \(S\) is positive. Therefore, \(d\) must be the greatest common divisor because it is divisible (and therefore bigger in magnitude than) any \(d’\).
Which means that \(d\) must be the greatest common divisor