[Discrete math]Help with a relation involving modular arithmatic and set operations

1. The problem statement, all variables and given/known data

Let R1 and R2 be the "congruent modulo 3" and "congruent modulo 4" relations on the set of integers.


2. Relevant equations
Find:
a) R1 U R2(or R1 union R2)
b)R1 intersects R2
There is also problem c, d but I won't write these here. If I am able to solve this, then the rest should be cake.


3. The attempt at a solution

I saw the answer but frankly I'm not quite sure how to solve it.
I know that a is congruent to b(mod 4) is the same as 4|a-b and that a is congruent to b(mod 3) is the same as 3|a-b
I checked the equivalence classes of R1 and R2
R1 has 3 being
[0]r1={...,-12,-9,-6,-3,0,3,6,9,12...}
[1]r1={...,-11,-8,-5-,-2,1,4,7,10,13,...}
[2]r2={...,-10,-7,-4,-1,2,5,8,11,14...}

R2 has 4
[0]r2={...,-12,-8,-4,0,4,8,12,..}
[1]r2={...,-11,-7,-3,1,5,9,13,...}
[2]r2={...,-10,-6,-2,2,6,10,...}
[3]r2={...,-9,-5,-1,3,7,11,...}
I have tried to express that the intersection of r1 and r2 is
{(a,b)|a is congruent to b(mod 12)} as the intersection of both r1 and r2 are values that can be divided by 12. However I'm not sure how to express this in a mathematical notation. Any help or guidance would be much appreciated!

BUT what the heck is the question?

You did not bother to tell us what the question asks.

I believe I did. Let me go ahead and repost


Let R1 and R2 be the "congruent modulo 3" and "congruent modulo 4" relations on the set of integers. Find:
a) R1 U R2(or R1 union R2)
b)R1 intersects R2"

Actually this problem is written backwards.
You need to find the relation first!
Is mod 12 ?

Quote:

---

I have tried to express that the intersection of r1 and r2 is
{(a,b)|a is congruent to b(mod 12)} as the intersection of both r1 and r2 are values that can be divided by 12. However I'm not sure how to express this in a mathematical notation.

---

You are right, because for different primes p, q and for all n, we have p | n and q | n iff pq | n (here n is supposed to be a - b).

; I don't know how to simplify this further. Note that this is not an equivalence relation because it is not transitive.

Quote:

---

Originally Posted by emakarov

You are right, because for different primes p, q and for all n, we have p | n and q | n iff pq | n (here n is supposed to be a - b).

---

This is exactly what I was looking for! Thanks!

Quote:

---

Originally Posted by emakarov

; I don't know how to simplify this further. Note that this is not an equivalence relation because it is not transitive.

---

Well accoridng to this book I found on google books, the answer is
{(a,b):a-b is congruent to 0,3,4,6,8, or 9 (mod 12)}
How they got to this conclusion, I have no idea.

Quote:

---

Well accoridng to this book I found on google books, the answer is {(a,b):a-b is congruent to 0,3,4,6,8, or 9 (mod 12)}

---

To prove this, one needs to show that 3 | n or 4 | n iff for . The right-to-left direction is straightforward. For the left-to-right direction, suppose that 3 | n, i.e., n = 3m for some m. Dividing m by 4, we get m = 4k + i for 0 <= i < 4, i.e., n = 12k + 3i. The case when 4 | n is considered similarly (by dividing the ratio of n and 4 by 3).