# A number theory proof - how do I use these intuitions to prove $c^2 \mid ab$?

I've just been introduced to number theory and I had to admit it's a very cool math subfield. Solving problems is another matter entirely, however. Here is the problem:

For positive $a, b, c \in \mathbb{Z}$, prove that if $c = \gcd(a, b)$ then $c^2 \mid ab$.

I began by trying to list all the intuitions I had about the above:

If $c^2 \mid ab$, then $c^2 \mid a$ and $c^2 \mid b$ should also be valid statements, right?

I also feel that $c^2 \mid ab$ would also hold.

I've been introduced to the Euclidean algorithm as well, which means $c = \gcd(a, b)$ would also mean $c = \gcd(b, r)$ ($r$ being the remainder).

So I have a cluster of (what I think are correct) intuitions from the above, but pairing these into something that proves $c^2 \mid ab$ seems daunting. Could someone point me in the right direction so I can begin connecting these dots?

• Have you looked at any examples for $a$ and $b$? – Carsten S Jun 29 '16 at 15:17
• Hint $\ j\mid J,\, k\mid K\,\Rightarrow\, jk\mid JK\$ – Bill Dubuque Jun 29 '16 at 15:17
• the fact that it is a "gcd" is not necessary. It suffices that it is a common divisor. – Andres Mejia Jun 29 '16 at 15:20

If $c^2 \mid ab$, then $c^2 \mid a$ and $c^2 \mid b$ should also be valid statements, right?

Not at all. In fact for $c>1$, it's certain that at least one of these is false; otherwise the $\gcd$ of $a$ and $b$ would be $c^2$, not $c$.

What you do know from $c =\gcd(a,b)$ is that $c \mid a$ and $c \mid b$. And that's how you can deduce that $c^2 \mid ab$.

Hint: If $c$ divides both $a$ and $b$, then we can write $$a = cm$$ and $$b = cn$$ for some $m, n$.

If you multiply these two together a factor of $c^2$ appears on the RHS.

Write down the definitions:

$$\begin{cases}c\,\mid\,a\implies a=xc\\{}\\c\,\mid\,b\implies b=yc\end{cases}\implies ab=xyc^2\implies c^2\,\mid\,ab$$

and since the above is true for any common divisor, it is also true for the greatest common one.