Proving sum of even + odd = odd in the opposite direction.

Question

Every child knows this proof:

Assuming that:

$odd(x) = 2a + 1$, where $a \in \mathbb{N} $ and

$even(y) = 2b + 1$, where $b \in \mathbb{N} $ and also

$\lnot odd(x) = even (x)$

$\lnot even(x) = odd (x)$

then: $odd(x) \land even(y) \rightarrow odd (x + y)$ is simply proven by: $$x = 2a + 1 $$ $$y = 2b $$ $$x + y = 2a + 1 + 2b$$ $$x + y = 2(a + b) + 1$$ $$x + y = 2k + 1, k \in \mathbb{N}$$

Therefore $x + y$ is odd, by definition of odd.

I am interested in proving it the other way around: $odd (x + y) \rightarrow odd(x) \land even(y)$

I'm not even really certain how to get started. I cannot assume anything about either $x$ or $y$; the only thing which I can assume is that their sum is odd. Would one have to prove this with a contrapositive? The problem I see with this (might be a case of overthinking) is that:

$$\lnot(odd(x) \land even(y)) \rightarrow \lnot odd(x + y) $$ $$\lnot odd(x) \lor \lnot even(y) \rightarrow \lnot odd(x + y) $$ $$ even(x) \lor odd(y) \rightarrow \lnot odd(x + y) $$

which just seems wrong...

Answer 1

There are only $4$ cases to consider

• if $x$ is odd and $y$ is odd, then $x+y$ is even.
• if $x$ is even and $y$ is even, then $x+y$ is even.
• if $x$ is odd and $y$ is even, then $x+y$ is odd.
• if $x$ is even and $y$ is odd, then $x+y$ is odd.

Hence if $x+y$ is odd, and $x$ and $y$ are both integers, we know that $x$ and $y$ have different parity, one of them is odd and one of them is even.

If $x+y$ is odd, then ($x$ is odd and $y$ is even) or ($x$ is even and $y$ is odd).

Answer 2

Let me try:

Given $c=x+y$ ; where $c$ is odd, i.e.

$c= 2k+1 =x +y .$

1)Assume $x,y$ are even, i.e. $2|x$ and $2|y$

then $2|c$, a contradiction,

since $c=2k+1$.

Hence it is not true that both $x$ and $y$ are even.

Hence $x$ is odd or $y$ is odd.

2) Assume both $x$ and $y$ are odd, then

$x= 2m+1$; $y=2n+1$ , and

$x+y = 2(m+n)+2$, a contradiction

since $c=x+y = 2k+1.$

3) Hence:

Either $x$ or $y$ is odd, not both.