A community for students.
Here's the question you clicked on:
 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?
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

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I think condition (i) is easy to check. Having difficult time with condition (ii)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Condition ii just says, you need \(n\) integers to form a complete residue set in modulus \(n\)

UsukiDoll
 one year ago
Best ResponseYou've already chosen the best response.0so if we have modulo 6 would the complete residue be [0,1,2,3,4,5] ?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1condition i says, those \(n\) integers must be incongruent

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Any set of \(n\) consecutive integers form a complete residue set in modulus \(n\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.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

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1For example, in mod 3, below set satisfies condition i \[\{1,2\}\] because the integers in this set are incongruent to each other

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1the same set fails condition ii because there is no element in the set that is congruent to the integer \(0\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0so 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?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.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.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0so 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

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Awesome! thank you ;)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1np, btw notice that consecutive integers is not a "required" condition, below set also forms a complete residue set modulo 3 : \[\{1,2,6\}\]

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Yeah. 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.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1there are infinitely many, so there is not much use in thinking too much about this

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0:O oh.. infinitely many

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1divide 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

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1we almost always are interested in one complete residue set : the set in which the least element is 0

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0ah I see. Can I pick two integers in a same set? for example, 3 and 6?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1that breaks condition i because \(3\equiv 6\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I mean something like {1,3,6}

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1check that set for condition i

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0ah yes. That would violate condition (i)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0cool. Now I know how to form such set. ^^

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1think of it like this : Any set of \(n\) incongruent integers form a complete residue system in modulo \(n\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1The converse of that statement is also true : If a set forms a complete residue system in modulo \(n\), then it has \(n\) incongruent integers.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0btw, when you say " incongruent integers", do you mean no two distinct integers are congruent? (like condition (i) ?)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I see! thanks so much =]
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.