1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    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!

Homework Help: Equivalence Classes

  1. Dec 16, 2009 #1
    1. The problem statement, all variables and given/known data
    [tex]
    \forall (a,b), (c,d) \in (Z^2), (a,b)D(c,d) \leftrightarrow a\equiv c\mod\2\and\b\equiv d mod 3
    [/tex]

    *edit* Sorry the b = d mod 3 is all part of the same line.

    (a) List four elements of the equivalence class [{5,3}]

    (b) How many equivalence classes of D are there in total? List a representative element of each of them.


    2. Relevant equations



    3. The attempt at a solution

    (5,3)D(c,d)

    a = c mod 2 can also be written as 2 = a-c
    b = d mod 3 can also be written as 3 = b-d

    Would I need to somehow use the above two lines in this problem?

    I'm very lost on this one and have no clue where to start.
     
  2. jcsd
  3. Dec 16, 2009 #2

    Mark44

    Staff: Mentor

    I took the liberty of cleaning up your LaTeX formatting to make everything visible.
    In mod 2 arithmetic, every integer is congruent to either 0 or 1. In mod 3 arithmetic, every integer is congruent to 0, 1, or 2. For a pair of numbers, this represents 6 possibilities.
     
  4. Dec 16, 2009 #3
    Hi mark thank you for your reply,


    So "a mod b" is always going to produce an integer "b - 1"?

    So for part a here is what I have so far;

    a == c mod 2
    => a mod 2 = c mod 2

    we let a = 5

    so 5 mod 2 = c mod 2

    Is this correct so far?


    -Thank you in advance.
     
  5. Dec 16, 2009 #4

    Mark44

    Staff: Mentor

    I don't know what you mean by "b - 1". a mod b will be one of b integer values: 0, 1, 2, 3, ..., b - 1. a mod b is the remainder after a is divided by b.
    Yes, but you're not really getting all that far. 5 mod 2 = 1, 7 mod 2 = 1, 6 mod 2 = 0. In mod 2 arithmetic, every integer is put into one of two buckets: all the odd integers go in one bucket, and all the even integers go in the other bucket.

    In mod 3 arithmetic, all integers go into one of three buckets. 3, 6, 9, ... go into one bucket. 4, 7, 10, ... go into another bucket, and 5, 8, 11, ... go into the third bucket. Each number in the first group here is congruent to 0 mod 3. Each number in the second group is congruent to 1 mod 3, and each number in the third group is congruent to 2 mod 3.
     
  6. Dec 16, 2009 #5
    Oh I see now.

    so

    5 mod 2 = 1
    c mod 2 = 1

    therefore c can be 5, 7, 9, 11, etc. since 7/2 has a remainder of 1 and 9/2 has a remainder of one.


    Similarly,

    3 mod 3 = 0 so;
    d mod 3 = 0

    therefore d can be 3, 6, 9, 12 etc.

    So would 4 ordered pairs be;

    (5,3), (7,6), (9,9), (11,12)?



    -Thanks again.
     
  7. Dec 16, 2009 #6

    Mark44

    Staff: Mentor

    Yes, those ordered pairs would be in the same equivalence class as (5, 3), as would (1, 0).

    To clarify a couple of things you wrote, if c mod 2 = 1, then c could be any odd integer, including the negative ones. All of them could be represented as {..., -3, -1, 1, 3, 5, ...}

    If d mod 3 = 0, then d is any integer that is evenly divisibly by 3. All of them would be {..., -6, -3, 0, 3, 6, 9, 12, ...}
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook