# Proof by Cases: "For integers $x$ and $y$, if $xy$ is odd, then $x$ is odd and $y$ is odd."

Using the technique proof by cases, show that

"For integers $$x$$ and $$y$$, if $$xy$$ is odd, then $$x$$ is odd and $$y$$ is odd."

There are solutions online that go through every combination of odd and even values. (Case 1: $$x$$ is even and $$y$$ is even, Case 2: $$x$$ is even and $$y$$ is odd, Case 3: $$x$$ is odd and $$y$$ is even ... etc).

I don't think this is the proper way of doing a proof by cases because the cases should be in terms of what is given in the hypothesis ($$xy$$ is odd) instead of the conclusion we are trying to prove.

However, the only thing I can think of is Case 1: $$xy$$ is odd, but there is no other case which makes it more of a direct proof. What is the proper way to prove this?

• In my opinion, the simplest way to prove is by contrapositive: if at least one of $x,y$ is even, their product is even. Commented Oct 30, 2019 at 23:42
• the proof by cases is fine, because integers are either odd or even. another proof would be, suppose x or y is even, then xy must be even. Commented Oct 30, 2019 at 23:44

The proof is perfectly fine. I suspect your confusion comes from the idea that to show $$p\rightarrow q$$ by breaking into cases, we have to break $$p$$ itself up into cases and discuss. That is not really true. In particular, the statement $$p\rightarrow q$$ is equivalent to its contrapositive $$\neg q\rightarrow\neg p$$, so we can just as well break into cases regarding $$\neg q$$ (the negation of $$q$$) instead.

In particular, we want to show if $$xy$$ is odd then $$x,y$$ are odd. We may just as well show that if one of $$x,y$$ is even (i.e. they are not both odd), then $$xy$$ is even (the contrapositive statement), which you can do for example by breaking into three cases: when $$x$$ is even and $$y$$ is odd, then $$x$$ is odd and $$y$$ is even, or when $$x,y$$ are both even. Of course, there's no necessity to do that here, since it is easy to observe that if one of the factors of $$xy$$ is even then it automatically is too.

If $$xy$$ is odd, then:

case 1: $$x$$ is even, $$y$$ is odd. But $$xy$$ would be even since any integer ($$y$$) multiple of an even number ($$x$$) is an even number. Hence, contradiction.

case 2: $$x$$ is odd, $$y$$ is even. Again, contradiction.

case 3: both $$x$$ and $$y$$ are even. Then, again $$xy$$ would be even, since $$xy$$ is an integer ($$y$$) multiple of an even number $$x$$. Contradiction.

Therefore, if $$xy$$ is odd, then neither $$x$$ nor $$y$$ can be even.

Claim: If $$xy$$ is odd. then $$x$$, $$y$$ are odd.

Proof: Suppose by contradiction that either $$x$$ or $$y$$ is even i.e. $$x = 2k , y = 2k'+1$$ or vice versa for $$k, k' \in \mathbb{Z}$$ , then we have: $$xy = 4kk'+2k \equiv 0 \mod{2}$$. A contradiction.

Moreover, if $$x$$ and $$y$$ are mutually even, then $$x = 2k, y= 2k'$$ implies $$xy = (2k)(2k') = 4kk' \equiv 0 \mod{2}.$$ A contradiction.

However, for the case where $$x, y$$ are both odd, we have: $$xy = 8kk'^2+8kk'+2k+4k'^2+4k'+1 \equiv 1 \mod{2}$$.

This completes the proof.