Well ordering property and induction

**oldguynewstudent** · November 28th 2009, 05:28 PM

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

**tonio** · November 28th 2009, 06:11 PM

Originally Posted by oldguynewstudent

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?

Where is that implied and why would it?? Just take $s=t=1\,\Longrightarrow\,0<as+bt=a+b\in\mathbb{Z}^+ \,\Longrightarrow\,S\neq\emptyset$

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

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

Tonio

**oldguynewstudent** · November 29th 2009, 08:30 AM

Originally Posted by tonio

Fort some $s\,,\,r\in\mathbb{Z}\,,\,c=ar+bt$ , so $r=a-qc=a-q(as+bt)=a(1-qs)+b(qt)\in S$ , since $r>0$ , and since also $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 $S_1$ = { $s_1$ | $s_1$ $\epsilon$ S, $s_1$ $\not=$ c}

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

Now choose $S_2$ = { $s_2$ | $s_2$ $\epsilon$ $S_1$ , $s_2$ $\not=$ $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 $m_1$ and $m_2$ both elements of S that divide a and b. If $m_1$ is less than $m_2$ then $m_1$ could not be the gcd(a,b). If $m_2$ is less than $m_1$ then $m_2$ could not be gcd(a,b). Therefore $m_1$ = $m_2$ . Is this correct?

Thanks again.

**emakarov** · November 30th 2009, 03:23 AM

First, concerning a).

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?

You need to show that there exists an element in $S$ , not that $\{as+bt\mid s,t\in\mathbb{Z}\}$ consists of positive elements or something like that. When you prove existence, you have the right to choose an element. In this case, you can choose $a$ , which belongs to $S$ with $s=1$ , $t=0$ . This is different from when you are proving something for all $s$ and $t$ : then it is your opponent (so to speak; the one who doubts the validity of the statement) and not you who has the right to choose $s$ and $t$ .

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.

You have already shown that it exists: it is $c$ . Indeed, it is a common divisor by d), and every other common divisor $d$ divides $c$ by c), so every other common divisor $d$ does not exceed $c$ .

From part c) we have shown that all elements of S divide a and b.

This is not correct; c) shows that only the smallest element $c$ of $S$ divides $a$ and $b$ . You used the fact that $c$ is the smallest when you proved that the remainder of $a / c$ is 0, since it is smaller than $c$ . Also, e.g., $a\in S$ , but $a$ does not have to divide $b$ .

Finish the proof by showing that this greatest common divisor is unique...
Assume m is not unique, then there are and both elements of S that divide a and b. If is less than then could not be the gcd(a,b). If is less than then could not be gcd(a,b). Therefore = . Is this correct?

You need to show not that the least element of $S$ is unique but that the GCD is unique. Not every common divisor of $a$ and $b$ is in $S$ ; for example, when $a$ and $b$ are both even, then every element of $S$ is even and therefore $1\notin S$ .

But the idea is basically correct. If there are two GCDs, then each of them is $\ge$ than the other, so they are equal.

**oldguynewstudent** · November 30th 2009, 05:03 AM

Originally Posted by emakarov

First, concerning a).
You need to show that there exists an element in $S$ , not that $\{as+bt\mid s,t\in\mathbb{Z}\}$ consists of positive elements or something like that. When you prove existence, you have the right to choose an element. In this case, you can choose $a$ , which belongs to $S$ with $s=1$ , $t=0$ . This is different from when you are proving something for all $s$ and $t$ : then it is your opponent (so to speak; the one who doubts the validity of the statement) and not you who has the right to choose $s$ and $t$ .

You have already shown that it exists: it is $c$ . Indeed, it is a common divisor by d), and every other common divisor $d$ divides $c$ by c), so every other common divisor $d$ does not exceed $c$ .

This is not correct; c) shows that only the smallest element $c$ of $S$ divides $a$ and $b$ . You used the fact that $c$ is the smallest when you proved that the remainder of $a / c$ is 0, since it is smaller than $c$ . Also, e.g., $a\in S$ , but $a$ does not have to divide $b$ .

You need to show not that the least element of $S$ is unique but that the GCD is unique. Not every common divisor of $a$ and $b$ is in $S$ ; for example, when $a$ and $b$ are both even, then every element of $S$ is even and therefore $1\notin S$ .

But the idea is basically correct. If there are two GCDs, then each of them is $\ge$ than the other, so they are equal.

Thank you very much for the excellent advise.

Thread: Well ordering property and induction

LinkBack

Thread Tools

Display

Well ordering property and induction

Thank you for your help so far

Similar Math Help Forum Discussions

ordering property of Z

use the well-ordering property to prove the Principle of Strong induction

Induction and Well Ordering Principle

Well-Ordering Property

well-ordering <--> induction principle?

Search Tags