20
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by apnorton, Michael Galuza, Eric Stucky, Lord_Farin, J. M. is a poor mathematician Aug 20 '15 at 19:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ Try a proof by contradiction: find an integer that is not even and is not odd. $\endgroup$ – Jeffrey L. Aug 19 '15 at 13:18
  • 2
    $\begingroup$ This question feels very familiar. $\endgroup$ – user153918 Aug 19 '15 at 16:00
  • 1
    $\begingroup$ @JeffreyL. Okay done. Now what? $\endgroup$ – PyRulez Aug 19 '15 at 16:35
  • 1
    $\begingroup$ "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. $\endgroup$ – Matthew Leingang Aug 19 '15 at 18:40
  • 5
    $\begingroup$ 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. $\endgroup$ – Sempliner Aug 19 '15 at 21:06
43
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, this seems to be just the way to do it using induction! Thanks for this. I hadn't even thought of this. $\endgroup$ – John Doe Aug 19 '15 at 13:30
  • $\begingroup$ A simpler case, where we are talking about things usually called "numbers," is the Gaussian integers. $\endgroup$ – Thomas Andrews Aug 19 '15 at 21:26
  • 1
    $\begingroup$ @ThomasAndrews: For familiarity, $\mathbb Z[\sqrt 2]$ might do even better. $\endgroup$ – Henning Makholm Aug 20 '15 at 0:27
  • $\begingroup$ $\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) $\endgroup$ – Hurkyl Aug 20 '15 at 19:33
  • $\begingroup$ @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]$. $\endgroup$ – Henning Makholm Aug 20 '15 at 19:36
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – CBredlow Aug 19 '15 at 21:10
  • $\begingroup$ @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. $\endgroup$ – user 170039 Aug 20 '15 at 2:24
  • 2
    $\begingroup$ "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. $\endgroup$ – Taemyr Aug 20 '15 at 8:35
  • $\begingroup$ is this in fact the same as induction ? $\endgroup$ – Fattie Aug 20 '15 at 14:58
  • $\begingroup$ @JoeBlow: Yes both induction on natural numbers and well-ordering of the natural numbers are equivalent. $\endgroup$ – user21820 Aug 20 '15 at 16:17
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @MorganRodgers: It is essentially the same thing as induction, just phrased (very) slightly differently. $\endgroup$ – Henning Makholm Aug 20 '15 at 9:30
  • $\begingroup$ @HenningMakholm I wasn't meaning to insult the induction proof (and so I shouldn't)! Of course, using the well-ordering is very similar in principal (although I feel it more closely resembles a proof by contradiction). I just definitely like this: very short, very concise. Really, using division with remainder is best because it is a direct proof, and gives proper intuition on the statement (but OP wanted to avoid that). $\endgroup$ – Morgan Rodgers Aug 20 '15 at 9:38
  • $\begingroup$ 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. $\endgroup$ – Steve Jessop Aug 20 '15 at 12:41
  • $\begingroup$ 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? $\endgroup$ – Fattie Aug 20 '15 at 14:58
  • $\begingroup$ @JoeBlow: Well he means "... hence $n-1$ must be either odd or even by minimality of $n$." I agree there is a grammatical error. $\endgroup$ – user21820 Aug 20 '15 at 16:21
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ You are welcome. Almost everything about the naturals requires induction, if we wish to go back to fundamentals. $\endgroup$ – André Nicolas Aug 19 '15 at 13:34
-2
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.