# Prove that greatest common divisor of two numbers multiplied with itself divides the product of those numbers

$a, b, c \in \mathbb{N}$ if $c$ is the greatest common divisor of $a$ and $b$, $c^2$ divides $a\cdot b$.

$c = \gcd(a, b) \implies c^2|ab$

How would I prove this? I understand why this sentence is true, but can't formulate it in a mathematically correct way.

When we say $c \mid a$ we really mean that $\frac ac$ is an integer. Similarily, $c\mid b$ means that $\frac bc$ is an integer. What can you now say about $\frac{ab}{c^2}$? This really has nothing to do with the "$\operatorname{g}$" in the abbreviation "$\gcd$", only the "$\operatorname{cd}$" part is relevant.

It is very simple.

Since $c=\gcd(a,b)$, so we can write that there exist distinct integers $p,q$ such that $a=cp$ and $b=cq$ where $\gcd(p,q)=1$.

Hence $$ab=cp\cdot cq = c^2 \cdot pq$$

Thus we can conclude that $$c^2 | ab$$

• Thanks for the simple explanation. Jan 25 '16 at 12:11
• @CrushedPixel You're welcome. Jan 25 '16 at 12:12
• You don't need to know $\gcd(p,q)=1$. And $p,q$ don't have to be distinct (e.g. if $a=b$). Jan 25 '16 at 14:03
• @user236182 well, the only way $p$ and $q$ would not be distinct is if $a=b$, in which case by definition $c=a=b$ so $p=q=1$... but like you said, that doesn't affect the validity of the proof. Of course one could argue it's important to at least consider corner cases like this. Jan 25 '16 at 15:59