Prove that there's no fractions that can't be written in lowest term with Well Ordering Principle

This is from Class Note from 6.042 ocw courses at MIT:

"Well Ordering Principle" section:

( Sorry for not posting latex; I have less than 10 reputations to post images )

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:

So by definition of $C$, there is an integer $n_0 > 0$ such that:

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

Why $\frac{m_0}{n_0}$ cannot be written in lowest terms means $m_0$ and $n_0$ must have a common factor?

What does '$\frac{m_0}{n_0}$ cannot be written in lowest terms' actually means?

I'm not native English speaker so it may be confusing at places to understand the words.

And I don't quite understand this statement, too:

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.

Thanks!

• That $m_0/n_0$ cannot be written in lowest terms means precisely that $m_0$ and $n_0$ have a common factor. For a fraction $m_0/n_0$ to be written in lowest terms means that $\gcd(m_0, n_0)= 1$. – Alex Wertheim Aug 9 '13 at 4:48
• I thought 'm0/n0 cannot be written in lowest terms' means 'it cannot be reduced to lowest terms'. Different from: 'm0/n0 is not in lowest terms' – Hieu Nguyen Aug 9 '13 at 5:02

If $\frac{m}{n}$ cannot be written in lowest terms, this means that for all $m', n'$ such that $\frac{m'}{n'} = \frac{m}{n}$, $m'$ and $n'$ share some common divisor $d > 1$.

The later statement says that if

$$\frac{\frac{m_0}{p}}{\frac{n_0}{p}}$$

can be expressed in lowest terms, as some $\frac{q}{r}$, then as

$$\frac{q}{r} = \frac{\frac{m_0}{p}}{\frac{n_0}{p}},$$

it is also true that

$$\frac{q}{r} = \frac{m_0}{n_0},$$

and so $\frac{q}{r}$ would be an expression of $\frac{m_0}{n_0}$ in lowest terms. Since no such expression can exist, since $m_0 \in C$ and by definition of $C$, there can also be no way to express

$$\frac{\frac{m_0}{p}}{\frac{n_0}{p}}$$

in lowest terms.

• ok now i understsand. thanks! – Hieu Nguyen Aug 9 '13 at 5:20
• can't vote up. i've got less than 15 reputations. sorry – Hieu Nguyen Aug 9 '13 at 5:21
• Sorry this isn't an answer but I'm not able to comment since my reputation is below $50$. Anyway @qalpha or anyone else who understands this: if $m_0$/ $n_0$ cannot be written in lowest terms why is it true that $m_0$ and $n_0$ must have a common prime factor (which excludes $1$ since $1$ isn't prime)? I read through the accepted answer above but I don't think it quite explained this...thanks! – user3761743 Aug 10 '14 at 16:15
• If $m_0$ and $n_0$ do not have a common prime factor, then $m_0/n_0$ is already in lowest terms. – qaphla Aug 11 '14 at 21:07
• I think this answer needs more explanation, it not clear at a go.There is an exact question [here][1]. That answer gives a more intuitive understanding. [1]: math.stackexchange.com/questions/893228/… – Ritu Nov 7 '15 at 7:36