Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

@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

Answer 7

For example, in mod 3, below set satisfies condition i
\[\{1,2\}\]

because the integers in this set are incongruent to each other

Answer 8

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

Answer 9

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?

Answer 10

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

Answer 11

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

Answer 12

that will do

Answer 13

Awesome! thank you ;)

Answer 14

np, btw notice that consecutive integers is not a "required" condition, below set also forms a complete residue set modulo 3 :

\[\{1,2,6\}\]

Answer 15

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.

Answer 16

didn't *state*

Answer 17

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

Answer 18

:O oh.. infinitely many

Answer 19

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

Answer 20

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

Answer 21

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

Answer 22

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

Answer 23

I mean something like {1,3,6}

Answer 24

check that set for condition i

Answer 25

ah yes. That would violate condition (i)

Answer 26

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

Answer 27

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

Answer 28

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.

Answer 29

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

Answer 30

Exactly!

Answer 31

I see! thanks so much =]

Answer 32

np