# 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.

• Try a proof by contradiction: find an integer that is not even and is not odd. Commented Aug 19, 2015 at 13:18
• This question feels very familiar.
– user153918
Commented Aug 19, 2015 at 16:00
• @JeffreyL. Okay done. Now what? Commented Aug 19, 2015 at 16:35
• "I know that one can divide an integer by 2 and the remainder will be 0 or 1". This statement is equivalent to what you want to prove. And it also requires the well-ordering principle or induction of some sort. Commented Aug 19, 2015 at 18:40
• Suppose there was a number that was neither odd nor even. That would be odd. This contradicts our original assumption and thus this number cannot exist. Commented Aug 19, 2015 at 21:06

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.

• Yes, this seems to be just the way to do it using induction! Thanks for this. I hadn't even thought of this. Commented Aug 19, 2015 at 13:30
• A simpler case, where we are talking about things usually called "numbers," is the Gaussian integers. Commented Aug 19, 2015 at 21:26
• @ThomasAndrews: For familiarity, $\mathbb Z[\sqrt 2]$ might do even better. Commented Aug 20, 2015 at 0:27
• $\mathbb{Z}[\sqrt{2}]$ is a bad choice, since it's especially nonobvious whether $\sqrt{2}$ should be considered even or not. (although in the Gaussian integers, $1+i$ suffers from a similar worry)
– user14972
Commented Aug 20, 2015 at 19:33
• @Hurkyl: I'd say that's the point -- the OP has defined even and odd to mean, respectively, "twice something" and "one plus twice something", and $\sqrt2$ has is neither of these properties in $\mathbb Z[\sqrt2]$. Commented Aug 20, 2015 at 19:36

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$.

• Sorry if my logic is wrong, but if n is 2k, then n- 1 = 2k-1, which is 2(k-1) +1, which is odd? So even if n < 0, you can still apply the 2k or 2k+1 proof? Commented Aug 19, 2015 at 21:10
• @CBredlow: You are right. But actually what I wanted to get was a number which we know to be either even or odd. That's why the argument is framed that way.
– user170039
Commented Aug 20, 2015 at 2:24
• "At one stage you are forced to conclude that 0 is neither even nor odd which is a contradiction since 0=2⋅0." You skip a step to reach this conclusion. You need the fact that the natural numbers are well ordered to ensure that you will eventually reach 0. Commented Aug 20, 2015 at 8:35
• is this in fact the same as induction ? Commented Aug 20, 2015 at 14:58
• @JoeBlow: Yes both induction on natural numbers and well-ordering of the natural numbers are equivalent. Commented Aug 20, 2015 at 16:17

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.

• @MorganRodgers: It is essentially the same thing as induction, just phrased (very) slightly differently. Commented Aug 20, 2015 at 9:30
• What the questioner wants to prove fundamentally is that "division by 2 with remainder 0 or 1" is possible. As such, proving it from a general result about remainders without proving the general case is delightfully short but it isn't want I'd call "direct", it's what I'd call "begging the question" ;-) I think the questioner's urge to seek a different proof is a very sound one! Someone with more experience finds it best to go straight for the most general result, but to the questioner proving it first for 2 and later proving a remainder theorem probably is best. Commented Aug 20, 2015 at 12:41
• fyi the sentence "So n−1 is still positive, hence by minimality of n must be either odd or even." has some sort of typo or grammatical problem? Commented Aug 20, 2015 at 14:58
• @JoeBlow: Well he means "... hence $n-1$ must be either odd or even by minimality of $n$." I agree there is a grammatical error. Commented Aug 20, 2015 at 16:21
• @JoeBlow: I don't see the error, but I've rephrased with more punctuation. Commented Aug 20, 2015 at 19:16

If one really wants to prove that every integer is even or odd, one can go back to fundamentals and first prove that every natural number is even or odd. Then the extension to integers is straightforward.

For the natural numbers (which I think of as starting at $0$), one proves the result by induction. For the induction step, we show that if $k$ is even or odd, so is $k+1$. This is easy. If $k$ is even, say $2t$, then $k+1=2t+1$. If $k$ is odd, say $2t+1$, then $k+1=2t+1+1=2(t+1)$.

• You are welcome. Almost everything about the naturals requires induction, if we wish to go back to fundamentals. Commented Aug 19, 2015 at 13:34

If you know or believe that every integer can be expressed in decimal, then this is easy: A number is even or odd according to whether the units digit in its decimal representation is even or odd. This is because $10$ is even and every single-digit number is either even or odd.

Of course, proving that every integer can be expressed in decimal (or any base) requires induction.

And if you go that route, its nicer to prove directly that every integer can be expressed in binary and the look at the units digit, which is $0$ or $1$.