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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.