# Proof involving primes and divisibility

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!

• Hint: Use the fact that there is unique factorization into prime elements in $\mathbb{Z}$. Jan 31, 2017 at 16:44
• @mathma I'd say that OP is not allowed to use that. Jan 31, 2017 at 16:45
• Are you allowed to use the Bezout's identity? Or maybe the four numbers theorem? Jan 31, 2017 at 16:47
• 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? Jan 31, 2017 at 16:49
• @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. Jan 31, 2017 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$.
• But we're only considering $\mathbb{Z}$, no? Jan 31, 2017 at 17:16
• 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. Jan 31, 2017 at 17:17