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

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- jamiebookeater

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- 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.