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

This problem aims to familiarize us with the method of poof. The concept required to solve this problem is related to discrete mathematics, including direct proof or proof by contradiction, and proof by contrapositive.

There are multiple methods to write a proof, but here we are going to see only two methods, proof by contradiction and proof by contrapositive. Now proof by contradiction is a kind of proof that demonstrates the truth or the reality of a proposal, by exhibiting that considering the proposal to be incorrect points to a contradiction. It is also comprehended as indirect proof.

For a proposal to be proved, the event such as $P$ is assumed to be false, or $\sim P$ is said to be true.

Whereas the method of proof by contrapositive is utilized to prove conditional statements of the structure “If $P$, then $Q$”.This is a conditional statement that shows that $P \implies Q$. Its contrapositive form would be $\sim Q \implies \sim P$.

Let’s suppose $m\times n$ is even, then we can assume an integer $k$ such that we get a relation:

$m\times n= 2k$

If we get $m$ to be even then there is nothing to prove, so let’s say that $m$ is odd. Then we can set the value of $m$ to be $2j + 1$, where $j$ is some positive integer:

$m = 2j + 1$

Substituting this into the first equation:

$m\times n= 2k$

$(2j + 1)\times n= 2k$

$2jn + n = 2k$

And therefore,

$n= 2k – 2jn$

$n= 2(k – jn)$

Since $k – jn$ is an integer, this shows that $n$ would be an even number.

Proof by contraposition:

Suppose that the statement “$m$ is even or $n$ is even” is not true. Then both $m$ and $n$ are supposed to be odd. Let’s see if the product of two odd numbers is an even or an odd number:

Let $n$ and $m$ be equal to $2a + 1$ and $2b + 1$ respectively, then their product is:

$(2a+1)(2b+1) = 4ab+2a+2b+1$

$= 2(2ab+a+b)+1$

This shows that the expression $2(2ab+a+b)+1$ is of the form $2n+1$, thus the product is odd. If the product of odd numbers is odd, then $mn$ is not true to be even. Therefore, in order for $mn$ to be even, $m$ must be even or $n$ must be an even number.

Numerical Result

In order for $mn$ to be even, $m$ must be even or $n$ must be an even number proved by contraposition.

Example

Let $n$ be an integer and the expression $n3 + 5$ is odd, then prove that $n$ is even by using proof by contraposition.

The contrapositive is “If $n$ is odd, then $n^3 +5$ is even.” Suppose that $n$ is odd. Now we can write $n=2k+1$. Then:

$n^2+5= (2k+1)3+5 =8k^3+12k^2+6k+1+5$

$=8k^3+12k^2+6k+6 = 2(4k^3+6k^2+3k+3)$

Hence, $n^3+5$ is twice some integer, thus it is said to be even by the definition of even integers.