Results 1 to 8 of 8

Math Help - Well Ordering principle

  1. #1
    Newbie
    Joined
    Jan 2008
    Posts
    15

    Well Ordering principle

    Hi all,

    I am having problem of trying to apply the well ordering principle. I know what it is, but i find it difficult to apply it. If anyone knows of any good website that has a lot of useful information, please do let me know. I do not know where to start working on a solution, and i am terribly lost. Below are my questions:

    Qns 1:
    Use the well-ordering principle to prove that if a and b are positive integers, then there exist integers u,v such that gcd(a,b) = ua+vb.

    Qns 2:
    Let a, b be integers, not both zero, and d be a positive integer. Prove that d=gcd(a,b) iff

    (i) d|a, d|b and
    (ii) for all c element of integers, if c|a and c|b, them c|d.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by shaoen01 View Post
    Hi all,

    I am having problem of trying to apply the well ordering principle. I know what it is, but i find it difficult to apply it. If anyone knows of any good website that has a lot of useful information, please do let me know. I do not know where to start working on a solution, and i am terribly lost. Below are my questions:

    Qns 1:
    Use the well-ordering principle to prove that if a and b are positive integers, then there exist integers u,v such that gcd(a,b) = ua+vb.
    Given positive integer a and b there exists integers q and r such that a=qb+r where 0<=r<b. You need this fact. Now let (a,b) = {ax+by|x,y in Z}. The set (a,b) has a positive number, by well-ordering principle choose the smallest positive number d. Define (d) = {dz|z in Z}. Now claim that (a,b) = (d) by showing each is a subset of the other (this is where you use the first line of this post). Once you show (d) = (a,b) the rest is simple, since a in (d) it means d divides a, since b in (d) it means d divides b. If c is a divisor of a and b then c is a divisor of ax+by thus c is in (a,b) so c is in (d) thus d divides c, which proves d the greatest common divisor.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2008
    Posts
    51
    Induction and Well-Ordering are equivalent, so if you can't figure out how to use well-ordering you should be able to use induction. However it might be easier to do some questions with well-ordering.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2008
    Posts
    15
    ThePerfectHacker:
    Thanks for the help! Can i ask did you use the variable b on purpose in "a=qb+r"? Is there any special significance? Can i ask if the question writes gcd(a,b), is it safe to assume b<a? Thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2008
    Posts
    15
    Quote Originally Posted by shawn View Post
    Induction and Well-Ordering are equivalent, so if you can't figure out how to use well-ordering you should be able to use induction. However it might be easier to do some questions with well-ordering.
    Is there anyway to know in which situation i should use well-ordering or mathematical induction. I have some problems with understanding strong mathematical induction. Thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2008
    Posts
    51
    Quote Originally Posted by shaoen01 View Post
    Is there anyway to know in which situation i should use well-ordering or mathematical induction. I have some problems with understanding strong mathematical induction. Thanks
    You can use either in any case...they are equivalent Although Well-ordering is usually harder to do than strong induction, but for some questions it just makes more sense.

    Here's a little comparison of regular and strong induction that might help you understand it better:
    Strong induction versus weak induction

    And here's a link that might help clarify the well-ordering principle: Well Ordering Principle

    Hope it helps.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2008
    Posts
    15
    Shawn:
    Thanks for the links, based on my understand strong mathematical induction requires the step of proving by introducing another variable. So instead of one variable b, we have another additional variable a. So if "a value"<=a<b, so if all values of a is true, then b will also be true considering that b>a right? Hope that makes some sense ...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Feb 2008
    Posts
    51
    Quote Originally Posted by shaoen01 View Post
    Shawn:
    Thanks for the links, based on my understand strong mathematical induction requires the step of proving by introducing another variable. So instead of one variable b, we have another additional variable a. So if "a value"<=a<b, so if all values of a is true, then b will also be true considering that b>a right? Hope that makes some sense ...
    Yes, you introduce another "dummy variable"...in your inductive step you have to assume that it is true for all values of k before k+1, not just for k.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Well ordering principle and the maximum principle
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: August 3rd 2010, 09:31 AM
  2. well ordering principle
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: August 18th 2009, 03:18 PM
  3. Well-Ordering Principle
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 20th 2009, 11:59 AM
  4. well-ordering principle
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 10th 2007, 09:09 PM
  5. Well ordering principle
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 14th 2007, 08:37 AM

Search Tags


/mathhelpforum @mathhelpforum