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? 


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.
