# Math Help - well-ordering principle

1. ## 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

2. It is safe to say $a,b\not = 0$. Consider the set $S=\{ an+bm|n,m\in \mathbb{Z} \}$. Now if $x,y\in S$ then $x+y,x-y\in S$ and $xz\in S$ where $x\in S,z\in \mathbb{Z}$. Since $S$ has a positive element (that is easy to show) it has a least positive element $c$. Now by division algorithm, $a=qc+r$ where $0\leq r < c$. Thus, $r=a-qc \in S$ because of closure properties above. But then $r=0$ because $c$ is least. So $c|a$ similarly $c|b$.