Well ordering property and induction

From ROSEN, section 4.2, problem 36

The well-ordering property can be used to show that there is a unique greatest common divisor of two positive integers. Let a and b be positive inteters, and let S be the set of postive integers of the form as + bt, where s and t are intergers.

a) Show that S is nonempty.

Since a, b, s, and t are integers and the set of integers is closed under addition and multiplication, as + bt must be an integer.

*My question is this: Is it implied that s and t are ***POSITIVE** integers. If s and t were both negative integers, then S could be empty. Could someone explain what I'm missing?

b) Use the well ordering property to show that S has a smallest element c.

Since S was proved to be non-empty in a), then by the well ordering property, S must contain a smallest element since S is a set of positive integers. Call that element c.

c) Show that if d is a common divisor of a and b, then d is a divisor of c.

Since c is an element of S and all elements of S have the form as + bt, then by the theorem (that if d divides a and d divides b then d divides a + b) we show that d divides c.

d) Show that c divides a and c divides b.

Assume that c does not divide a, then a = qc + r where 0 < r < c.

*I am stuck proving that r is an element of S, and I don't see how this contradicts the choice of c. I see that r is a positive integer, but how is it of the form as + bt?*

*Thanks*

Thank you for your help so far

Quote:

Originally Posted by

**tonio** Fort some $\displaystyle s\,,\,r\in\mathbb{Z}\,,\,c=ar+bt$ , so $\displaystyle r=a-qc=a-q(as+bt)=a(1-qs)+b(qt)\in S$ , since $\displaystyle r>0$ , and since also $\displaystyle r < c$ we get here a contradiction to the minimality of c in S.

Tonio

Tonio, thank you for all the help. It is greatly appreciated.

I forgot about part e), would you verify that my reasoning is correct?

e) Conclude from (c) and (d) that the greatest common divisor of a and b exists. Finish the proof by showing that this greatest common divisor is unique.

From part c) we have shown that all elements of S divide a and b. Also S is not empty from part a), therefore there is a common divisor of a and b.

If c is the minimum element of S then choose $\displaystyle S_1$ = {$\displaystyle s_1$ | $\displaystyle s_1$ $\displaystyle \epsilon$ S, $\displaystyle s_1$ $\displaystyle \not=$ c}

Then by the well ordering property, there is an element $\displaystyle c_1$ $\displaystyle \epsilon$ $\displaystyle S_1$ that is the smallest element of $\displaystyle S_1$. Since $\displaystyle c_1$ $\displaystyle \epsilon$ S, $\displaystyle c_1$ | a and $\displaystyle c_1$ | b.

Now choose $\displaystyle S_2$ = {$\displaystyle s_2$ | $\displaystyle s_2 $ $\displaystyle \epsilon$ $\displaystyle S_1$, $\displaystyle s_2$ $\displaystyle \not=$ $\displaystyle c_1$}

Keep choosing subsets until only one element is left. That one element is gcd(a,b), call it m.

*The only thing I can come up with to prove m is unique is the following:*

*Assume m is not unique, then there are $\displaystyle m_1$ and $\displaystyle m_2$ both elements of S that divide a and b. If $\displaystyle m_1$ is less than $\displaystyle m_2$ then $\displaystyle m_1$ could not be the gcd(a,b). If $\displaystyle m_2$ is less than $\displaystyle m_1$ then $\displaystyle m_2 $ could not be gcd(a,b). Therefore $\displaystyle m_1$ = $\displaystyle m_2$. Is this correct?*

*Thanks again.*