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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.