text: # [Discrete math]Help with a relation involving modular arithmatic and set operations
  
  • Dec 9th 2010, 04: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, 04:44 PM
  Plato
  BUT what the heck is the question?
  
  You did not bother to tell us what the question asks.
  • Dec 9th 2010, 04: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, 06:26 PM
  Plato
  Actually this problem is written backwards.
  You need to find the relation $\displaystyle R_1\cap R_2$ first!
  Is $\displaystyle R_1\cap R_2$ mod 12 ?
  • Dec 10th 2010, 02: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, $\displaystyle 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).
  
  $\displaystyle 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, 05:20 AM
  emonimous
  Quote:
  
  Originally Posted by emakarov
  You are right, $\displaystyle 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
  $\displaystyle 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, 06: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 $\displaystyle n\equiv r\pmod{12}$ for $\displaystyle 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).