# Proof: sum of even and odd integer is odd

Statement: Sum of even and odd integer is odd

$$\forall(a,b) \in \mathbb{Z} : a \text{ mod } 2 = 0 \wedge b \text{ mod } 2 \neq 0 \implies a + b \text{ mod } 2 \neq 0$$

Proof:

$$a \text{ mod } 2 = 0 \implies \exists n \in \mathbb{Z}: a = 2n$$ $$b \text{ mod } 2 \neq 0 \implies \exists k \in \mathbb{Z}: b = 2k +1$$

$$\implies (2n+2k+1) \text{ mod } 2 \neq 0 \implies \exists q \in \mathbb{Z}: 2q+1 = (2n+2k+1)$$

$$\implies q = n + k$$

Not quite sure if this is correct or not. To me it would seem it's correct but could i have comment on this?

## 2 Answers

No, it is not correct, because of those $$\implies$$ signs. You wish to prove that$$a+b\not\equiv0\pmod2,\tag1$$which means that $$2n+2k+1\not\equiv0\pmod2$$. Therefore, you should have used a $$\iff$$ sign here. And you should also use that sign after that, since you wish to prove $$(1)$$, not to extract conclusions from it.

It is not correct for the use of the implication mark. You have to write in a different way the last part. Below is my suggestion.

We have:

• $$a=0\pmod{2} \Rightarrow \exists n\in\mathbb{Z}\,:\, a=2n$$
• $$b\neq 0 \pmod{2} \Rightarrow \exists k\in\mathbb{Z} \,:\, b=2k+1$$

Both the above imply $$a+b = 2n+2k+1 = 2(n+k)+1$$ and this is $$\neq 0\pmod{2}$$ because $$\exists q\in\mathbb{Z}\,:\,a+b=2q+1$$, and in particular $$q=n+k$$.