If p does not divide a and p does not divide k, than p does not divide a*k

Question

How can I prove that:

If $p$ (prime) does not divide $a$ and $p$ does not divide $k$, than $p$ does not divide $a*k$?

Does this follow from Euclid's lemma? $$\forall a,b\in \Bbb Z~:~ p\text{ prime}\implies \left(p\mid ab \implies (p\mid a\vee p\mid b)\right)$$

Answer 1

Remember, any statement of the form $(A\wedge B)\to C$ is equivalent to $A\to(B\to C)$. (This rule of equivalence is known as "exportation".)

So Euclid's Lemma can be stated: $$\forall a,b\in \Bbb Z~:~ p\text{ priem}\implies (p\mid ab \implies (p\mid a\vee p\mid b))$$

Thus if we substitute the contrapositive for that inner nested implication (and use deMorgan's Law): $$\forall a,b\in \Bbb Z~:~ p\text{ priem}\implies ((p\nmid a\wedge p\nmid b)\implies p\nmid ab)$$

And via exportation again we have $$\forall a,b\in \Bbb Z~:~ (p\text{ priem}\wedge p\nmid a\wedge p\nmid b) \implies p\nmid ab$$

Thus the statement, "If $p$ (a prime) does not divide $a$ (an integer) and does not divide $b$ (an integer), then $p$ does not divide their product, $ab$," is logically equivalent to Euclid's Lemma .

Answer 2

Yes, it is in fact the contrapositive. If $p$, being prime, divided $a \times k$, it would imply from Euclid's lemma that $p$ divides either $a$ or $k$. Since neither is the case, then $p$ cannot divide $a \times k$.