Proof that there exists a smallest positive linear combination?

Click For Summary
SUMMARY

The theorem discussed confirms that for any two nonzero integers a and b, there exists a smallest positive linear combination of a and b. The proof utilizes the Well Ordering Principle, establishing that the set S, defined as S = {w ∈ Natural numbers : w = am + bn}, contains a smallest positive element if it is nonempty. The author questions the necessity of assuming S is nonempty and contrasts this direct proof with a proof by contradiction suggested by their professor.

PREREQUISITES
  • Understanding of number theory concepts, specifically linear combinations.
  • Familiarity with the Well Ordering Principle in mathematics.
  • Basic knowledge of integer properties and sets.
  • Experience with proof techniques, including direct proof and proof by contradiction.
NEXT STEPS
  • Study the Well Ordering Principle in depth to understand its implications in number theory.
  • Explore proof by contradiction techniques and their applications in mathematical proofs.
  • Investigate linear combinations and their significance in algebra and number theory.
  • Review examples of smallest positive integers in various mathematical contexts.
USEFUL FOR

Mathematicians, students studying number theory, and anyone interested in proof techniques and integer properties.

Aziza
Messages
189
Reaction score
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\inNatural 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?
 
Physics news on Phys.org
You really don't have to assume that S is non-empty, as you can easily prove this fact.
 

Similar threads

Undergrad Characterizing linear independence in terms of span
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Confused about small detail in rank-nullity theorem
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Uniqueness of reduced row echelon form (proof verification)
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Proof by induction of block diagonal decomposition of a matrix
  • · Replies 4 ·
Replies
4
Views
2K
MHB Short topical webpage title: Proving Properties of Unital Rings
  • · Replies 1 ·
Replies
1
Views
3K
MHB Linear Maps and Eigenvalues/Eigenvectors
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Questions about non existence of GCDs vs (coimages, cokernels)
  • · Replies 12 ·
Replies
12
Views
1K
Undergrad Definition of minimal ideal using symbolic logic notation
  • · Replies 3 ·
Replies
3
Views
2K
Show that gcd(a,b) is the smallest positive element in the set {ma+nb}
  • · Replies 2 ·
Replies
2
Views
2K
MHB Can a Matrix be Written as a Linear Combination of Another Matrix's Columns?
  • · Replies 2 ·
Replies
2
Views
2K