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.

  • 1
    $\begingroup$ contrapositive is 'if x,y have different parities, x+y is odd' $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.