# Prove Z can be partitioned into 3 parts

1. Sep 21, 2009

### gotmilk04

1. The problem statement, all variables and given/known data
Prove that Z can be partitioned as Z= 3Z $$\cup$$ (1+3Z) $$\cup$$ (2+3Z),
where m+3Z={m_3n| n$$\in Z$$}

2. Relevant equations

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

2. Sep 21, 2009

### aPhilosopher

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

3. Sep 21, 2009

### gotmilk04

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

4. Sep 21, 2009

### aPhilosopher

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

5. Sep 21, 2009

### gotmilk04

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

6. Sep 21, 2009

### 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?

7. Sep 21, 2009

### 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?

8. Sep 21, 2009

### 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?

9. Sep 21, 2009

### 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?

10. Sep 21, 2009

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