Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 11 down vote accepted

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

share|cite|improve this answer
    
Thanks for the simple explanation. – CrushedPixel Jan 25 at 12:11
    
@CrushedPixel You're welcome. – SchrodingersCat Jan 25 at 12:12
3  
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 at 14:03
2  
@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 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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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