# Proof by Contradiction: Odd and Its Square

We have had several examples on proof by contradiction in this blog like irrationality of square root of 3 and the sum of root of 2 and root of 3. In this post, we will have another detailed example.

In proof by contradiction, we want to change the statement “if P then Q” to “if NOT Q then NOT P.” These two statements are equivalent, so if we can prove the latter, then we have proved the former. Consider the following theorem.

Theorem: For any integer \$latex x\$, if \$latex x^2\$ is odd, then \$latex x\$ is odd.

We can assign the statements above to P (the hypothesis) and Q (the conclusion) as follows.

P: \$latex x^2\$ is odd

Q: \$latex x\$ is odd.

If we are going to change this statement to “if NOT Q then NOT P,” then, we have to find the opposite of P and opposite of Q.

For Q, what is the opposite of “x is odd”? This can mean “\$latex x\$ is NOT odd” or equivalently, “x is even.”  This is also the same with P. The statement NOT P is the same as “\$latex x^2\$ is NOT odd” or equivalently “\$latex x^2\$ is even.” Therefore, the statement in the form of  “if NOT Q, then NOT P” can be stated as follows.

Theorem: If \$latex x\$ is even, then \$latex x^2\$ is even.

Proof

If \$latex x\$ is even, then it is divisible by 2, which means that x is a product of 2 and some integer \$latex k\$. So, \$latex x = 2k\$.

Squaring, we have

\$latex x^2 = (2k)^2 = 4k^2\$.

Now, \$latex 4k^2\$ is a multiple of 2 since \$latex k\$ is an integer. Therefore, \$latex 4k^2\$ is divisible by 2 which means that it is even.

Since \$latex 4k^2\$ is even, \$latex x^2\$ is also even and this proves the theorem.

Notice that the restated theorem (or the contrapositive) is a lot easier to prove that its equivalent statement above.