Equivalence Classes Homework: (a) & (b)

[PolyFX]

Homework Statement

$$\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.

Homework Equations

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.

 

[Mark44]

I took the liberty of cleaning up your LaTeX formatting to make everything visible.

Homework Statement

$$\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.

Homework Equations

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.

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.

 

[PolyFX]

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.

 

[Mark44]

Hi mark thank you for your reply,


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

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.

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?

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.

-Thank you in advance.

 

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

 

[Mark44]

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