Printable View
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
It is safe to say. Consider the set
. Now if
then
and
where
. Since
has a positive element (that is easy to show) it has a least positive element
. Now by division algorithm,
where
. Thus,
because of closure properties above. But then
because
similarly
.