Proving that all integers are even or odd [duplicate]

I know that $\mathbb{Z}$ is a group under addition with a multiplication defined. I have just the definition of even and odd integers: $n$ is even if $n = 2k$ for some integer $k$ and $n$ is odd if $n = 2k+1$ for some integer $k$.

Using just this I am wondering how to prove that all integers are either even or odd. That is, how can I prove that given an integer $n$, $n$ must be even or odd?

My problem with this is that it seems so simple. I know that one can divide an integer by $2$ and the remainder will be $0$ or $1$. Using this, it is clear that the even and odd integers make up everything. But how can I prove it without using this fact about remainders and such? I guess one could also use facts about prime numbers, but I am looking for a proof that just uses the definition of odd and even.

Solution 1:

If you really want to avoid using general facts about division with remainder, you can use mathematical induction on $n$ to prove it for nonnegative integers:

Base case: $0$ is even because $0=2\cdot 0$.

Induction step: Assume that $n$ is odd or even; then we must prove that $n+1$ is also either odd or even.

First subcase: $n$ is even, so $n=2k$ for some $k$. Then $n+1=2k+1$ and so it is by definition odd.

Second subcase: $n$ is odd, so $n=2k+1$ for some $k$. Then $n+1=2k+1+1=2k+2=2(k+1)$, and so $n+1$ is even.

That completes the induction proof, and now we just need to know that negative integers are also all either odd or even. But if $n$ is negative, then $-n$ is positive. One easily sees that if $-n$ is even, then $n$ is even too, and if $-n$ is odd, then $n$ is odd too.

Whether this satisfies your requirements is a bit debatable, because the induction part of the proof is essentially the same as how you prove that division with remainder works in general.

However, you CANNOT prove that every integer is either odd or even solely from the fact that the integers form "a group under addition with a multiplication defined", that is a commutative ring with unit. The reason for this is that there are some rings where not all elements are either odd or even -- such as $\mathbb Z[X]$, the ring of polynomials with integer coefficients. Here the polynomial $X+1$ is neither twice something, nor twice something plus one.

Solution 2:

Suppose that $n>0$ is an integer which neither odd nor even. So, if $n$ is not odd, it cannot be of the form $2k+1$. Also since it is not even it cannot be of the form $2k$. From this it follows that $n-1$ is also neither even, nor odd. Apply this argument repeatedly so long as your $n>1$. At one stage you are forced to conclude that $0$ is neither even nor odd which is a contradiction since $0=2\cdot 0$.

When $n<0$ we play the game with $-n$.

Solution 3:

I prefer appealing to the well-ordering principle. It's equivalent to induction but in my opinion a tiny bit cleaner.

First, reduce the proposition to the statement that all positive integers are odd or even. If there exist positive integers that are neither odd nor even, there must be a smallest positive integer $n$ which is neither odd nor even. Since $1$ is definitely odd, $n \geq 2$, hence $n-1$ is still positive. Since $n$ is the least positive integer that is neither odd nor even, $n-1$ must be either odd or even.

• If $n-1$ is even, $n-1 = 2k$ for some $k$. But this implies $n=2k+1$, i.e., $n$ is odd.
• If $n-1$ is odd, $n-1 = 2k+1$ for some $k$. But this implies $n=2k+2 = 2(k+1)$, i.e., $n$ is even.

Either way we have a contradiction, so the set of positive integers which are neither even nor odd is empty.