3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Adam Hughes Aug 10 '14 at 18:13
  • $\begingroup$ @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. $\endgroup$ – Strants Aug 10 '14 at 18:17
  • 1
    $\begingroup$ @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. $\endgroup$ – Adam Hughes Aug 10 '14 at 18:19
  • $\begingroup$ 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. $\endgroup$ – user3761743 Aug 10 '14 at 18:20
  • $\begingroup$ @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." $\endgroup$ – Adam Hughes Aug 10 '14 at 18:25
3
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Thanks Chris for simplifying this. $\endgroup$ – user3761743 Aug 10 '14 at 20:11
0
$\begingroup$

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.

$\endgroup$

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.