# Thread: Greatest common divisor proof

1. ## Greatest common divisor proof

If gcd(m,n)=1 and gcd(k,n)=1, show that gcd(mk,n)=1.
I have tried approaching it by doing a proof of the contrapositive, but I keep getting stuck..

Let m,k,n be integers such that gcd(mk,n)\neq{1}. Then there exists d>1 such that d=gcd(mk,n). Then, d divides mk and d divides n. So, d divides (mk+n) etc....

any advice on where to go from here?? thanks!!!

2. ## Re: Greatest common divisor proof

Originally Posted by sfspitfire23
If gcd(m,n)=1 and gcd(k,n)=1, show that gcd(mk,n)=1.
I have tried approaching it by doing a proof of the contrapositive, but I keep getting stuck..

Let m,k,n be integers such that gcd(mk,n)\neq{1}. Then there exists d>1 such that d=gcd(mk,n). Then, d divides mk and d divides n. So, d divides (mk+n) etc....

any advice on where to go from here?? thanks!!!
Can you use the fact that $\displaystyle (m,n)=1$ if and only if $\displaystyle mx+ny=1$ for some $\displaystyle x,y\in\mathbb{Z}$?

3. ## Re: Greatest common divisor proof

if we can find integers s,t such that (mk)s + nt = 1, we'll be done.

we know that there exist integers x,y and u,v such that: mx + ny = 1 and ku + nv = 1.

can you see what to do next? hint: 1*1 = 1, so maybe if we multiply...

4. ## Re: Greatest common divisor proof

Great!! Thanks.