Prove that if m and n are integers and mn is even, then m is even or n is even

In this case, we will attempt a proof by contradiction.

Remember that to use proof by contradiction to prove a conditional statement(p->q), we do the following:

  • Assume the negation of q (the conclusion of the conditional statement).
  • Use p and ¬q to arrive at a contradiction.

This type of proofs is valid because p->q ≡ (p^q)-> F.

p= “mn is even”

q= “m is even or n is even”

¬q = “m and n are odd”.   (¬(pvq)≡¬p^¬q by the De Morgan law)

If m and n are both odd, then:

m= 2k+1, for some integer k

n=2t+1, for some integer t

mn = (2k+1) x (2t+1) = 4kt + 2k + 2t +1 = 2(2kt+k+t) + 1

Therefore, mn is odd.

Because p is true (premise) and ¬p is also true, we have a contradiction.

This completes the proof by contradiction ∎

Related posts: