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 '17 at 16:44
  • $\begingroup$ @mathma I'd say that OP is not allowed to use that. $\endgroup$ – ajotatxe Jan 31 '17 at 16:45
  • $\begingroup$ Are you allowed to use the Bezout's identity? Or maybe the four numbers theorem? $\endgroup$ – ajotatxe Jan 31 '17 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$ – Bill Dubuque Jan 31 '17 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 '17 at 16:55

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$ – Bill Dubuque Jan 31 '17 at 17:13
  • $\begingroup$ You may be right. I'll leave it here in case it helps. $\endgroup$ – Antonios-Alexandros Robotis Jan 31 '17 at 17:14
  • $\begingroup$ No, it is impossible to prove using just divisibility properties because it fails in more general domains. $\endgroup$ – Bill Dubuque Jan 31 '17 at 17:15
  • $\begingroup$ But we're only considering $\mathbb{Z}$, no? $\endgroup$ – Antonios-Alexandros Robotis Jan 31 '17 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$ – Bill Dubuque Jan 31 '17 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.