Understanding the Existence and Uniqueness of the GCD

Question

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?

Answer 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.

Answer 2

We are asked to show the existence and uniqueness of the GCD denoted as $c$ of two integers $a,b$. There are two parts of of this proof: Showing the existence and showing the uniqueness. To show the existence we must show there is a $c$ that divides $a,b$ and for any common divisor $d$ of $a,b$, $d|c$.

Part I: Existence

1) Let $S = \{as+bt|s,t \in \mathbb{Z},as+bt > 0\}$. Since $S \neq \emptyset$, by WOP, $S$ has a smallest element $c$, which we will call the GCD.

2) Will now show any divisor $d$ also divided $c$. $c \in S \implies c =ax+by$ and any $d \in \mathbb{Z} \land d|a \land d|b \implies d|(ax+by) \implies d|c$

3) We now show that $c|a$ and $c|b$. If $c$ doesn't divide $a$, then $a = qc + r$ where $q,r \in \mathbb{Z^+} \land 0 < r < c \implies r = a - qc = a - q(ax + by) = a - qax - qby = a(1-qx) + (-qy)b \implies r \in S$ this contradicts that $c$ is the smallest element in $S$. Similar arguments apply for b

4) We have shown $c|a \land c|b \land d|c$ for any divisor $d$ of $a,b$, so now we must show that $c$ is unique.

Part II: Uniqueness

1) If $c_1,c_2$ both satisfy the conditions of GCD, then one is GCD and one is common divisor. If $c_1$ is GCD and $c_2$ is CD, then $c_2|c_1$ the other way around, we have $c_1|c_2$ which means $c_1 = c_2$ because they are both positive.