Proof that there exists a smallest positive linear combination?

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.
 

Thread 'Trouble understanding an online solution to an exercise in Dummit & Foote'

##\textbf{Exercise 10}:## I came across the following solution online: Questions: 1. When the author states in "that ring (not sure if he is referring to ##R## or ##R/\mathfrak{p}##, but I am guessing the later) ##x_n x_{n+1}=0## for all odd $n$ and ##x_{n+1}## is invertible, so that ##x_n=0##" 2. How does ##x_nx_{n+1}=0## implies that ##x_{n+1}## is invertible and ##x_n=0##. I mean if the quotient ring ##R/\mathfrak{p}## is an integral domain, and ##x_{n+1}## is invertible then...
View full post »

Thread 'Questions about non existence of GCDs vs (coimages, cokernels)'

The following are taken from the two sources, 1) from this online page and the book An Introduction to Module Theory by: Ibrahim Assem, Flavio U. Coelho. In the Abelian Categories chapter in the module theory text on page 157, right after presenting IV.2.21 Definition, the authors states "Image and coimage may or may not exist, but if they do, then they are unique up to isomorphism (because so are kernels and cokernels). Also in the reference url page above, the authors present two...
View full post »

Thread 'Decomposition into irreps of compact Lie group'

When decomposing a representation ##\rho## of a finite group ##G## into irreducible representations, we can find the number of times the representation contains a particular irrep ##\rho_0## through the character inner product $$ \langle \chi, \chi_0\rangle = \frac{1}{|G|} \sum_{g\in G} \chi(g) \chi_0(g)^*$$ where ##\chi## and ##\chi_0## are the characters of ##\rho## and ##\rho_0##, respectively. Since all group elements in the same conjugacy class have the same characters, this may be...
View full post »

Similar threads

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

Hot Threads

Recent Insights

Back
Top