1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove Z can be partitioned into 3 parts

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

    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. jcsd
  3. Sep 21, 2009 #2
    When dividing [tex]n \in \textbf{Z}[/tex] by 3 and taking the remainders, what are the possible values?
  4. Sep 21, 2009 #3
    You can get either 0, 1, or 2 as the remainder.
  5. Sep 21, 2009 #4
    What would happen if n had remainder b and remainder c after being divided by 3 with b and c not equal?
  6. Sep 21, 2009 #5
    How would that be possible without b and c being equal?
  7. Sep 21, 2009 #6
    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?
  8. Sep 21, 2009 #7
    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?
  9. Sep 21, 2009 #8

    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?
  10. Sep 21, 2009 #9
    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?
  11. Sep 21, 2009 #10
    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook