# Proof: no fractions that can't be written in lowest term with Well Ordering Principle

My question is the exact same question as the one in this post but I commented on it but it's from a year ago so I just wanted to bump it and see if I could get a response:

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

I don't understand what the text means by "so by definition of C, there is an integer $n_0 > 0$ such that the fraction ${m_0\over n_0}$ cannot be written in lowest terms. This means that $m_0$ and $n_0$ must have a common prime factor, $p >1$."

If ${m_0\over 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)?

Thanks.

• The fundamental theorem of arithmetic says that if two numbers are not coprime, they have a common prime factor. By definition "lowest terms" means they have a common factor, and some prime divides every positive integer greater than $1$ (i.e. a factor). – Adam Hughes Aug 10 '14 at 18:13
• @AdamHughes Maybe I'm missing something, but isn't that just the definition of coprime? I don't see where the fundamental theorem of arithmetic comes in to play. – Strants Aug 10 '14 at 18:17
• @Strants, actually no, at least not for a proper definition of "coprime," since the FTA comes after things like the Euclidean algorithm for finding a gcd. Usually one defines "coprime" to mean gcd = 1. – Adam Hughes Aug 10 '14 at 18:19
• Thanks for the edits. How can we assume they are not coprime? Where is this constraint in the problem? I looked up coprime and it says that coprime means the only common factors between 2 numbers is 1. – user3761743 Aug 10 '14 at 18:20
• @user3761743 it's a proof by contradiction, so their "assumption" isn't justified, it's part of the proof technique to show "if this were true, something impossible would happen, ergo it's not true." – Adam Hughes Aug 10 '14 at 18:25

That statement is confusing, since the conclusion doesn't need the full strength of the assumptions. Here's what they really mean.

1. If $\frac{m_0}{n_0}$ cannot be written in lowest terms, then certainly $\frac{m_0}{n_0}$ is not already written in lowest terms.
2. And if $\frac{m_0}{n_0}$ is not written in lowest terms, then $m_0$ and $n_0$ have a common prime factor.
• Thanks Chris for simplifying this. – user3761743 Aug 10 '14 at 20:11

Def. From Wolfram: http://mathworld.wolfram.com/ReducedFraction.html

As Adam Hughes said, they're basically doing a proof by contradiction since lowest terms means that the $GCD(m_0, n_0)=1$ and both numerator and denominator have no common factors except for 1. So assuming otherwise means that they share a common factor other than 1.

The Well Ordering Principle hints that if there was a least common factor other than 1 then the factor would have a prime component of 2 (smallest prime) or greater in it's prime decomposition and the fraction wouldn't be written in lowest terms.

Their argument could probably be stated better as Chris said.