How can we prove that integers can be defined as odd or even?

1. Dec 16, 2015

Alpharup

Iam working through Spivak calculus now.
The book defines natural numbers as of form N=1,2,3,4....
Iam able to prove that every natural number is either odd or even. How can I extend to Z, integers?
In one of the problems, Spivak says we can write any integer of the form 3n, 3n+1, 3n+2.( n is integer) He gives as hint to the problem.But am not convinced,
In general how can we prove that if m is a natural number, n is an integer, then
any integer can be expressed of the form km, km+1, km+2, km+3,.....,km+(k-1)?

2. Dec 16, 2015

Erland

If you have a negative integer n = -m, and k>0, then there are integers q,r, with 0≤r<k such that m = kq + r.
What can you then say about n?

(Hint: r = k - (k - r) ).

3. Dec 16, 2015

WWGD

Like Erland suggested, it basically comes down to the fact that an integer m divided by n, can have possible remainders 0,1,...m-1. As he suggested, you can use the Euclidean algorithm to prove this.

4. Dec 18, 2015

Alpharup

Spivak has not mentioned about Euclid algorithm. Could you help me with some other way?

Last edited: Dec 18, 2015
5. Dec 18, 2015

Alpharup

I did think of alternate proof like this. Let A be a set of integers which can't be expressed of the form 3n, 3n+1, 3n+2: where n is an integer
Every non-null set of integers has a smallest member. Let it be s.
Consider s-1. s-1 must be expressed of the form 3n, 3n+1, 3n+2. Orelse, it belongs to A, resulting in contradiction.
Now the proof involves equating s-1 to either of these 3 forms: 3n, 3n+1,3n+2
By equating we can easily find that, s is of the form 3n, 3n+1, 3n+2. Hence s does not belong to A. A is null set. So, every integer exists of this form.

6. Dec 18, 2015

Samy_A

Nitpick:
This is not correct. Every non-null set of natural numbers has a smallest member.

Your proof only works for positive integers, but of course once you have it for positive integers, you can easily extend it to all integers (by considering -n if n is negative).

7. Dec 18, 2015

Alpharup

Yeah...you are right....we can prove for natural numbers( postive integers) . For negative integers, we can sustidute -n. I tried proving s does not belong to A. I can easily prove -s does not belong to A. but what about s?

8. Dec 18, 2015

Samy_A

You have established that each natural number n can be expressed as 3k, 3k+1 or 3k+2.
If n is a negative integer, -n is positive. So -n can be expressed as 3k, 3k+1 or 3k+2.
Just as an example, say -n=3k+1, then n=-3k-1.
We don't like that -1, but that is easily fixed: n=-3(k+1)+3-1=3(-k-1)+2.

But it really boils down to what @Erland and @WWGD said before: when you divide an integer by a natural number m, the remainder can only be 0,1,2, ..., m-1.

9. Dec 18, 2015

Alpharup

nailed it...thanks

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook