Results 1 to 2 of 2

Thread: 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 $\displaystyle a,b\not = 0$. Consider the set $\displaystyle S=\{ an+bm|n,m\in \mathbb{Z} \}$. Now if $\displaystyle x,y\in S$ then $\displaystyle x+y,x-y\in S$ and $\displaystyle xz\in S$ where $\displaystyle x\in S,z\in \mathbb{Z}$. Since $\displaystyle S$ has a positive element (that is easy to show) it has a least positive element $\displaystyle c$. Now by division algorithm, $\displaystyle a=qc+r$ where $\displaystyle 0\leq r < c$. Thus, $\displaystyle r=a-qc \in S$ because of closure properties above. But then $\displaystyle r=0$ because $\displaystyle c$ is least. So $\displaystyle c|a$ similarly $\displaystyle 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, 02:40 PM
  2. Well ordering principle and the maximum principle
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Aug 3rd 2010, 08:31 AM
  3. well ordering principle
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Aug 18th 2009, 02:18 PM
  4. Well-Ordering Principle
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 20th 2009, 10:59 AM
  5. Well ordering principle
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Oct 14th 2007, 07:37 AM

Search Tags


/mathhelpforum @mathhelpforum