# Prove that if xy is odd, then x and y are odd. Proof by cases

• Oct 7th 2013, 09:53 AM
Prove that if xy is odd, then x and y are odd. Proof by cases
Course: Foundations of Higher Mathematics

Let x and y be integers. Prove that if x*y is odd, then x and y are odd.

I assume that x and y are odd, i.e. $\displaystyle x=2a + 1$ and $\displaystyle y=2b + 1$.

Then, $\displaystyle xy = (2a + 1)(2b + 1)$

= $\displaystyle 4ab + 2a + 2b + 1$

= $\displaystyle 2(2ab + a + b) +1$

= $\displaystyle 2c + 1$, for some integer c

There's only one case for x and y to be odd, so is another case needed?
• Oct 7th 2013, 10:23 AM
emakarov
Re: Prove that if xy is odd, then x and y are odd. Proof by cases
Quote:

There's only one case for x and y to be odd, so is another case needed?

No, this is fine. I would add that at this level of detail, you should note that $\displaystyle a$ and $\displaystyle b$ are integer.

You could also prove this by contradiction. Then you need to consider two cases: $\displaystyle a$ is even and $\displaystyle b$ is even (each case includes the possibility that both are even).
• Oct 7th 2013, 10:40 AM
Re: Prove that if xy is odd, then x and y are odd. Proof by cases
Quote:

Originally Posted by emakarov
You could also prove this by contradiction. Then you need to consider two cases: $\displaystyle a$ is even and $\displaystyle b$ is even (each case includes the possibility that both are even).

I want to give that a try. I'm assuming that you mean that case 1 would be that a is even and case 2 would be that b is even, right?
• Oct 7th 2013, 11:02 AM
emakarov
Re: Prove that if xy is odd, then x and y are odd. Proof by cases
Quote:

I'm assuming that you mean that case 1 would be that a is even and case 2 would be that b is even, right?

Yes. The negation of the conclusion "x is odd and y are odd" is "x is even or y is even". This negation is assumed in a proof by contradiction. When you assume a disjunction (A or B) and use it to prove some C, you do it by cases, i.e., you prove that A implies C and B implies C.
• Oct 7th 2013, 11:22 AM
SlipEternal
Re: Prove that if xy is odd, then x and y are odd. Proof by cases
The answer in post #1 is not correct. You are not trying to prove that if $\displaystyle x$ and $\displaystyle y$ are odd, then their product is odd. You are trying to prove that if $\displaystyle x\cdot y$ is odd, then both $\displaystyle x$ and $\displaystyle y$ are odd. So, if you assume that $\displaystyle x$ and $\displaystyle y$ are odd, you will always get that $\displaystyle x$ and $\displaystyle y$ are odd because that was your assumption in the first place. Instead, assume only that the product $\displaystyle x\cdot y$ is odd. A logically equivalent statement to the one you are trying to prove would be "If x is even or y is even, then x*y is even." This is called the contrapositive, and a conditional statement is logically equivalent with its contrapositive. So, if you prove that statement, you also prove the original statement. Assume (without loss of generality) that $\displaystyle x$ is even. Then $\displaystyle x=2k$ for some integer $\displaystyle k$. Hence $\displaystyle x\cdot y = 2ky = 2(ky)$ is even. This proves the contrapositive, and in so doing, also proves the initial statement.
• Oct 7th 2013, 11:32 AM
emakarov
Re: Prove that if xy is odd, then x and y are odd. Proof by cases
Quote:

Originally Posted by SlipEternal
The answer in post #1 is not correct. You are not trying to prove that if $\displaystyle x$ and $\displaystyle y$ are odd, then their product is odd. You are trying to prove that if $\displaystyle x\cdot y$ is odd, then both $\displaystyle x$ and $\displaystyle y$ are odd.

Thanks. I retire for the night.
• Oct 7th 2013, 01:42 PM
Re: Prove that if xy is odd, then x and y are odd. Proof by cases
Quote:

