Saturday, November 15, 2008

Prove if ab is odd, then both a and b are odd. (Contradiction)

Assume a and b are positive integers, prove if a*b is odd then a and b are odd.

Proof by contradiction: where we want to prove Q => P we take ~P=> Q Λ ~ Q which is a contradiction, so therefore we conclude P.

This is a proof by contradiction which means that we have to assume the opposite consequent, which is the say that a and b are not both odd. So either a is even or b is even.

If a is even, then a=2k for some integer k, and b*2k will always be even.

If b is even, then b=2m for some integer m, and a*2m will always be even.

So either case leads to a contradiction that a*b is odd, and therefore if a*b is odd, then both a and b are odd.

No comments: