Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof that there exists a smallest positive linear combination?

  1. Oct 31, 2012 #1
    A theorem from number theory states that, if a and b are nonzero integers, then there exists a smallest positive linear combination of a and b.

    This is my proof:

    Let S be a set such that S = {w[itex]\in[/itex]Natural numbers : w=am+bn} , where a and b are positive integers, m and n are any integers, and w is by definition a linear combination of a and b.
    Suppose S is nonempty. Then S is a subset of the natural numbers. Then by the Well Ordering Principle, S has a smallest (positive) element. Thus there exists a smallest positive linear combination of a and b.


    Is this correct? Or am I missing something? My professor said that fastest way to prove this is by contradiction, but it seems to me that just directly proving by the well ordering principle is faster?
     
  2. jcsd
  3. Oct 31, 2012 #2
    You really don't have to assume that S is non-empty, as you can easily prove this fact.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof that there exists a smallest positive linear combination?
  1. Linear Combinations (Replies: 2)

  2. Linear combinations (Replies: 2)

  3. Linear combination (Replies: 1)

  4. Linear Combination (Replies: 2)

Loading...