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?

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

Quote:

Originally Posted by

**MadSoulz** 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).

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?

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

Quote:

Originally Posted by

**MadSoulz** 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.

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.

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.

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$

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

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

Quote:

Originally Posted by

**MadSoulz** 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:

Originally Posted by

**MadSoulz** 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** integer**s** x & y.

Otherwise, it is the way to do it.

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

Quote:

Originally Posted by

**MadSoulz** 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.

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.

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.

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

Oops, I've made another mistake.

Find the contrapositive, and prove that x*y is even, with 2-3 cases

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

It's taking a little time, but I'm getting this. I really appreciate the help.

Original statement: If x*y is odd, then x and y is odd.

I didn't understand how Plato got "If x is even OR y is even, then x*y is even" as the contrapositive, but now I see it. You also negate the "and" to get "or".