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

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.

• Just, you must assume that "there is" some odd integer m and some odd integer n, such that mn is even... But you really don't need to use an indirect proof. Jan 19, 2016 at 20:38
• So I should replace "Assume for all integers m and n, if mn is even, then m is odd, and n is odd" with "There exist integers m and n where if mn is even, then m is odd and n is odd"?
– 123
Jan 19, 2016 at 20:46
• Better to use this one: "There exist integers m and n where mn is even and m is odd and n is odd." (I have replaced "if ... then ..." by "and") Jan 19, 2016 at 20:50

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.

• I think I get what you're saying. So if I replace the incorrect negation "Assume for all integers m and n, if mn is even, then m is odd, and n is odd" with the correct negation (I think) "There exist integers m and n where mn is even, and m is odd, and n is odd", then this would be valid?
– 123
Jan 19, 2016 at 20:50
• No, there is no ìf … then in the negation. In ordinary language, it would be something like ‘[ …] $m$ and $n$ are odd, albeit $mn$ is even’. Jan 19, 2016 at 20:55
• I edited that, but I think you missed my edit. "There exist integers m and n where mn is even, and m is odd, and n is odd" Is that accurate?
– 123
Jan 19, 2016 at 20:57

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.