I applied Modus Tollens and De Morgan's laws to the following property of primes:

If $p$ is a prime and $p | ab$ for $a, b \in \mathbb{Z}$, then either $p|a$ or $p|b$.

Modus Tollens: If not ($p|a$) or ($p|b$) then $p$ is not (a prime and $p|ab$).

By De Morgan's laws, If $p \nmid a$ and $p \nmid b$, then $p$ is not a prime or $p \nmid ab$.

Is it possible to use this to prove the following statement?

If $n$ is not a prime, then $a, b \in \mathbb{Z} : n | ab$ but $n \nmid a$ and $n \nmid b$.

I'm thinking about applying De Morgan to that statement but wouldn't know how when there's a "but".

  • 3
    $\begingroup$ You need quantifiers, ie, first order logic, to make sense of the sentences you want to say: "(p is prime) iff for all a in Z, for all b in Z (p|ab implies (p|a or p|b))" $\endgroup$ – user359302 Feb 14 at 19:58
  • 1
    $\begingroup$ Nope, your second statement (even if the appropriate existence quantifier is added) does not follow from the first using bare logic. You have to think about numbers and primes to prove it. If "primes" were defined in a way that there would be no primes at all, then the first statement would still be true (vacuously), but the second would not. $\endgroup$ – darij grinberg Feb 14 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.