Prove Z can be partitioned into 3 parts

[gotmilk04]

Homework Statement

Prove that Z can be partitioned as Z= 3Z $$\cup$$ (1+3Z) $$\cup$$ (2+3Z),
where m+3Z={m_3n| n$$\in Z$$}

Homework Equations

The Attempt at a Solution

Not sure how to start to prove this. I know it has to do with the remainder when an arbitrary integer is divided by 3, but I don't know how to proceed.

 

[aPhilosopher]

When dividing $$n \in \textbf{Z}$$ by 3 and taking the remainders, what are the possible values?

 

[gotmilk04]

You can get either 0, 1, or 2 as the remainder.

 

[aPhilosopher]

What would happen if n had remainder b and remainder c after being divided by 3 with b and c not equal?

 

[gotmilk04]

How would that be possible without b and c being equal?

 

[aPhilosopher]

Can you show that it causes a contradiction? Another way to do it is to show that b and c are equal as you said.

There are two things that you need to prove and you already know how to do both of them. Do you know what they are?

 

[gotmilk04]

I need to prove that when n is divided by 3 it has a unique remainder (0,1 or 2) and that these three groups make up all of Z, right?

 

[aPhilosopher]

correct.

put another way:

1) every integer is in one of the sets
2) every integer is in only one of the sets

what are some theorems you've learned that can help with 1?

 

[gotmilk04]

Any pair of equivalence classes is either equal or disjoint
and equivalence classes form a partition of the set?
So if I show that there are three equivalence classes, that would prove it?

 

[aPhilosopher]

Yeah that would do it. I didn't know if you knew equivalence classes or not.

So you could define an equivalence relation and show that it's transitive, reflexive and symmetric and then apply the theorem that you quoted. That's three things that you need to prove.

I'd just use the definition of division to establish the equivalence classes directly as that's only two things that need to be proved.

Either way though. One wouldn't be much harder than the other.