Results 1 to 5 of 5

Math Help - Well ordering property and induction

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by oldguynewstudent View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Thank you for your help so far

    Quote Originally Posted by tonio View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. ordering property of Z
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: January 16th 2012, 03:22 PM
  2. Replies: 1
    Last Post: November 16th 2010, 01:36 AM
  3. Induction and Well Ordering Principle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 8th 2010, 06:09 PM
  4. Well-Ordering Property
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 27th 2010, 01:06 PM
  5. well-ordering <--> induction principle?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 22nd 2010, 04:42 AM

Search Tags


/mathhelpforum @mathhelpforum