# contrapositive of the following logical statement

What is the contrapositive of the following statement: $p|ab$ and $p|a$ or $p|b$ then $p$ is prime.

number theory problem

• The '$p|ab$ and $p|a$ or $p|b$' part is ambiguous. – Git Gud Jan 26 '14 at 22:11
• @GitGud And has precedence over or. – J.R. Jan 26 '14 at 22:11
• @TooOldForMath Since when? – Git Gud Jan 26 '14 at 22:12
• @GitGud Thats just how it is. – J.R. Jan 26 '14 at 22:13
• The statement that you intended to write might have been "if $p\mid ab$ implies $p\mid a$ or $p\mid b$ for all $a$ and $b$, then $p$ is a prime". Written that way, it's almost true about the natural numbers (though it fails for $p=1$), but the position of the quantification over $a$ and $b$ is crucial, and leaving it out of the statement invites mistakes in forming the contrapositive. – Henning Makholm Jan 26 '14 at 22:17

The contrapositive of

$p|ab \land (p|a \lor p|b) \Rightarrow p$ is prime

is

$p$ is not prime $\Rightarrow p \not\mid ab \lor (p\not\mid a \land p\not\mid b)$.

But I don't think those are true statements...

• You are right; in another post about number theory, it was proved that $\forall p \forall a \forall b (Prime(p) \rightarrow (p∣ab \rightarrow (p∣a \lor p∣b)))$. But if you have $p = 60$, $a = 60$ and $b = 10$, then $60|600$ and $60|60$, so that $p|ab \land (p|a \lor p|b)$ but $\lnot Prime(60)$. – Mauro ALLEGRANZA Jan 28 '14 at 10:51

The contrapositive of $(P \rightarrow Q)$ is : $(\lnot Q \rightarrow \lnot P)$.

So, if we omit the initial quantifiers $\forall a \forall b \forall p$, we have :

$( p|ab \rightarrow (p|a \lor p|b) ) \rightarrow Prime(p)$

Then the contrapositive must be :

$(\lnot Prime(p) \rightarrow \lnot ( p|ab \rightarrow (p|a \lor p|b) )$.

Now, if we want to "unwind" also the inner conditional, we can take into account that : $(P \rightarrow Q)$ is equivalent to : $(\lnot P \lor Q)$, so that $\lnot (P \rightarrow Q)$, using De Morgan laws, becomes : $(\lnot \lnot P \land \lnot Q)$, and finally : $(P \land \lnot Q)$.

The translation now is :

$(\lnot Prime(p) \rightarrow ( p|ab \land \lnot (p|a \lor p|b) )$

and finally :

$(\lnot Prime(p) \rightarrow ( p|ab \land (\lnot p|a \land \lnot p|b) )$.

• In my suggested interpretation the quantifiers $\forall a\forall b$ are NOT initial, but belong on the left of the $\to$. That makes the statement almost true (and fully true if we redefine "prime" to include $1$). – Henning Makholm Jan 27 '14 at 17:39
• @Henning Makholm - I'm sorry; I'll correct my answer. I supposed that the question was about the "logical machinery" and not about proving if the number theoretic statement was true or not. – Mauro ALLEGRANZA Jan 27 '14 at 17:41
• @Henning Makholm - my "interpretation" was based on a previous post about number theory, i.e.checking that $( p \mid ab \rightarrow (p \mid a \lor p \mid b) )$, that is true only if $Prime(p)$ [if not, $60 \mid 6 \times 10$]. So, the theorem can be formalized as : $\forall p \forall a \forall b ( Prime(p) \rightarrow ( p \mid ab \rightarrow (p \mid a \lor p \mid b)) )$. I'm supposing that the OP is trying to prove the other "direction" of the "iff". – Mauro ALLEGRANZA Jan 27 '14 at 19:42
• x @mauro: That has the implication going the other way. – Henning Makholm Jan 27 '14 at 19:44
• @Henning - I understand your comment; my point of view is that, assuming that my reading of the OP's formula is correct, and if my contraposition is, we have that the formula is not true. Take $p = 60$, so that $\lnot Prime(p)$ is true, take $a = 60$ and $b = 10$, so that $p|ab$, but $60|60$, and so: $\lnot p|a$ is false. This shows that the formula above $[True \rightarrow (True \land (False \land True))]$ will get $False$. Having said that, under my initial "assumptions", we have that $\forall p \forall a \forall b ((p|ab \rightarrow (p|a \lor p|b)) \rightarrow Prime(p))$ is false. – Mauro ALLEGRANZA Jan 28 '14 at 11:00