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

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. – CrushedPixel Jan 25 '16 at 12:11
• @CrushedPixel You're welcome. – SchrodingersCat 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$). – user236182 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. – David Z Jan 25 '16 at 15:59

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.