Proof that there exists a smallest positive linear combination?

[Aziza]

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$\in$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?

 

[PiAreSquared]

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