# For $p, q$ prime, if $q$ divides an integer $n$ but $p$ does not, show that $\text{gcd}(n, p\cdot q) = q$

For $$p, q$$ prime, if $$q$$ divides an integer $$n$$ but $$p$$ does not, show that $$\text{gcd}(n, pq) = q$$

This statement sort of reminds me of Euclid's Lemma, but I haven't been able to progress much.

I tried writing $$n = kq$$ for some integer $$k$$. Then we have $$\text{gcd}(kq, pq)$$, where $$p$$ and $$q$$ are prime. I don't really know how to progress from here.

• q divides n and pq $\implies$ gcd(n,pq) divides q – J. W. Tanner Mar 25 '19 at 4:02
• @J.W.Tanner I believe the right hand part of what you wrote should be "$q$ divides $\gcd(n,pq)$" instead. – John Omielan Mar 25 '19 at 4:08
• @JohnOmielan: Thank you for the correction. I should have said q divides n and pq $\implies$ q divides gcd(n,pq). If I could show also gcd(n,pq) divides q, I'd be done! – J. W. Tanner Mar 25 '19 at 4:10
• gcd(n,pq) divides n and pq; if it divided p it would be 1 or p, but it's not 1 since q divides it, so it would be p, but then we'd have p divides n, which it does not; so we can't have gcd(n,pq) dividing p, so it must divide q – J. W. Tanner Mar 25 '19 at 4:17

Hint: there are only $$4$$ divisors of $$p\cdot q$$. Which could be $$\gcd(n,p\cdot q)$$?
More generally for any $$\,p,q\in\Bbb Z\!:\,$$ $$\, \color{#c00}{(p,n)}=1\,\Rightarrow\, (pq,n) = (q,n),\,$$ because
$$(pq,n) = (pq,nq,n)=(\color{#c00}{(p,n)}q,n) = (q,n)$$