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

  • 1
    $\begingroup$ Contrapositive follows the truth value of.. $\endgroup$
    – AgentS
    Mar 24, 2018 at 12:22
  • $\begingroup$ Here's how to ask a good question; in particular, we use MathJax here. $\endgroup$
    – Shaun
    Mar 24, 2018 at 12:25

2 Answers 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$.

  • $\begingroup$ Thanks, I just had some trouble with the contrapositive of p prime. But p stays always prime in the normal statement and the contrapositive? $\endgroup$ Mar 24, 2018 at 12:26
  • 1
    $\begingroup$ Yeah, the actual, formal contrapositive would be that "either $p$ does not divide $ak$ or $p$ isn't prime", but since you know that $p$ is prime then it must be the other. $\endgroup$ Mar 24, 2018 at 12:30
  • $\begingroup$ $(A\wedge\neg C)\to\neg B$ can be considered a contraposition of $(A\wedge B)\to C$, though to be precise $\neg C\to(\neg A\vee\neg B)$ is the contrapositive. In any case, all three statements are considered equivalent, so proving one proves the others. $\endgroup$ Mar 24, 2018 at 12:30
  • $\begingroup$ @GrahamKemp But (A∧¬C)→¬B is not the same as ¬C→(¬A∨¬B) ? $\endgroup$ Mar 24, 2018 at 22:07
  • $\begingroup$ They are equivalent. @WinstonCherf $\endgroup$ Mar 25, 2018 at 2:16

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 .


Not the answer you're looking for? Browse other questions tagged .