9
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Alex Wertheim Aug 9 '13 at 4:48
  • $\begingroup$ 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' $\endgroup$ – Hieu Nguyen Aug 9 '13 at 5:02
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ok now i understsand. thanks! $\endgroup$ – Hieu Nguyen Aug 9 '13 at 5:20
  • $\begingroup$ can't vote up. i've got less than 15 reputations. sorry $\endgroup$ – Hieu Nguyen Aug 9 '13 at 5:21
  • $\begingroup$ 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! $\endgroup$ – user3761743 Aug 10 '14 at 16:15
  • $\begingroup$ If $m_0$ and $n_0$ do not have a common prime factor, then $m_0/n_0$ is already in lowest terms. $\endgroup$ – qaphla Aug 11 '14 at 21:07
  • $\begingroup$ 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/… $\endgroup$ – Ritu Nov 7 '15 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.