Even and Odd

---

Even integer

\(Definition\)

Let \(x\) be an integer.
We say that \(x\) is even iff there is some integer \(k\) such that \(x = 2k\).

\[ \forall x \in \mathbb{Z} \,\, [ \,\, Even(x) \iff \exists k \in \mathbb{Z} \,\, (x = 2k) \,\, ] \]

Odd integer

\(Definition\)

Let \(x\) be an integer.
We say that \(x\) is odd iff there is some integer \(k\) such that \(x = 2k + 1\).

\[\begin{split} \begin{align*} \forall x \in \mathbb{Z} \,\, [ \,\, Odd(x) &\iff \exists k \in \mathbb{Z} \,\, (x = 2k + 1) \\ &\iff \lnot Even(x) \\ &\iff \lnot\exists k \in \mathbb{Z} \,\, (x = 2k) \\ &\iff \forall k \in \mathbb{Z} \,\, (x \ne 2k) \,\, ] \\ \end{align*} \end{split}\]

even x integer = even

\(Claim\)

The product of any integer and an even integer is even.

\[ \forall m, n \in \mathbb{Z} \,\, [ \,\, Even(m) \implies Even(mn) \,\, ] \]

\(Proof\)

Let \(m\) be an even integer (of the form \(2s\) for some integer \(s\)).

Let \(n\) be an odd integer (of the form \(2t + 1\) for some integer \(t\)).
Then \(mn = (2s)(2t + 1) = 4st + 2s = 2(2st + s) = 2k\) where \(k = 2st + s\).
\(\therefore mn\) is even.

Let \(n\) be an even integer (of the form \(2t\) for some integer \(t\)).
Then \(mn = (2s)(2t) = 2(2st) = 2k\) where \(k = 2st\).
\(\therefore mn\) is even.

Therefore the product of any integer and an even integer is even.

\(\blacksquare\)

odd x odd = odd

\(Claim\)

The product of two odd integers is odd.

\[ \forall m, n \in \mathbb{Z} \,\, [ \,\, (Odd(m) \land Odd(n)) \implies Odd(mn) \,\, ] \]

\(Proof\)

Let \(m\) be an odd integer (of the form \(2s + 1\) for some integer \(s\)) and let \(n\) be an odd integer (of the form \(2t + 1\) for some integer \(t\)).
Then \(mn = (2s + 1)(2t + 1) = 2^2st + 2s + 2t + 1 = 2(2st + s + t) + 1 = 2k + 1\) where \(k = 2st + s + t\).
\(\therefore mn\) is odd.

\(\blacksquare\)

An integer is even (odd) iff its square is even (odd)

\(Claim\)

An integer is even iff its square is even.

\[ \forall x \in \mathbb{Z} \,\, [ \,\, Even(x) \iff Even(x^2) \,\, ] \]

And an integer is odd iff its square is odd.

\[ \forall x \in \mathbb{Z} \,\, [ \,\, Odd(x) \iff Odd(x^2) \,\, ] \]

\(Proof \,\, by \,\, contraposition\)

\(Even(x) \implies Even(x^2)\)

Let \(x\) be an even integer (of the form \(2k\) for some integer \(k\)).
\(x = 2k \implies x^2 = 2(2k^2) = 2\ell\) where \(\ell = 2k^2\).
\(\therefore x^2\) is even.

\(Even(x^2) \implies Even(x)\) is equivalent to \(Odd(x) \implies Odd(x^2)\)

Let \(x\) be an odd integer (of the form \(2k + 1\) for some integer \(k\)).
\(x = 2k + 1 \implies x^2 = 2(2k(k + 1)) + 1 = 2\ell + 1\) where \(\ell = 2k(k + 1)\).
\(\therefore x^2\) is odd.

\(\blacksquare\)

An integer is even iff one greater than it is odd

\(Claim\)

Let \(n\) be an integer.
\(n\) is even iff \(n + 1\) is odd.

\[ \forall n \in \mathbb{Z} \,\, [ \,\, Even(n) \iff Odd(n + 1) \,\, ] \]

\(Proof \,\, by \,\, contraposition\)

\(Even(n) \implies Odd(n + 1)\).

Let \(n\) be an even integer (of the form \(2k\) for some integer \(k\)).
\(n = 2k \implies n + 1 = 2k + 1\)
\(\therefore n + 1\) is odd.

\(Odd(n + 1) \implies Even(n)\) is equivalent to \(Odd(n) \implies Even(n + 1)\).

Let \(n\) be an odd integer (of the form \(2k + 1\) for some integer \(k\)).
\(n = 2k + 1 \implies n + 1 = 2k + 2 = 2(k + 1) = 2\ell\) where \(\ell = k + 1\).
\(\therefore n + 1\) is even.

\(\therefore Even(n) \iff Odd(n + 1)\)

\(\blacksquare\)

---