# Thread: Suppose gcd(a,b) = 1, prove gcd(na,nb) = n

1. ## Suppose gcd(a,b) = 1, prove gcd(na,nb) = n

Suppose gcd(a,b) = 1, prove gcd(na,nb) = n

Any help?

2. ## GCD

Hello qtpipi
Originally Posted by qtpipi
Suppose gcd(a,b) = 1, prove gcd(na,nb) = n

Any help?
$n$ is a common divisor of $na$ and $nb$. Suppose now that $\gcd(na, nb) = m > n$. Then, since every common divisor of $na$ and $nb$ is a divisor of $\gcd(na, nb), n|m \Rightarrow np = m$, for some $p > 1$

$\Rightarrow np | na$

$\Rightarrow p|a$ and

$np|nb \Rightarrow p|b$.

So $p$ is a common divisor of $a$ and $b$. Contradiction, since $\gcd(a,b)=1$.

Therefore $gcd(na, nb) = n$.

3. Thank you thank you!

I have another similar problem:

Prove that gcd(a+b, a-b) = gcd(2a, a-b) = gcd(a+b, 2b)

Any help with this one too??? Thanks!

4. Nevermind I figured it out!