I am in a basic proofs class, and am having trouble with the following question:

Let $a \in \mathbb{Z}$ and let $p$ and $q$ be distinct primes. Show that if $p|a$ and $q|a$, then $pq|a$.

Since we're just starting, we're really only allowed to use the properties of primes and divisibility. However, after trying to prove it directly, through the contrapositive, and through contradiction, I was unable to get to any conclusion; noticeably, I'm not sure where to use the fact that p and q are primes in the question. On a related note: when trying to prove the contrapositive, I have: $$ a \ne pq*k$$ (for any $k \in \mathbb{Z}$). Since $a \ne p(qk)$, why does this not imply that $p$ does not divide $a$ (which is what we want to complete the contrapositive)?

Any and all help is appreciated. Thank you kindly!

  • $\begingroup$ Hint: Use the fact that there is unique factorization into prime elements in $\mathbb{Z}$. $\endgroup$
    – mathma
    Jan 31, 2017 at 16:44
  • $\begingroup$ @mathma I'd say that OP is not allowed to use that. $\endgroup$
    – ajotatxe
    Jan 31, 2017 at 16:45
  • $\begingroup$ Are you allowed to use the Bezout's identity? Or maybe the four numbers theorem? $\endgroup$
    – ajotatxe
    Jan 31, 2017 at 16:47
  • 1
    $\begingroup$ You need to tell us what methods you have available after "just starting". E.g. do you know Euclid's Lemma, or the Bezout gcd identity, or the Prime Divisor Property $p\mid ab\,\Rightarrow p\mid a$ or $p\mid b,\,$ or gcd laws, etc? $\endgroup$ Jan 31, 2017 at 16:49
  • $\begingroup$ @Gizmo. You need something more than the basic divisibility rules. The reason is that there are rings (like $\Bbb Z[\sqrt{-5}]$) where this is not true. $\endgroup$
    – ajotatxe
    Jan 31, 2017 at 16:55

1 Answer 1


How about the following. $p|a,$ so $a=kp$ for some $k\in \mathbb{N}$. Now, $q|a$, so $q|kp$. But $p$ is prime, so $q$ can not divide $p$ because $p\ne q$. Then it must be the case that $q|k$. Then $k=jq$ for some $j\in \mathbb{N}$. Combining these facts, $a=jpq$, and we see that $pq|a$.

  • $\begingroup$ You are using the Prime Divisor Property, and the OP has not yet confirmed knowledge of such - see the comments. $\endgroup$ Jan 31, 2017 at 17:13
  • $\begingroup$ You may be right. I'll leave it here in case it helps. $\endgroup$ Jan 31, 2017 at 17:14
  • $\begingroup$ No, it is impossible to prove using just divisibility properties because it fails in more general domains. $\endgroup$ Jan 31, 2017 at 17:15
  • $\begingroup$ But we're only considering $\mathbb{Z}$, no? $\endgroup$ Jan 31, 2017 at 17:16
  • $\begingroup$ Any proof using only general divisibility properties (i.e. those true in any domain) would imply that it was true in any domain. But it's not. The proof requires using special properties of $\,\Bbb Z,\,$ e.g. that is has (Euclidean) Division with remainder. $\endgroup$ Jan 31, 2017 at 17:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.