# Equivalence Classes

1. Dec 16, 2009

### PolyFX

1. The problem statement, all variables and given/known data
$$\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$$

*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. Dec 16, 2009

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

3. Dec 16, 2009

### PolyFX

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?

4. Dec 16, 2009

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

5. Dec 16, 2009

### PolyFX

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.

6. Dec 16, 2009

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