Well-Ordering Principle to Show All fractions can be written in lowest terms This is from Class Note from 6.042 ocw courses at MIT:
"Well Ordering Principle" section:
You can read the original here at page 1 and 2; Well Ordering Principle: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap03.pdf


In fact, looking back, we took the Well Ordering Principle for granted
  in proving that $\sqrt{2}$ is irrational. That
  proof assumed that for any positive integers $m$ and $n$, the fraction $\frac{m}{n}$
  can be written in lowest terms, that is, in the form $\frac{m'}{n'}$ where $m'$
  and $n'$ are positive integers with no common factors. How do we know
  this is always possible?
Suppose to the contrary that there were $m$, $n$ in $\mathbb{Z}^+$ such that the fraction $\frac{m}{n}$ cannot be written in lowest
  terms. Now let $C$ be the set of positive integers that are numerators
  of such fractions. Then $m$ in $C$, so $C$ is nonempty. Therefore, by Well
  Ordering, there must be a smallest integer, $m_0$ in $C$. So by definition of
  $C$, there is an integer $n_0 > 0$ such that the fraction $\frac{m_0}{n_0}$ cannot be
  written in lowest terms. This means that $m_0$ and $n_0$ must have a common
  factor, $p > 1$. But 
$(\frac{m_0}{p}) / (\frac{n_0}{p}) = \frac{m_0}{n_0}$
so any way of expressing the left hand fraction in lowest terms would
  also work for $\frac{m_0}{n_0}$, which implies the fraction($\frac{m_0}{p}) / (\frac{n_0}{p})$ cannot be in written in lowest terms either.
So by definition of $C$, the numerator, $\frac{m_0}{p}$, is in $C$. But $\frac{m_0}{p} < m_0$,
  which contradicts the fact that $m_0$ is the smallest element of $C$. Since
  the assumption that $C$ is nonempty leads to a contradiction, it follows
  that $C$ must be empty. That is, that there are no numerators of
  fractions that can’t be written in lowest terms, and hence there are
  no such fractions at all.


I don't really understand the part where, the author says:

This means that $m_0$ and $n_0$ must have a common factor, $p > 1$ .

BECAUSE $\frac {m_0}  {n_0}$ is a irreducible fraction, both $m_0$ and $n_0$ have no common factors other than 1. If they had common factors other than one, then $\frac {m_0}  {n_0}$ would not be a irreducible fraction. I think that IT IS NOT THE CASE THAT $m_0$ and $n_0$ must have a common factor, $p > 1$. 
Let that fraction be $2/3$, $2/3$ is irreducible. 2 and 3 have no common factors other than $1$. 
I assume that if a fraction cannot be written in lowest terms, then the fraction is irreducible, i.e. something like one half. 



If you didn't want to access MIT. look no further
 A: $m_0$ and $n_0$ are defined so that $m_0/n_0$ cannot be written in lowest terms. This means by definition that they have a common factor (since if they didn't, then $m_0/n_0$ would already be in lowest terms, so can be written in lowest terms). I think you're confusing 'irreducible' with 'cannot be written in lowest terms'. These are actually quite different and mutually exclusive. (The fact that the second property is a hypothetical one that the author is proving cannot occur, and that no such $m_0$ and $n_0$ actually exist probably makes it more difficult.)
A: The proof is needlessly complex. We claim that every fraction $f$ can be written irreducibly, i.e. $\,f = a/b\,$ where $a,b$ are coprime. Indeed, by well ordering, there exists a representation $ f = a/b $ with $\rm\color{#c00}{least}$ denominator $b$. If $a,b$ were not coprime then we could cancel a common factor $d>1$ from $a,b$ yielding an equal fraction with smaller denominator $b/d < b\,$ contra $\rm\color{#c00}{least}$ness of $b$.
