Prove that gcd(n, mp) = gcd (n, m) if n and p are relatively prime Let $n, m$ and $p$ non-zero natural integers, with $n$ and $p$ relatively prime. Prove that $\gcd(n, mp) = \gcd (n, m)$.
This problem had three questions. First, to prove that if $d$ divides $n$ then $d$ and $p$ are relatively prime. That's done. Second, to prove that an integer $d$ which divides $n$ and $mp$ also divides $m$. Done. I'm left with the third question (the one in the title). I know I'm supposed to use the results I got for the first two, but I just can't seem to connect the dots...

Hint $\ $ If $\rm\:n,mp\:$ and $\rm\:n,m\:$ have the same set D of common divisors, then the also have the same greatest common divisor = max D. $ $  To show they have the same set of common divisors $\rm\:d\in D,\:$ we need to show that $\rm\:d\mid n,mp\iff d\mid n,m,\:$ i.e. if $\rm\:d\mid n\:$ then $\rm\:d\mid mp\iff d\mid m,\:$ which follows by Euclid's Lemma, since you've proven $\rm\:(d,p) = 1.\:$
Remark $\ $ More generally one can prove $\rm\:(mp,n) = (m(p,n),n)\ \ [=\, (m,n)\ \ if\ \ (p,n) = 1]\:$ via
$$\rm if\ \ d\mid n\ \ then\ \ d\mid mp\iff d\mid mp,mn\iff d\mid (mp,mn) = m(p,n)$$
