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

• Dec 9th 2010, 05:14 PM
emonimous
[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!
• Dec 9th 2010, 05:44 PM
Plato
BUT what the heck is the question?

You did not bother to tell us what the question asks.
• Dec 9th 2010, 05:52 PM
emonimous
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"
• Dec 9th 2010, 07:26 PM
Plato
Actually this problem is written backwards.
You need to find the relation $R_1\cap R_2$ first!
Is $R_1\cap R_2$ mod 12 ?
• Dec 10th 2010, 03:22 AM
emakarov
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, $R_1\cap R_2=\{(a,b): a\equiv b\pmod{12}\}$ 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).

$R_1\cup R_2=\{(a,b):3\mid a-b\lor 4\mid a-b\}$; I don't know how to simplify this further. Note that this is not an equivalence relation because it is not transitive.
• Dec 10th 2010, 06:20 AM
emonimous
Quote:

Originally Posted by emakarov
You are right, $R_1\cap R_2=\{(a,b): a\equiv b\pmod{12}\}$ 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
$R_1\cup R_2=\{(a,b):3\mid a-b\lor 4\mid a-b\}$; 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.
• Dec 10th 2010, 07:35 AM
emakarov
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 $n\equiv r\pmod{12}$ for $r\in\{0,3,4,6,8,9\}$. 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).