Originally Posted by SlipEternal
The answer in post #1 is not correct. You are not trying to prove that if $\displaystyle x$ and $\displaystyle y$ are odd, then their product is odd. You are trying to prove that if $\displaystyle x\cdot y$ is odd, then both $\displaystyle x$ and $\displaystyle y$ are odd.

That's weird, because we've been doing things in class that way for a while. But I could be wrong. Take a look at this proof. The professor did it in class.

Let a, b, and c be integers. Prove: (a|b) ^ (b|c) => (a|c)

Assume that $\displaystyle (a|b)$ ^ $\displaystyle (b|c)$, i.e. $\displaystyle b=ax$ and $\displaystyle c=by$, for any integer x,y

Then, $\displaystyle c=by$
= $\displaystyle (ax)y$
= $\displaystyle a(xy)$
= $\displaystyle az$, for some integer z

Therefore, $\displaystyle c=az$, for some integer z, so $\displaystyle a|c$
• Oct 7th 2013, 02:10 PM
topsquark
Re: Prove that if xy is odd, then x and y are odd. Proof by cases
Quote:

Originally Posted by SlipEternal
The answer in post #1 is not correct. You are not trying to prove that if $\displaystyle x$ and $\displaystyle y$ are odd, then their product is odd. You are trying to prove that if $\displaystyle x\cdot y$ is odd, then both $\displaystyle x$ and $\displaystyle y$ are odd. So, if you assume that $\displaystyle x$ and $\displaystyle y$ are odd, you will always get that $\displaystyle x$ and $\displaystyle y$ are odd because that was your assumption in the first place. Instead, assume only that the product $\displaystyle x\cdot y$ is odd. A logically equivalent statement to the one you are trying to prove would be "If x is even or y is even, then x*y is even." This is called the contrapositive, and a conditional statement is logically equivalent with its contrapositive. So, if you prove that statement, you also prove the original statement. Assume (without loss of generality) that $\displaystyle x$ is even. Then $\displaystyle x=2k$ for some integer $\displaystyle k$. Hence $\displaystyle x\cdot y = 2ky = 2(ky)$ is even. This proves the contrapositive, and in so doing, also proves the initial statement.

I am not great with logic, so please forgive me if my comment is obvious. I am not sure that the contrapositive is fully constructed here. My thought is that, yes, you can show that if the product of two numbers is even then at least one of the original numbers also must be even. But I don't feel that the possibility of one of the numbers being even and one odd (from the original problem statement) is addressed here? Or am I mistaken?

-Dan
• Oct 7th 2013, 02:19 PM
Plato
Re: Prove that if xy is odd, then x and y are odd. Proof by cases
Quote:

Course: Foundations of Higher Mathematics
Let x and y be integers. Prove that if x*y is odd,then x and y are odd.
I assume that x and y are odd, i.e. $\displaystyle x=2a + 1$ and $\displaystyle y=2b + 1$.

Quote:

That's weird, because we've been doing things in class that way for a while. But I could be wrong. Take a look at this proof. The professor did it in class.
Let a, b, and c be integers. Prove: (a|b) ^ (b|c) => (a|c)
Assume that $\displaystyle (a|b)$ ^ $\displaystyle (b|c)$, i.e. $\displaystyle b=ax$ and $\displaystyle c=by$, for any integer x,y
Then, $\displaystyle c=by$
= $\displaystyle (ax)y$
= $\displaystyle a(xy)$
= $\displaystyle az$, for some integer z
Therefore, $\displaystyle c=az$, for some integer z, so $\displaystyle a|c$

The question about your OP is that you are proving the converse of what you are asked to prove.
If $\displaystyle xy$ is odd, then both $\displaystyle x~\&~y$ are odd. Not the other way around.
Personally, I would do this by contradiction. Suppose $\displaystyle xy$ is odd.
Then is any even number times any integer is even. SO?

