Vtgyjfy

Definitions

For $a,b in mathbb{Z}$, a positive integer $c$ is said to be a common divisor of $a$ and $b$ if $cmid a$ and $cmid 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 $dmid 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,tin 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,tin 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?

This is related to Bezout 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 dmid c_0tag{1}$

On the other hand for $cin 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} Squad$ but $0le 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 $qge 1$ then $cge c_0$ ($qge 0$ integer, and cannot be $0$, else $c=0notin S$). We already know it from the minimum assertion, but it's good to have it back as a verification.

$cin SRightarrow ctext{ is a multiple of }c_0tag{2}$

Using the same method of euclidian 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 $0le r<c_0$ so $r=(1-s_0q)a+(-t_0q)boverset{?}{in} S$ and we conclude like previously, same with $b$.

$a,b text{ are multiples of } c_0tag{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.

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.