[Math] mn is is even iff m is even or n is even

discrete mathematicslogicproof-verification

The problem states:

Let $mn$ be integers. Show that $mn$ is even if and only if $m$ is even or $n$ is even.

They are asking to prove an iff statement. So it can be said that $P→Q$ and $Q→P$. I can prove that $¬P→¬Q$ and $¬Q→¬P$ as far is I understood.

I tried it like this:

$¬P→¬Q$: $mn$ is odd if $m$ and $n$ are odd. An odd integer can be represented as $2x + 1$, so we can rewrite $mn$ as $(2x + 1)(2y + 1) = 2(2xy + x + y) + 1$ which is odd.

$¬Q→¬P$: if $m$ and $n$ are odd, then $mn$ is odd. How to write this then? Isn't that essentially the same as the previous? Or did I misunderstand how to prove iff in this case.

Best Answer

Yes, to prove a biconditional 'P if and only if Q' you want to prove both 'If P then Q' and 'If Q then P'.

And yes, in order to show a conditional 'If P then Q', you can also show its contrapositive 'If not Q then not P'.

However, just because you show the one conditional 'If P then Q' through its contrapositive, does not mean that you have to show the other conditional 'If Q then P' by its contrapositive as well. Hence, there are 4 ways to prove a biconditional 'P if and only if Q':

  1. You show 'If P then Q' and 'If Q then P'
  2. You show 'If P then Q' and 'If not P then not Q'
  3. You show 'If not Q then not P' and 'If Q then P'
  4. You show 'If not Q then not P' and 'If not P then not Q'

(and by the way, a common mistake I see is that someone proves: 'If P then Q' and 'If not Q then not P' ... that does not work, since they are each other's contrapositive, so you really only show one direction twice!)

Now, which of these 4 methods do you use. Well, it makes sense to pick the easiest one.

So, for the 'If $mn$ is even, then $m$ is even or $n$ is even', I think you did indeed pick the easiest one by considering its contrapositive 'If $m$ and $n$ are odd, then $mn$ is odd'

However, for the other direction 'If $m$ or $n$ is even, then $mn$ is even', the direct proof is probably easier than the contrapositive: all you need to do is consider the 2 cases:

Case 1. $m$ is even. Then $m=2k$ for some integer $k$, and hence $mn=2kn$ is even.

Case 2. $n$ is even. Then $n=2k$ for some integer $k$, and hence $mn=2km$ is even.

Since either $m$ or $n$ is even, and since in both acses we get that $mn$ is even, we have shown that $mn$ is definitely even (proof by cases)

Related Question