Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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|cite|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|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.