Understanding the Existence and Uniqueness of the GCD

Definitions

For $a,b \in \mathbb{Z}$, a positive integer $c$ is said to be a common divisor of $a$ and $b$ if $c\mid a$ and $c\mid b$.

$c$ is the greatest common divisor of $a$ and $b$ if it is a common divisor of $a,b$ and for any common divisor $d$ of $a$ and $b$, we have $d\mid c$.

The Proof

For all $a,b \in \mathbb{Z^{+}}$ there exists a unique $c \in \mathbb{Z^{+}}$, that is the greatest common divisor of $a,b$.

Let $S = \{as + bt: s,t\in \mathbb{Z}, as+bt > 0\}$. Since $ S \neq \emptyset$, then by the WOP, S has a least element $c$. We claim $c$ is a greatest common denominator of $a,b$.

My Problem

$S = \{as + bt: s,t\in \mathbb{Z}, as+bt > 0\}$. I have no idea what this has to do with the greatest common divisor. I understand the WOP ensures the existence of a smallest element, but why can I just claim this as the GCD?

Solution 1:

This is related to Bézout identity.

Let $c_0=as_0+bt_0=\min(S)\tag{0}$

Then if $d$ is a common divisor of $a,b$ then $a=da'$ and $b=db'$ we have $as_0+bt_0=d(a's_0+b't_0)=c_0$

$\text{d divides a,b}\Rightarrow d\mid c_0\tag{1}$

On the other hand for $c\in S$, we have $c=as+bt=c_0q+r=(as_0+bt_0)q+r$

So $r=(s-s_0q)a+(t-t_0q)b\ \overset{?}{\in} S\quad$ but $0\le r<c_0$ by euclidian division definition.

If $r>0$ this contradict the fact that $c_0$ is $\min(S)$, so $r=0$ and $c=c_0q$

Note: since $q\ge 1$ then $c\ge c_0$ ($q\ge 0$ integer, and cannot be $0$, else $c=0\notin S$). We already know it from the minimum assertion, but it's good to have it back as a verification.

$c\in S\Rightarrow c\text{ is a multiple of }c_0\tag{2}$

Using the same method of euclidean division by $c_0$, we can show that $a$ and $b$ are also multiples of $c_0$. (note: $q,r$ are dummy variables, they are not the same than previously).

$a=c_0q+r=(as_0+bt_0)q+r$ with $0\le r<c_0$ so $r=(1-s_0q)a+(-t_0q)b\overset{?}{\in} S$ and we conclude like previously, same with $b$.

$a,b\ \text{ are multiples of } c_0\tag{3}$

Combining $(0),(1),(2),(3)$ we proved that $c_0=\gcd(a,b)$ and that $c_0$ is the smallest number reachable by a relation of type $S$ whose elements are all multiples of $c_0$.

To put this in everyday words: if two numbers are multiple of $3$ for instance, then their sum and their difference is also a multiple of $3$. Plus if they are not equal, the smallest possible difference is $3$.

Replace $3$ by $\gcd(a,b)$ and this is exactly what is mathematically written above.