A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

Help me understand the definition of complete residue system. Definition: The set of integers {r1, r2, ..., rs} is called a complete residue system if: i) r_i not congruent to r_j whenever i ≠ j; ii) for each integer n, there corresponds an r_i such that n ≡ r_i (mod m). Is the set {1,2,3} a complete residue system mod 3?

  • This Question is Closed
  1. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I think condition (i) is easy to check. Having difficult time with condition (ii)

  2. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Condition ii just says, you need \(n\) integers to form a complete residue set in modulus \(n\)

  3. UsukiDoll
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so if we have modulo 6 would the complete residue be [0,1,2,3,4,5] ?

  4. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    condition i says, those \(n\) integers must be incongruent

  5. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Any set of \(n\) consecutive integers form a complete residue set in modulus \(n\)

  6. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @UsukiDoll that's one of them for mod 6. (I think). @ganeshie8 uhm.. yeah, it's proved in the book. if a set is a complete residue system mod m, then there exactly m elements in the set. Let's just check the conditions

  7. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    For example, in mod 3, below set satisfies condition i \[\{1,2\}\] because the integers in this set are incongruent to each other

  8. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    the same set fails condition ii because there is no element in the set that is congruent to the integer \(0\)

  9. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so the negation of (ii) is there exists an integer such that for all r_i, n is not congruent to r_i (mod m) 0 ≡ 1 (mod 3) is false 0 ≡ 2 (mod 3) is false. ok, How do I check condition (ii) for the set {1,2,3} though?

  10. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    \(1 \equiv 1\\ 2 \equiv 2\\ 3 \equiv 0\\ \) so the given set of integers are congruent to \(\{0, 1, 2\}\) in some order By euclid division algorithm, any integer can be represented in one of the forms \(3k, ~3k+1, ~3k+2\). It follows that "any" integer is congruent to one of the integers from the given set.

  11. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so if n = 3k, then let r = 3. if n = 3k+1, let r = 1 if n = 3k+2, let r = 2 3k ≡ 3 (mod 3) is true for all for all k 3k + 1 ≡ 1 (mod 3) is true for all k 3k + 2 ≡ 2 (mod 3) is true for all k

  12. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    that will do

  13. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Awesome! thank you ;)

  14. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    np, btw notice that consecutive integers is not a "required" condition, below set also forms a complete residue set modulo 3 : \[\{1,2,6\}\]

  15. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah. The book mentioned there is more than one set that forms a complete residue system mod m; though it didn't stately explicitly how many there would be or how to form such set.

  16. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    didn't *state*

  17. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    there are infinitely many, so there is not much use in thinking too much about this

  18. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    :O oh.. infinitely many

  19. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    divide integers into 3 groups : {3k}, {3k+1} and {3k+2} pick one integer from each group and form a set : {3a, 3b+1, 3c+2} this forms a complete residue set

  20. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    we almost always are interested in one complete residue set : the set in which the least element is 0

  21. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ah I see. Can I pick two integers in a same set? for example, 3 and 6?

  22. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    that breaks condition i because \(3\equiv 6\)

  23. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I mean something like {1,3,6}

  24. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    check that set for condition i

  25. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ah yes. That would violate condition (i)

  26. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    cool. Now I know how to form such set. ^^

  27. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    think of it like this : Any set of \(n\) incongruent integers form a complete residue system in modulo \(n\)

  28. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    The converse of that statement is also true : If a set forms a complete residue system in modulo \(n\), then it has \(n\) incongruent integers.

  29. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    btw, when you say " incongruent integers", do you mean no two distinct integers are congruent? (like condition (i) ?)

  30. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Exactly!

  31. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I see! thanks so much =]

  32. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    np

  33. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.