
wellordering principle
Let a and b be positive integers. By the wellordering principle the nonempty 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

It is safe to say $\displaystyle a,b\not = 0$. Consider the set $\displaystyle S=\{ an+bmn,m\in \mathbb{Z} \}$. Now if $\displaystyle x,y\in S$ then $\displaystyle x+y,xy\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=aqc \in S$ because of closure properties above. But then $\displaystyle r=0$ because $\displaystyle c$ is least. So $\displaystyle ca$ similarly $\displaystyle cb$.