Well-Ordering Principle to Show All fractions can be written in lowest terms

Question

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

Answer 1

$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.)

Answer 2

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$.