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).
explanation: The document is a forum post from a math help website where a user is seeking assistance with a discrete math problem involving modular arithmetic and set operations. The user provides the problem statement, relevant equations, and their attempt at a solution. The problem asks to find the union and intersection of two relations, R1 and R2, defined as "congruent modulo 3" and "congruent modulo 4" on the set of integers, respectively. The user also mentions the solution for the intersection but is unsure about the union. Another user confirms the intersection and provides a solution for the union.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # [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).
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document is a forum post from a math help website where a user is seeking assistance with a discrete math problem involving modular arithmetic and set operations. The user provides the problem statement, relevant equations, and their attempt at a solution. The problem asks to find the union and intersection of two relations, R1 and R2, defined as "congruent modulo 3" and "congruent modulo 4" on the set of integers, respectively. The user also mentions the solution for the intersection but is unsure about the union. Another user confirms the intersection and provides a solution for the union.
  
  Label: question-and-answer