Take the 2-minute tour ×

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

share|improve this question
So, you have proved that if $d=\gcd(n,mp)$, then $d$ divides $m$, so $d$ is a common divisor of $m$ and $n$. There's just a little bit left to do.... –  Gerry Myerson Dec 11 '12 at 23:16

2 Answers 2

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

share|improve this answer

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)$$

share|improve this answer

Your Answer


