Proving that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even. Here is the proof:

Let $a,b \in \mathbb{Z}$. Prove that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even.

When working these problems, I do try to set them up logically. My scratch work usually looks something like this:

$P: a+b$ and $ab$ are the same parity
$Q: a$ and $b$ are even
$P \Rightarrow Q:$ If $a+b$ and $ab$ are the same parity, then $a$ and $b$ are even.
$Q \Rightarrow P$: If $a$ and $b$ are even, then $a+b$ are the same parity.

For some reason, I am getting caught up on writing the contrapositive of this statement when addressing the forwards ($P \Rightarrow Q$) direction of this biconditional.
Here is what I was thinking:

If $a$ or $b$ is not even (odd), then $a+b$ or $ab$ are of different parity.

I believe I am negating too much, and this is where I struggle: what would the proper negation look like? How do I know what to negate (or switch) vs. what I should leave alone? I generally get that "and" becomes an "or", but then I feel like I start to negate too much (if that makes sense...).
Any advice? I can usually get this far pretty easily, but I wanted to use contrapositive for $P \Rightarrow Q$, and I don't believe I am writing the statement correctly. In addition to verifying this, I would appreciate any advice when it comes to what portion of my statement I should negate. Thanks!
 A: You have the contrapositive right. You must negate $P$ and $Q$ separately and prove that the negation of $Q$ implies the negation of $P$.
To expand on this, for "$a$ and $b$ are even" to be false, you only need one of $a$ and $b$ to be odd, so the negation is "$a$ is not even or $b$ is not even". 
And for the statement "$a+b$ and $ab$ have the same parity" to be false, you need $a+b$ and $ab$ to have different parity, which is what you wrote.
(Something interesting about writing the proof of this direction by contrapositive is that you get to use a "without loss of generality", because the expressions $a+b$ and $ab$ are symmetric. If you were proving it directly, you'd have to treat two cases, one where both expressions are even, and one where both are odd.)

EDIT: Clarification of the and/or discussion in the comments. 
I'll try to illustrate the difference between an and that is negated into an or and an and that isn't.
In the statement

$a$ and $b$ are even

you have a logical and, which turns into an or in the negation:

$a$ is odd or $b$ is odd  

which can also be written as

$a$ or $b$ is odd

The difference between this statement and yours is that this statement can actually be written as two statements connected by an and:

$a$ is even and $b$ is even

If we let $E(x)$ be the statement "$x$ is even", then the whole statement above is $E(a) \land E(b)$, meaning its negation is $\lnot E(a)\lor \lnot E(b)$.
In contrast, we can't rewrite your statement ($a+b$ and $ab$ have the same parity) as two statements connected with an and,  because it makes no sense to say

$a$ has the same parity and $b$ has the same parity

This happens because "$a$ and $b$ have the same parity" is a statement about two quantities, not two statements, each about one quantity, connected by an and.

Here is another (maybe simpler) example: 

Alice and Bob like pizza

Can be rewritten as 

Alice likes pizza and Bob likes pizza

So its negation is 

Alice or Bob doesn't like pizza

However, the statement

Alice and Bob are friends

cannot be rewritten as 

Alice is friend and Bob is friend

so its negation is 

Alice and Bob are not friends

Basically you have to evaluate whether the statement you're trying to negate is a statement relating two quantities (in which case the and isn't negated into an or) or two individual statements, each about one quantity, connected by a logical and (which is negated into an or). I hope this clarifies things a little.

