A Quick Little Proof

Prove that mn is odd if and only if both m and n are odd. We can write this in mathamatical notation as mn \in \mathbb O \Longleftrightarrow m,n \in \mathbb O

Let’s first prove that if both m and n are odd then their product is odd. An odd number is of the form two times and integer plus one. So let m = 2r + 1 and 2q + 1 . Then mn = (2r + 1)(2q  + 1) = 4rq + 2r  + 2q + 1 = 2(2rq + r + q) + 1 . Which is odd, by definition, it’s two time an integer — in this case the integer is 2(2rq + r + q)  — plus one.

Now we have to prove things in the other direction. If mn is odd then so are both m and n . Let’s do a proof by contradiction. We must assume that either m or n is even and then prove that mn is even. Assume m is even. Then mn = (2r)(2q  + 1) = 4rq + 2r = 2(2rq + r), which is even. The same holds if n is even. We’ve completed our proof by contradiction and so have proven our original statement.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s