well-ordering principle

• Nov 7th 2007, 01:31 PM
well-ordering principle
Let a and b be positive integers. By the well-ordering principle the non-empty set of positive integers

am+bn such that m,n are integers and am+bn is greater than 0 has a minimum element c. Prove by contradiction that c is a common divisor of a and b
• Nov 10th 2007, 08:09 PM
ThePerfectHacker
It is safe to say $\displaystyle a,b\not = 0$. Consider the set $\displaystyle S=\{ an+bm|n,m\in \mathbb{Z} \}$. Now if $\displaystyle x,y\in S$ then $\displaystyle x+y,x-y\in S$ and $\displaystyle xz\in S$ where $\displaystyle x\in S,z\in \mathbb{Z}$. Since $\displaystyle S$ has a positive element (that is easy to show) it has a least positive element $\displaystyle c$. Now by division algorithm, $\displaystyle a=qc+r$ where $\displaystyle 0\leq r < c$. Thus, $\displaystyle r=a-qc \in S$ because of closure properties above. But then $\displaystyle r=0$ because $\displaystyle c$ is least. So $\displaystyle c|a$ similarly $\displaystyle c|b$.