# When asked to prove something by contradiction, is it enough to show it in one case rather than doing division into cases?

Example: Prove that for all integers m and n if mn is odd, then m is odd and n is odd. (Use contradiction.)

Here's my work:

Suppose not. That is, suppose that there exists integers m and n such that mn is odd and m is not odd or n is not odd.

Since either m is not odd or n is not odd,

let m be an odd integer such that m = 2k+1 for some integer k (by def of odd integer)

and let n be an even integer such that n = 2g for some integer g (by def of even integer)

mn = (2k+1)(2k) (substitution)

= 4gk + 2g (distributive property of multiplication)

= 2(2gk + g) (factoring out a 2)

Let r = (2gk + g) where are is an integer by definition of integer because it is comprised of the sums and products of integers.

mn = 2r (substituting r for (2gk + g)

Thus mn is even by definition of even integer which contradicts our supposition that mn is odd.

Therefore, the given proposition "for all integers m and n if mn is odd, then m is odd and n is odd" is true.

My question is, is my work enough to show proof by contradiction or do I need to include division into cases? i.e., I proved contradiction for even m and odd n, do I also need to prove contradiction for odd m and even n?

Also, when I negated the statement and got: "suppose that there exists integers m and n such that mn is odd and m is not odd or n is not odd" which is of the form p and (~q or ~r), does this mean ~q or ~r OR does it mean ~q or ~r or both (~q and ~r). Basically in this negation, can both m and n be not odd? Or does it have to be one or the other and not both?

Going forward, will there EVER be a situation where I have to do a proof by contradiction and there will be division into cases, or can I just show one example where there is a contradiction and that is enough. That is what my textbook implies, just want to make sure...

Thank you!

• You did not consider the case in which neither $m$ nor $n$ was odd. Easy to rule out, of course, but no easier than the cases you do consider.
– lulu
Commented Nov 8, 2022 at 21:45
• Commented Nov 8, 2022 at 22:28

Your statement you want to proof is from a formal point of view: $$p \Rightarrow (a \land b)$$. The stamenent you want to contradict is then: $$p \Rightarrow \neg (a \land b) \iff p \Rightarrow (\neg a \lor \neg b)$$.

Basically in this negation, can both m and n be not odd?

Yes, either a or b is wrong or both can be wrong (by definition of "$$\lor$$"). That also means you should prove your statement with even n and even m.

do I also need to prove contradiction for odd m and even n?

No, you can just say it's analogous for even n and odd m. But that just works here because its very easy.

Going forward, will there EVER be a situation where I have to do a proof by contradiction and there will be division into cases, or can I just show one example where there is a contradiction and that is enough.

For example with ORS you need consider at least 3 cases. In generel there can be (direct, induction, whatever) proofs where you need to consider multiple cases.