# Can this be proved both directly and indirectly?

I am teaching a class in Number Theory and using a new textbook by James Pommersheim. There is a proof in the first chapter that states:

Let $m$ and $n$ be integers. If both $m$ and $n$ are odd, then $mn$ is odd.

They then prove this by saying $m=2q+1$ and $n=2r+1$. There's a simple foil, and then you can factor and find that $mn=2(\text{something})+1$ which means it's odd, thus proving the statement.

Then under the indirect proof section they make another statement:

Let $m$ and $n$ be integers. Prove that if $mn$ is odd, then both $m$ and $n$ are odd.

They then prove this by contradiction, saying $m=2k$. Then multiply both sides of the equation by $n$, giving $mn=2kn$, which states $mn$ is even, which contradicts the first statement. So, therefore, without loss of generality, both $m$ and $n$ must be odd.

My students had issue with the fact that they couldn't just use the proof for the first statement to prove the second statement. My understanding is that the two statements are converse of one another, they are both true, but need to be proven in different ways. In the first one, you start with $m$ and $n$, in the second one you start with $mn$. I'd like to give a more formal explanation for why we have a different method for proving the converse statement (using contradiction indirectly), but I could only just say "because it is the converse you have to go about it indirectly". But I'm not exactly sure.

-

Statements are simply not equivalent to their converses. To formally explain this, all you need to do is provide a counterexample. For example, the statement

If I break my leg, then I won't go to work tomorrow

is not equivalent to the statement

If I'm not at work tomorrow, then I broke my leg.

There are plenty of other reasons not to go to work tomorrow (e.g. you missed your bus, you're sick, you really didn't want to).

In this case, the two statements you're relating happen to be equivalent, but you have to prove this. Here is a very similar-looking situation where we do not have equivalence: it's true that

If m and n are even then mn is even

but it is not true that

If mn is even then m and n are even.

I just reread your question and noticed that you are really asking two questions, and possibly I have misread one of them. The other one is "why do we need contradiction to prove the second statement?"

We don't. As Divakaran says, we can take the contrapositive instead, and proving a statement is equivalent to proving its contrapositive. The difference between a proof by contradiction and a proof by contrapositive is somewhat subtle. When you want to prove that $P \Rightarrow Q$ by contradiction, you assume $P$ and $\neg Q$ and try to derive a contradiction. When you prove it by contrapositive, you assume $\neg Q$ and try to derive $\neg P$. Note that you cannot assume $P$ if you do this.

-

Consider the analog when you replace "odd" with "even": if $m,n$ are even then $mn$ is even, but it's not true that if $mn$ is even then $m,n$ are even.

The first statement is a simple one: given two numbers with given structure, I can tell you what you get if you multiply them. That's not very surprising. What the second statement is saying is more complicated: the only way to get to an odd number by multiplication is if you multiply two odd numbers. This is much more surprising, and a deeper fact. To prove that fact, you "go over all possibilities" of the product of two numbers, and show that only "odd times odd" gives you an odd number.

-

I would like to add to what Qiaochu Yuan said. It is easy to see that "If I break my leg, then I won't go to work tomorrow" is equivalent to "If i am at work tomorrow then i didnt break my leg". This is what you did in the proof: called proving the contrapositive. May be this link will explain better: http://en.wikipedia.org/wiki/Contraposition

-