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

You’ve proved that if $d$ is a common divisor of $n$ and $mp$, then $d\mid m$; since $d\mid n$ as well, it follows that $d$ is a common divisor of $n$ and $m$. In particular, if $d=\gcd(n,mp)$, then $d\mid\gcd(n,m)$. On the other hand, it’s clear that any common divisor of $n$ and $m$ is a common divisor of $n$ and $mp$, so ... ?
