We define even and odd as follows: an integer
is even if
for some integer
, and
is odd if
is even. An immediate consequence of the definition, which we will feel free to use, is that an integer
is odd if and only if
for some integer
.
- Prove than an integer cannot be both even and odd.
- Prove that every integer is either even or odd.
- Prove that the set of even integers is closed under sums and products. What can be said about sums and products of odd integers?
- Prove that if
is even,
must be even as well. Prove also that for integers
and
, if
, then both
and
must be even.
- Prove that every rational number can be written as the ratio of integers
and
at least one of which is odd.
- Proof. Suppose otherwise, that there is some
that is both even and odd. Then, there exist
such that
and
(since
is odd,
is even, so
). Hence,
![Rendered by QuickLaTeX.com \[ 2a = 2b-1 \implies 2(b-a) = 1 \implies b-a = \frac{1}{2}. \]](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-a80179c122a5226f80d13c9d87e91dfc_l3.png)
But
, contradicting the fact that the integers are closed under addition (and subtraction)
- Proof. Let
be an arbitrary integer. Then,
is a real number, so by I.3.12, Exercise #4 we know there exists
such that
![Rendered by QuickLaTeX.com \[ m \leq \frac{n}{2} < m+1 \quad \implies \quad 2m \leq n < 2m+2. \]](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-190837d07fe606b003760adc3ef03b36_l3.png)
If
, then
is even and we are done.
Otherwise, if
, then we have
![Rendered by QuickLaTeX.com \[ 2m < n < 2m+2. \]](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-ff5b4b779f63f2c1f7804d1c4f0dc4c5_l3.png)
But this implies
since
is the only integer in the interval. Thus,
is odd.
Hence, every integer is either even or odd
- Proof. Let
be even integers. Then, there exist integers
and
such that
,
. Then,

where
and
are integers. Hence,
and
are both even
Next, we claim the sum of two odd integers is even, and the product of two odd integers is odd.
Proof. Let
be odd integers. Then there exist integers
and
such that
and
. Then,

Hence,
for some integer
and
for some integer
. Therefore,
is even and
is odd, as claimed
- Proof. Let
with
even. Since
and we know from part (b) that
must be either even or odd and from part (a) that it cannot be both. By part (c) the product of two even integers even, while the product of two odd integers is odd; hence, we must have
even (otherwise
would be the product of two odd integers and would have to be odd).
Next, if
and
are integers with
, then
is even by definition (since it equals
for some integer
). So, by the above we know
is even, say
. Then
. But then we have,
![Rendered by QuickLaTeX.com \[ 2b^2 = 2(2k^2) \quad \implies \quad b^2 = 2k^2 \]](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-b7ad425fe28e4e58cff05f6112fc1325_l3.png)
and by the same reasoning that lead to
even, we also have
must be even. Thus, both
and
are even
- Proof. Let
be a rational number with
. If
and
are both even, then we have
![Rendered by QuickLaTeX.com \[ a = 2c \text{ and } b = 2d \qquad \implies \quad \frac{a}{b} = \frac{2c}{2d} = \frac{c}{d}, \]](https://www.stumblingrobot.com/wp-content/ql-cache/quicklatex.com-8ff1349bb873d1f22f575b638374345f_l3.png)
with
, and
. Now, if
and
are both even, repeat the process. This will give a strictly decreasing sequence of positive integers, so the process must terminate by the well-ordering principle (see I.4.3, p. 34 in Apostol, Calculus, Volume I ). Thus, we must have some integers
and
, not both even with
. This was the requested property