Discrete Math Use proof by contraposit ion to show that if m

(Discrete Math)

Use proof by contraposit ion to show that if mn is even then m is even or n is even.

Solution

Suppose that m and n are arbitrary odd integers. Then m = 2a + 1 and n= 2b + 1; where a and b are integers. Then

mn = (2a + 1)(2b+ 1) (substitution)

     = 4ab+ 2a+ 2b + 1 (associative, commutative, and distributive laws)

     = 2(2ab + a + b) + 1 (distributive law)

Since

mn is twice an integer namely, 2(ab+a+b) plus 1, mn is odd.

hence the given statement is proved.