Proof that there exists a smallest positive linear combination?

  • Thread starter Aziza
  • Start date
  • #1
190
1

Main Question or Discussion Point

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?
 

Answers and Replies

  • #2
You really don't have to assume that S is non-empty, as you can easily prove this fact.
 

Related Threads on Proof that there exists a smallest positive linear combination?

Replies
3
Views
2K
  • Last Post
Replies
15
Views
763
Replies
36
Views
14K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
2K
Replies
6
Views
10K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
3K
Replies
2
Views
2K
  • Last Post
Replies
9
Views
3K
Top