Thread: Prove that every natural number is either even or odd?

This question is bugging me, and it has been for some time now. I know how to use mathematical induction, but I just dont see how I can "logically" fit it into this proof! I'm sure its oversight on my behalf.

I know that every number can be written in the form or and that corresponds to all the even numbers and that corresponds to all the odd numbers. But, from my understanding mathematical induction works by steps, the whole stuff, but how can I use induction on this problem? Because niether or encompasses the whole set of positive numbers implied by induction, correct? Becuase in either set, they are missing "half" the numbers?

How do you get around this and use induction (I'm sure, like I said, the answer is right under my nose, and is very obvious, but I'm just not seeing it), or any proof for that matter, to prove that evey natural number is either of the form or . Thanks in advance.

Use strong induction. Break up your inductive step into two cases: is even and is odd.

In PlanetMath: division algorithm for integers you can find a very short, useful information on the Division Algorithm.

For any two integers and , we can always a unique pair of integers such that , with . ( is the remainder)

In particular, choose , then for any integer , you have , or .

From the Divistion Algorithm, we also know that any integer is exactly one of the forms , , or .