Take the 2-minute tour ×
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.

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

 
discard

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.