anonymous
  • anonymous
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?
Mathematics
schrodinger
  • schrodinger
See more answers at brainly.com
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this
and thousands of other questions

anonymous
  • anonymous
I think condition (i) is easy to check. Having difficult time with condition (ii)
ganeshie8
  • ganeshie8
Condition ii just says, you need \(n\) integers to form a complete residue set in modulus \(n\)
UsukiDoll
  • UsukiDoll
so if we have modulo 6 would the complete residue be [0,1,2,3,4,5] ?

Looking for something else?

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

More answers

ganeshie8
  • ganeshie8
condition i says, those \(n\) integers must be incongruent
ganeshie8
  • ganeshie8
Any set of \(n\) consecutive integers form a complete residue set in modulus \(n\)
anonymous
  • anonymous
@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
  • ganeshie8
For example, in mod 3, below set satisfies condition i \[\{1,2\}\] because the integers in this set are incongruent to each other
ganeshie8
  • ganeshie8
the same set fails condition ii because there is no element in the set that is congruent to the integer \(0\)
anonymous
  • anonymous
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?
ganeshie8
  • ganeshie8
\(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
  • anonymous
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
ganeshie8
  • ganeshie8
that will do
anonymous
  • anonymous
Awesome! thank you ;)
ganeshie8
  • ganeshie8
np, btw notice that consecutive integers is not a "required" condition, below set also forms a complete residue set modulo 3 : \[\{1,2,6\}\]
anonymous
  • anonymous
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.
anonymous
  • anonymous
didn't *state*
ganeshie8
  • ganeshie8
there are infinitely many, so there is not much use in thinking too much about this
anonymous
  • anonymous
:O oh.. infinitely many
ganeshie8
  • ganeshie8
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
ganeshie8
  • ganeshie8
we almost always are interested in one complete residue set : the set in which the least element is 0
anonymous
  • anonymous
ah I see. Can I pick two integers in a same set? for example, 3 and 6?
ganeshie8
  • ganeshie8
that breaks condition i because \(3\equiv 6\)
anonymous
  • anonymous
I mean something like {1,3,6}
ganeshie8
  • ganeshie8
check that set for condition i
anonymous
  • anonymous
ah yes. That would violate condition (i)
anonymous
  • anonymous
cool. Now I know how to form such set. ^^
ganeshie8
  • ganeshie8
think of it like this : Any set of \(n\) incongruent integers form a complete residue system in modulo \(n\)
ganeshie8
  • ganeshie8
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.
anonymous
  • anonymous
btw, when you say " incongruent integers", do you mean no two distinct integers are congruent? (like condition (i) ?)
ganeshie8
  • ganeshie8
Exactly!
anonymous
  • anonymous
I see! thanks so much =]
ganeshie8
  • ganeshie8
np

Looking for something else?

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