1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ q divides n and pq $\implies$ gcd(n,pq) divides q $\endgroup$ – J. W. Tanner Mar 25 '19 at 4:02
  • $\begingroup$ @J.W.Tanner I believe the right hand part of what you wrote should be "$q$ divides $\gcd(n,pq)$" instead. $\endgroup$ – John Omielan Mar 25 '19 at 4:08
  • $\begingroup$ @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! $\endgroup$ – J. W. Tanner Mar 25 '19 at 4:10
  • $\begingroup$ 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 $\endgroup$ – J. W. Tanner Mar 25 '19 at 4:17
0
$\begingroup$

Hint: there are only $4$ divisors of $p\cdot q$. Which could be $\gcd(n,p\cdot q)$?

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy