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

number theory problem

  • $\begingroup$ The '$p|ab$ and $p|a$ or $p|b$' part is ambiguous. $\endgroup$ – Git Gud Jan 26 '14 at 22:11
  • $\begingroup$ @GitGud And has precedence over or. $\endgroup$ – J.R. Jan 26 '14 at 22:11
  • $\begingroup$ @TooOldForMath Since when? $\endgroup$ – Git Gud Jan 26 '14 at 22:12
  • $\begingroup$ @GitGud Thats just how it is. $\endgroup$ – J.R. Jan 26 '14 at 22:13
  • 1
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Jan 26 '14 at 22:17

The contrapositive of

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


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

  • $\begingroup$ 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)$. $\endgroup$ – 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) )$.

  • $\begingroup$ 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$). $\endgroup$ – Henning Makholm Jan 27 '14 at 17:39
  • $\begingroup$ @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. $\endgroup$ – Mauro ALLEGRANZA Jan 27 '14 at 17:41
  • $\begingroup$ @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". $\endgroup$ – Mauro ALLEGRANZA Jan 27 '14 at 19:42
  • $\begingroup$ x @mauro: That has the implication going the other way. $\endgroup$ – Henning Makholm Jan 27 '14 at 19:44
  • $\begingroup$ @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. $\endgroup$ – Mauro ALLEGRANZA Jan 28 '14 at 11:00

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.