Results 1 to 7 of 7

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

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    15

    [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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    BUT what the heck is the question?

    You did not bother to tell us what the question asks.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    15
    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"
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    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 ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Sep 2009
    Posts
    15
    Quote Originally Posted by emakarov View Post
    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 View Post
    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.
    Last edited by emonimous; December 10th 2010 at 06:29 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular exponentiation/recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 2nd 2012, 03:27 PM
  2. discrete math - equivalence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 24th 2008, 10:26 AM
  3. discrete math:functions,recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 18th 2008, 01:49 AM
  4. Modular Arithmatic
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 31st 2008, 05:00 PM
  5. Discrete Math Problem - Relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 27th 2007, 08:08 PM

Search Tags


/mathhelpforum @mathhelpforum