# 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?
$\displaystyle n$ is a common divisor of $\displaystyle na$ and $\displaystyle nb$. Suppose now that $\displaystyle \gcd(na, nb) = m > n$. Then, since every common divisor of $\displaystyle na$ and $\displaystyle nb$ is a divisor of $\displaystyle \gcd(na, nb), n|m \Rightarrow np = m$, for some $\displaystyle p > 1$

$\displaystyle \Rightarrow np | na$

$\displaystyle \Rightarrow p|a$ and

$\displaystyle np|nb \Rightarrow p|b$.

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

Therefore $\displaystyle 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!