1. ## GCD proof help

Hi everyone, not sure how to do this question.

If gcd(m,n)=1 and p|mq and p|nq then prove that p|q.

Thanks in advance for any help guys.

2. ## Re: GCD proof help

Originally Posted by alexgeek101
Hi everyone, not sure how to do this question.

If gcd(m,n)=1 and p|mq and p|nq then prove that p|q.

Thanks in advance for any help guys.
$\displaystyle gcd(m,n)=1 \Rightarrow \exists x,y \in \mathbb{Z} \, such \, that \, mx+ny=1 \Rightarrow mqx+nqy=q.$
$\displaystyle p|LHS \Rightarrow p|RHS.$

3. ## Re: GCD proof help

If you're working over the integers, here's the intuition: since p|mq, you can imagine taking all the prime factors of p, and dividing as many of them as possible into q, with the remaining ones dividing m. Likewise, the remaining ones divide n, since p|nq. But (m,n)=1, so in fact all the factors of p can be divided into q.