## 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?

1. anonymous

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

2. ganeshie8

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

3. UsukiDoll

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

4. ganeshie8

condition i says, those $$n$$ integers must be incongruent

5. ganeshie8

Any set of $$n$$ consecutive integers form a complete residue set in modulus $$n$$

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

7. ganeshie8

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

8. ganeshie8

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

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

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

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

12. ganeshie8

that will do

13. anonymous

Awesome! thank you ;)

14. 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\}$

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

16. anonymous

didn't *state*

17. ganeshie8

18. anonymous

:O oh.. infinitely many

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

20. ganeshie8

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

21. anonymous

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

22. ganeshie8

that breaks condition i because $$3\equiv 6$$

23. anonymous

I mean something like {1,3,6}

24. ganeshie8

check that set for condition i

25. anonymous

ah yes. That would violate condition (i)

26. anonymous

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

27. ganeshie8

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

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

29. anonymous

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

30. ganeshie8

Exactly!

31. anonymous

I see! thanks so much =]

32. ganeshie8

np