Is this a valid proof of "For all integers m and n, if mn is even, then m is even, or n is even"?

Question

Theorem: For all integers $m$ and $n$, if $mn$ is even, then $m$ is even, or $n$ is even.

Proof: Assume for all integers $m$ and $n$, if $mn$ is even, then $m$ is odd and $n$ is odd.

By the definition of odd, $m = 2k + 1$, and $n = 2r + 1$, where $k$ and $r$ are particular but arbitrary integers.

$mn = (2k + 1)(2r + 1)$

$= 4(kr)2 + 2k + 2r + 1$

$= 2((kr)2 + k + r) + 1$

Since $k$ and $r$ are integers, we can replace $(kr)2 + k + r$ with $p$, where $p$ is the integer value of $(kr)2 + k + r$. By the definition of odd, $mn = 2(p) + 1$ is odd, which contradicts $mn$ is even. Hence the supposition is false, therefore the theorem is true.

Answer 1

No, this is not a valid proof. The underlying rule of logic you apply is that the negation of $\forall m\,\forall n\enspace (P\implies Q)$ is $\forall m\,\forall n\enspace (P\implies \neg Q)$, which is wrong: the negation is a counter-example, i.e. $\exists m\,\exists n\enspace(P\wedge( \neg Q))$.

The simplest proof would be by contrapositive, i.e. proving that if none of $m,n$ is even, then $mn$ can't be even.

Answer 2

The claim can be formalized as

$$ (\forall m\in \mathbb{Z})(\forall n\in \mathbb{Z})[mn \text{ is even} \to (m \text{ is even }) \lor (n \text{ is even})]. $$

To prove it start by assuming that $mn$ is even and that $m$ is not even (a number can either be even or odd but not both). Then there exists $k\in\mathbb{Z}$ s.t.

$m = 2k+1$

and so $mn = (2k+1)n$ is even. Assume, for the sake of a contradiction that $n$ is odd, i.e. $n = 2k^\prime+1$ for some $k^\prime\in \mathbb{Z}$. Then

$$mn = (2k+1)(2k^\prime+1) = 4(kk^\prime) + 2k + 2k^\prime +1 = 2p+1,$$

with $p = 2(kk^\prime) + k + k^\prime$ an integer. But this contradicts the assumption that $mn$ is even, so $n$ must be even. Q.E.D.