As for your instructor's proof, I hope he/she said $\displaystyle b=ax$ and $\displaystyle c=by$, for some integers x & y.
Otherwise, it is the way to do it.
• Oct 7th 2013, 03:53 PM
SlipEternal
Re: Prove that if xy is odd, then x and y are odd. Proof by cases
Quote:

That's weird, because we've been doing things in class that way for a while. But I could be wrong. Take a look at this proof. The professor did it in class.

Let a, b, and c be integers. Prove: (a|b) ^ (b|c) => (a|c)

Assume that $\displaystyle (a|b)$ ^ $\displaystyle (b|c)$, i.e. $\displaystyle b=ax$ and $\displaystyle c=by$, for any integer x,y

Then, $\displaystyle c=by$
= $\displaystyle (ax)y$
= $\displaystyle a(xy)$
= $\displaystyle az$, for some integer z

Therefore, $\displaystyle c=az$, for some integer z, so $\displaystyle a|c$

$\displaystyle (a|b) \wedge (b|c) \Longrightarrow (a|c)$ is the equivalent of saying, "If a divides b and b divides c, then a divides c."
Your professor assumed what came after the "if" and proved what came after the "then". In post #1, you assume what comes after the "then" and prove what comes after the "if". As Plato said, you proved the converse statement which is not logically equivalent to the original statement.

Quote:

Originally Posted by topsquark
I am not great with logic, so please forgive me if my comment is obvious. I am not sure that the contrapositive is fully constructed here. My thought is that, yes, you can show that if the product of two numbers is even then at least one of the original numbers also must be even. But I don't feel that the possibility of one of the numbers being even and one odd (from the original problem statement) is addressed here? Or am I mistaken?

-Dan

You are correct, I did not explain how the statement I wrote is logically equivalent to the contrapositive. The contrapositive would be, "If not (x and y are odd), then not (x*y is odd)." By DeMorgan's Laws, the negation of a conjunction of two expressions is logically equivalent to the disjunction of the negation of each expression $\displaystyle \left( \neg(P\wedge Q) \equiv \neg P \vee \neg Q \right)$. So, the statement is logically equivalent to "If (x is not odd) or (y is not odd), then x*y is not odd." Since not odd is equivalent to even, "If x is even or y is even, then x*y is even."

However, the statement you mention, "If the product of two numbers is even, then at least one of the original numbers also must be even," is actually an inverse statement, not a contrapositive one. In general, the truth value of the inverse statement does not in any way depend on the truth value of the original statement.
• Oct 7th 2013, 04:35 PM
Re: Prove that if xy is odd, then x and y are odd. Proof by cases
This is great. Thank you emakarov, SlipEternal, topsquark, and Plato!

I think what you all are saying is that I should prove that the consequent is true. Then, no matter what the truth value of the antecedent is, the implication will be true. I think I see it now. Don't assume the consequent is true, but prove that it is. I can't think of a way to prove that x and y are odd, so by finding the contrapositive I can prove that x*y is odd and would give me 2-3 cases. Case 1 being x and y are odd. Case 2 being that x is odd and y is even (and vice-versa for case 3, if it's needed).

Proof by contradiction was mentioned twice, but I don't know how to prove it that way. I can't find anything about the process in my textbook.
• Oct 7th 2013, 04:46 PM
SlipEternal
Re: Prove that if xy is odd, then x and y are odd. Proof by cases
For proof by contradiction: When is a conditional statement false? It is when the antecedent is true, but the consequent is false. Assume that the antecedent is true and the consequent is false and arrive at a logical contradiction. Proof by contradiction is not necessary in this case because proof by exhaustion is just as easy.

Case 1: x is odd and y is odd (you already showed that x*y is odd)
Case 2: x is even and y is odd (show that x*y is even)
Case 3: x is odd and y is even (show that x*y is even)
Case 4: x is even and y is even (show that x*y is even)

Assume that x*y is odd. Case 1 is the only possible conclusion because you showed that cases 2, 3, and 4 cannot be true if x*y is odd.
• Oct 7th 2013, 04:51 PM