Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From page 2 of The Prime Facts : from Euclid to AKS by Scott Aaronson :

Thus P/A = R/K. But R is less than P, since it’s a remainder from dividing by P.


So P/A can’t be in lowest terms;

[ Why? ]

something greater than 1 divides both P and A. But nothing divides P except 1 and itself, so P divides A.


I don't see the link between R being less than P, and P/A having to be not in lowest terms, otherwise I follow the argument. Can anyone suggest how I can convince myself?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

If $P/A = R/K$, and $R < P$, then $R/K$ is in lower terms than $P/A$, so the latter cannot be lowest!

So, after discussion in the comments, it transpires that my definition and your definition of "lowest terms" are a bit different. So, here's a bit of work to show they're equivalent:

Definition: a fraction $a/b$ is in lowest terms if there do not exist $c$ and $d$ with $c < a$ and $d < b$ such that $a/b = c/d$.

Remark: of course if $c < a$ then $d < b$, so the "and" above can be replaced with "or".

Theorem: If $a/b$ is in lowest terms, their GCD is 1.

Proof: Otherwise you could cancel their GCD and get a smaller fraction.

Theorem: ("obvious" but still needs proving) For any given fraction $x/y$, there is a fraction in lowest terms equal to it.

Proof: If $x/y$ is in lowest terms, then that's your fraction. Suppose not. By definition, this means there exists $c$ and $d$ with $c < x, d < y$ and $x/y = c/d$. If $c/d$ is in lowest terms, stop. Otherwise, this means there exists an even smaller fraction. Continue in this way – eventually you must stop, because the numerators are getting smaller every time.

Theorem: If $x/y$ is not in lowest terms, then $x$ and $y$ have a common factor.

Proof: By the previous theorem, there is a fraction in lowest terms to which $x/y$ is equal, say $x/y = a/b$. Then $xb = ya$. So $a$ divides $xb$. But we know that the GCD of $a$ and $b$ is 1, so in fact $a$ divides $x$. Likewise, $b$ divides $y$. So $x = ka$ and $y = lb$, so $ka/lb = a/b$. But then $k/l = 1$, so $k = l$. So $k$ is a common factor of $x$ and $y$.

share|improve this answer
Oh, since P must be a multiple of R and A must be a multiple of K, because of the equality? –  Cris Stringfellow Apr 5 '13 at 10:59
That's certainly true. How exactly do you define lowest terms? –  Ben Millwood Apr 5 '13 at 11:02
I suppose there would be not factor common between numerator and denominator. So if there is then it can't be in lowest terms. Okay, thanks for repairing my logical chain, I think I'm convinced. :) –  Cris Stringfellow Apr 5 '13 at 11:03
Wait, that's not quite right. Think of $9/6 = 6/4$. $P$ isn't a multiple of $R$, but that doesn't matter – all that matters is that something can be cancelled from $P/A$ because its terms are not minimal. –  Ben Millwood Apr 5 '13 at 11:11
Okay, if we say that the GCD of the GCD of both denominators and the GCD of both numerators is not 1, I think that settles it. So something can be cancelled from one side, or both sides. So P has a multiple in common with R, and A has a multiple in common with K and these two common multiples have a common multiple, that is not 1, then at least one side is not in lowest terms. Is that right? That sounds more right. I thought it still felt funny. Thanks for pursuing and pointing that out. –  Cris Stringfellow Apr 5 '13 at 11:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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