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.
Best Answer
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)$$
This is indeed one form of Euclid's Lemma. The above proof works in any domain where gcd exists (where proofs using unique factorization [e.g. Robert's answer] may fail).