# Missing one link in logic of basic unique factorization argument

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.

Okay

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.

Okay

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?

-

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

-
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