Results 1 to 6 of 6

Math Help - Reduced residue system modulo m

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Reduced residue system modulo m

    Definition:
    A reduced residue system modulo m is a set of integers such that
    (i) gcd(r_i, m) = 1,
    (ii) r_i ≡/≡ r_j (mod m) if i≠j,
    (iii) AND such that EVERY x relatively prime to m is congruent modulo m to some member r_i of the set.
    ==================================

    I am concerned about the last part of the definition. So according to this definition, is it even possible to tell whether a set is a reduced residue system modulo m? (because we have to check that EVERY x relatively prime to m is congruent modulo m to some member r_i of the set, which doesn't seem possible? How can we check every single x?)

    For example, how do we know whether {1, 5, 7, 11} is a reduced residue system modulo 12 or not? Look at part (iii) of the definition, we need to check that EVERY x relatively prime to 12 is congruent modulo 12 to some member r_i of the set. But I think there are many many such numbers, how can we possibly check them all?

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    Definition:
    A reduced residue system modulo m is a set of integers such that
    (i) gcd(r_i, m) = 1,
    (ii) r_i ≡/≡ r_j (mod m) if i≠j,
    (iii) AND such that EVERY x relatively prime to m is congruent modulo m to some member r_i of the set.
    ==================================

    I am concerned about the last part of the definition. So according to this definition, is it even possible to tell whether a set is a reduced residue system modulo m? (because we have to check that EVERY x relatively prime to m is congruent modulo m to some member r_i of the set, which doesn't seem possible? How can we check every single x?)

    For example, how do we know whether {1, 5, 7, 11} is a reduced residue system modulo 12 or not? Look at part (iii) of the definition, we need to check that EVERY x relatively prime to 12 is congruent modulo 12 to some member r_i of the set. But I think there are many many such numbers, how can we possibly check them all?

    Thank you.
    But, every x is congruent to \ell for some \ell\in\{0,\cdots,m-1\}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    You can show that all numbers x with gcd(x,12) = 1 is of the form x=12q+r_i, with  r_i \in \left\{1,5,7,11\right\}

    Or by contradiction: suppose this is not the case then gcd(x,12) \neq 1

    (hint:you can do this by showing that x\equiv 0 mod 3, or x\equiv 0 mod 2)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Drexel28 View Post
    But, every x is congruent to \ell for some \ell\in\{0,\cdots,m-1\}
    Then what is the point of having part (iii) in the definition?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    Then what is the point of having part (iii) in the definition?
    You tell me.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    I am guessing. I think (iii) is to avoid saying things like {7, 11} is a reduced residue system modulo 12. {7, 11} satisfies both (i) and (ii), but not (iii)

    But still I think (iii) is a very hard criteria to check. To tell whether a very large natural number x is relatively prime to m or not is already very difficult (e.g. how can we tell whether 61 and 654236 are relatively prime or not? how about 61 and 5648796545?), let alone determining whether ALL such numbers is congruent modulo m to some member r_i of the set. I don't see how (iii) can serve as a useful criterion.
    Last edited by kingwinner; January 20th 2010 at 09:30 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primitive roots & Reduced residue system
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: March 4th 2010, 06:51 AM
  2. Distinct residue modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 24th 2009, 03:08 PM
  3. Proof with reduced residue systems
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: November 11th 2009, 01:33 PM
  4. complete residue modulo
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 5th 2009, 03:53 PM
  5. residue modulo - wilson's theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 10:36 AM

Search Tags


/mathhelpforum @mathhelpforum