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

- 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

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

- ganeshie8

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

- 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

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

- ganeshie8

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

- 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

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

- ganeshie8

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

- 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

\(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

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

that will do

- anonymous

Awesome! thank you ;)

- 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

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

didn't *state*

- ganeshie8

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

- anonymous

:O oh.. infinitely many

- 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

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

- anonymous

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

- ganeshie8

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

- anonymous

I mean something like {1,3,6}

- ganeshie8

check that set for condition i

- anonymous

ah yes. That would violate condition (i)

- anonymous

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

- ganeshie8

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

- 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

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

- ganeshie8

Exactly!

- anonymous

I see! thanks so much =]

- ganeshie8

np

Looking for something else?

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