Question
The well-ordering principle can be used to show that there is a unique gcd of two positive integers. Let $a$ and $b$ be positive integers, and let $S$ be the set of positive integers of the form $as+bt$, where $s$ and $t$ are integers.
a) Show that $S$ is non-empty.
b) Use the well-ordering property to show that $S$ has a smallest element $c$.
c) Show that if $d$ is a common divisor of $a$ and $b$, then $d$ is a divisor $c$.
d) Show that $c|a$ and $c|b$.
e) Conclude from (c) and (d) that the greatest common divisor of $a$ and $b$ exists. Finnish the proof by showing that this gcd of two positive integers is unique.
This is my first use of well-ordering principle so I need
confirmation. More about my problem of this question in the section
Problem below.
My Attempt
a) $S$ is non-empty since $s$ and $t$ in $as+bt$ can be any non-negative integers.
b) From (a), since $S$ is non-empty set of positive integers, by Well-Ordering principle there is a least element $c$.
c) Since $d|a$ and $d|b$,
$$a = dk_1, k_1 \in \mathbb{Z}$$
$$b = dk_2, k_2 \in \mathbb{Z}$$
Thus,
$$c = as + bt = (dk_1)s + (dk_2)t = d(k_1s) + d(k_2s) \equiv 0 (\bmod d)$$
d) Suppose $c \nmid a$, then $a = qc + r, 0 < r < c$. Suppose now $r \in S$, this is a contradiction since since we've already established that $c$ is the least element in set $S$.
e)
-
Existence: We have shown a least element $c$ in a non-empty set $S$, such that $c\mid a$ and $c \mid b$. Other divisors such as $d$, divides $a, b, c$, thus $d \leq c$, hence gcd $c$ exist.
-
Uniqueness: Suppose $\exists e \mid \gcd(a, b) = e$ then $$e \mid a, e \mid b \rightarrow e \mid c,$$ which is true if and only if $e \leq c$, considering $\gcd(a, b) = e$, thus $e = c$.
Problem:
(a) and (b) was my very first use of well ordering principle (at least consciously) thus I need confirmation its being used right. (c) I'm quite confident so its unlikely that its wrong. (d) I'm a little shaky on that, is that also a correct use of well ordering principle? (e) I can't find anything wrong with it, but if its wrong just point it out.
Best Answer
For a, you didn't use the well-ordering principle. You showed there was at least one element of $S$ by exhibiting one. It would be a bit better to say "take $s=1, t=0$, then $as+bt=a$, so $S$ is not empty." but you have the idea. b is correct as stated-you used the well ordering principle correctly. c is fine as well. For d you don't justify that $r \in S$, but you can. This is the critical point. You have $r=a-qc$ Now substitute in $c=as+bt$ and you justify what you were assuming.