(A side note: In the cases where the and is not logical, it is also not essential to the meaning of the sentence.
We could rephrase your statement as  "$a+b$ has the same parity as $ab$"; then its negation is more clearly $a+b$ does not have the same parity as $ab$. Similarly,  we could rephrase the second example as "Alice is friends with Bob"; then its negation is "Alice is not friends with Bob". (This is a side note because it's trickier and it might be harder to generalize.))
A: 
What would the proper negation look like? 

It turns out that, in this case, there are a number of ways you can go in how you want to prove this claim, not just via direct proof or contrapositive but also how you frame the question logically as well. I'll outline what I think is the clearest and easiest way of going about it.

Claim: Let $a,b\in\mathbb{Z}$. If $a+b$ and $ab$ have the same parity, then $a$ and $b$ are even. 
Proof. Begin by writing out the claim logically, as you have done before:


*

*$P : a+b$ and $ab$ have the same parity.

*$Q : a$ and $b$ are both even.


Hence, you are trying to prove that $P\to Q$, something you can prove by contraposition since $P\to Q\equiv\neg Q\to\neg P$. Hence, formulate the negations of $P$ and $Q$:


*

*$\neg P : a+b$ and $ab$ do not have the same parity (this is an easier formulation than trying to mess with some application of DeMorgan). 

*$\neg Q : a$ or $b$ is odd (or both). 


Thus, to prove $\neg Q\to\neg P$, you need to prove the following:

If $a$ or $b$ are odd, then $a+b$ and $ab$ do not have the same parity. 

Note that there are three cases to consider:


*

*$a$ is odd and $b$ is even.

*$a$ is even and $b$ is odd.

*$a$ is odd and $b$ is odd.


As coldnumber pointed out, you can essentially "lump together" (1) and (2) due to symmetry (so called "without loss of generality"). So you ultimately need to consider, say, (1) and (3). I'll prove them below, and their proofs will conclude the overall proof. 
Proof of (1): Let $a=2\ell+1, \ell\in\mathbb{Z}$ and $b=2\eta, \eta\in\mathbb{Z}$. Then we have that 
$$
a+b=2\ell+1+2\eta=2(\ell+\eta)+1=2\gamma+1,\gamma\in\mathbb{Z}\tag{$a+b$ is odd}
$$
and
$$
ab=(2\ell+1)2\eta=2[\eta(2\ell+1)]=2\gamma, \gamma\in\mathbb{Z}.\tag{$ab$ is even}
$$
This proves (1). $\blacksquare$
Proof of (3): Let $a=2\ell+1, \ell\in\mathbb{Z}$ and $b=2\eta+1, \eta\in\mathbb{Z}$. Then we have that
$$
a+b=(2\ell+1)+(2\eta+1)=2(\ell+\eta+1)=2\gamma, \gamma\in\mathbb{Z}\tag{$a+b$ is even}
$$
and
$$
ab=(2\ell+1)(2\eta+1)=4\ell\eta+2\ell+2\eta+1=2(2\ell\eta+\ell+\eta)+1=2\gamma+1, \gamma\in\mathbb{Z}.\tag{odd}
$$
This proves (3). $\blacksquare$
A: The contrapositive of the statement

If $\overbrace{\text{$ab$ and $a+b$ have the same parity}}^{\large P}$, then $\overbrace{\text{$a$ is even and $b$ is even}}^{\large Q}$.

is

If $\overbrace{\text{$a$ is odd or $b$ is odd}}^{\large\lnot Q}$, then $\overbrace{\text{$ab$ and $a+b$ have different parities}}^{\large\lnot P}$.

Note that $Q$ is the conjunction $S\land T$, where $S$ means "$a$ is even" and $T$ means "$b$ is even". Thus, $\lnot Q$ is the disjunction $\lnot S\lor\lnot T$.

Here is an alternate approach:
$\begin{array}{cr}
\text{$ab$ and $a+b$ have the same parity}\\
\Updownarrow&\qquad\text{(1)}\\
\text{$ab-(a+b)$ is even}\\
\Updownarrow&\qquad\text{(2)}\\
\text{$(a-1)(b-1)$ is odd}\\
\Updownarrow&\qquad\text{(3)}\\
\text{$a-1$ is odd and $b-1$ is odd}\\
\Updownarrow&\qquad\text{(4)}\\
\text{$a$ is even and $b$ is even}\\
\end{array}$
Comments:
$(1)$: $m$ and $n$ have the same parity if and only if $m-n$ is even
$(2)$: $ab-(a+b)=(a-1)(b-1)-1$
$(3)$: $mn$ is odd if and only if both $m$ and $n$ are odd
$(4)$: $a-1$ has the opposite parity from $a$
A: This answer is close to robjohn's answer, written in very similar 'calculational' style designed and used by Edsger W. Dijkstra, Carel S. Scholten, et al.: see EWD1300 for more details.$
\newcommand{\calc}{\begin{align} \quad &}
\newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}}
\newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} }
\newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & }
\newcommand{\endcalc}{\end{align}}
\newcommand{\ref}[1]{\text{(#1)}}
\newcommand{\even}[1]{#1\text{ is even}}
$
We calculate as follows:
$$\calc
    a + b\text{ and }ab\text{ have the same parity}
\op\equiv\hint{definition of parity}
    \even{a + b} \;\equiv\; \even{ab}
\op\equiv\hint{LHS: either both or none are even; RHS: at least one is even}
    \even a  \;\equiv\; \even b \;\equiv\; \even a \lor \even b
\op\equiv\hint{logic: what Dijkstra et al. call the 'golden rule' $\ref{0}$}
    \even a \land \even b
\endcalc$$
Here the 'golden rule' is the following law of propositional logic:
$$
\tag{0}
P \land Q \;\equiv\; P \lor Q \;\equiv\; P \;\equiv\; Q
$$
Also note that logical equivalence $\;\equiv\;$ ("if and only if") is associative, so that no parentheses are necessary in that last statement.
A: Consider $f(X) = (X-a)(X-b) = X^2 - (a+b)X + ab$.
Since $f(X) \equiv X^2\pmod{2}$, it follows that its roots are even.
A: Consider the parity tables.
Addition $+$
$$
\begin{array}{cc|cc|cc}
+ &   & a & a & b & b\\
  &   & o & \bbox[4px,border:2px solid #008000]e & o & \bbox[4px,border:2px solid #008000]e\\
\hline
a & o & e & o & e & o\\
a & \bbox[4px,border:2px solid #008000]e & o & \bbox[4px,border:2px solid #800000]e & o & \bbox[4px,border:2px solid #800000]e\\
\hline
b & o & e & o & e & o\\
b & \bbox[4px,border:2px solid #008000]e & o & \bbox[4px,border:2px solid #800000]e & o & \bbox[4px,border:2px solid #800000]e
\end{array}
$$
Multiplication $\cdot$
$$
\begin{array}{cc|cc|cc}
\cdot &   & a & a & b & b\\
      &   & o & \bbox[4px,border:2px solid #008000]e & o & \bbox[4px,border:2px solid #008000]e\\
\hline
a     & o & o & e & o & e\\
a     & \bbox[4px,border:2px solid #008000]e & e & \bbox[4px,border:2px solid #800000]e & e & \bbox[4px,border:2px solid #800000]e\\
\hline
b     & o & o & e & o & e\\
b     & \bbox[4px,border:2px solid #008000]e & e & \bbox[4px,border:2px solid #800000]e & e & \bbox[4px,border:2px solid #800000]e
\end{array}
$$
Clearly both $a$ and $b$ are even.
