Prove that if $n,m \in \mathbb{N}^{\gt0}$ and $nm$ is even then either $n$ is even or $m$ is even Q: Prove that if $n,m \in \mathbb{N}$ and $nm$ is even then either $n$ is even or $m$ is even.
Attempt Contrapositive: Assume $n$ and $m$ are odd. Then $n=2k-1$ and $m=2k'-1$ and
$nm=(2k-1)(2k'-1)=2(2kk'-k-k'+1)-1$
how do I show that $2kk'-k-k'+1 \in \mathbb{N}$ ?
Attempt: since $k,k' \in \mathbb{N}$ $k \geq1$ and $k' \geq1$
Thus $2kk'\geq 2$ and $2kk'-k-k'+1>0$
 A: I believe it's easier to use $n = 2k + 1$ and $m = 2k' + 1$ where $k,k' \ge 0$. Then $nm = (2k + 1)(2k' + 1) = 4kk' + 2k + 2k' + 1 = 2(2kk' + k + k') + 1 \gt 0$ since the part multiplying $2$ is $\ge 0$ and $1$ is being added. Also, as it has a remainder of $1$ when divided by $2$, it's odd.
A: $2kk'-k-k'+1$
$=(kk'-k)+(kk'-k')+1$
$=k(k'-1)+k'(k-1)+1$
As $k$ and $k'$ are natural numbers, $k-1\ge0$ and $k'-1\ge0$, so $k(k'-1)$ and $k'(k-1)$ are nonnegative integers. The "$+1$" will make the number from nonnegative integer to natural number.
$\therefore2kk'-k-k'+1 \in \mathbb{N} .$
A: Hint:
Using your approach, consider $n, m$ odd where $n = 2k + 1$ and $m = 2k' + 1$, $k, k' \geq 0$ 
A: A number $s \in \Bbb N = \{1,2,\dots\}$ is even iff it can be written as $s= 2k$.
A number $s \in \Bbb N$ is odd iff $s = 1$ or it can be written as $s= 2k + 1$.
Suppose both $m$ and $n$ are odd.
Case 1: $m = 1$ and $n = 1$. Then $mn=1$ is odd.
Case 2: $m = 1$ and $n = 2k +1$. Then $mn = 2k + 1$ is odd.
Case 3: $m = 2k+1$ and $n = 1$. Then $mn = 2k + 1$ is odd.
Case 4: $m = 2k+1$ and $n = 2k'+1$ . Then
$$mn = 4kk'+2k + 2k'+1 =2(2kk'+k+k')+1$$
is odd.
So the product of any two odd numbers is odd.
