For all integers m and n, if m+n is even then m and n are both even or both odd. Proof by Contradiction: ... By exercise 19 in Section 3.1, the sum of any even integer and any odd integer is odd. Thus both when m is even and n is odd and when m is odd and n is even, the sum m+n is odd.