Thread: 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!!!

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 if and only if for some ?

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

Great!! Thanks.