Results 1 to 2 of 2

Math Help - well-ordering principle

  1. #1
    Junior Member
    Joined
    Oct 2007
    Posts
    37
    Awards
    1

    well-ordering principle

    Let a and b be positive integers. By the well-ordering principle the non-empty set of positive integers

    am+bn such that m,n are integers and am+bn is greater than 0 has a minimum element c. Prove by contradiction that c is a common divisor of a and b
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    It is safe to say a,b\not = 0. Consider the set S=\{ an+bm|n,m\in \mathbb{Z} \}. Now if x,y\in S then x+y,x-y\in S and xz\in S where x\in S,z\in \mathbb{Z}. Since S has a positive element (that is easy to show) it has a least positive element c. Now by division algorithm, a=qc+r where 0\leq r < c. Thus, r=a-qc \in S because of closure properties above. But then r=0 because c is least. So c|a similarly c|b.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum