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

[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)?

 

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

 

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

 

[Alpharup]

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

 

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

 

[Samy_A]

Nitpick:

Every non-null set of integers has a smallest member. Let it be s.

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

 

[Alpharup]

Yeah...you are right...we can prove for natural numbers( positive 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?

 

[Samy_A]

Yeah...you are right...we can prove for natural numbers( positive 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?

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.

 

[Alpharup]

nailed it...thanks