7
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the simple explanation. $\endgroup$ – CrushedPixel Jan 25 '16 at 12:11
  • $\begingroup$ @CrushedPixel You're welcome. $\endgroup$ – SchrodingersCat Jan 25 '16 at 12:12
  • 3
    $\begingroup$ You don't need to know $\gcd(p,q)=1$. And $p,q$ don't have to be distinct (e.g. if $a=b$). $\endgroup$ – user236182 Jan 25 '16 at 14:03
  • 2
    $\begingroup$ @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. $\endgroup$ – David Z Jan 25 '16 at 15:59
14
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.