# Let $x$ and $y$ be integers. Write a proof by contraposition to show that “if $x+y$ is even, then $x$ and $y$ have the same parity.”

Let $x$ and $y$ be integers. Write a proof by contraposition to show that "if $x+y$ is even, then $x$ and $y$ have the same parity."

proof by contrapositive:

Usually i would start these and assume the negation of the if statement, then i would list a definition and use it to substitute the then statement but that's not possible in this sentence.

Assume $x+y$ is odd

by definition of odd $∃k∈ℤ$ such that $x=2k+1$

by definition of odd $∃j∈ℤ$ such that $y=2j+1$

it's obvious that they must have the same parity to stay odd but i don't know how to exactly write it in proof form.

• contrapositive is 'if x,y have different parities, x+y is odd' – JonMark Perry Sep 17 '15 at 17:02

You've tried to prove the converse. The contrapositive is instead "if $x$ and $y$ have opposite parities, then $x+y$ is odd".
Let $x$ and $y$ have opposite parities. Then one is odd and one is even (by, I suppose, something like the pigeonhole principle). Therefore by the division algorithm we may write $x = 2k, y = 2m+1$ (wlog that $x$ is the even one). Then $x+y = 2k + 2m + 1 = 2(k+m) + 1$ which is manifestly odd.