- #36
Isaak DeMaio
- 74
- 0
Robert1986 said:Usually, a system of residues modulo n (n an integer) is defined this way:
A complete system of residues modulo m is a set of integers such that every integer is congruent modulo m to exactly one integer of the set.
OK, so cutting through the rather convoluted English, what does this mean? Let's look at your example of a system of residues modulo 5.
Now, first we note that two integers m and n are congruent modulo 5 if and only if the remainder of m after dividing m by 5 is equal to the remainder of n after dividing n by 5. So 1/5 = 0 plus a remainder of 1 and 6/5 = 1 plus a remainder of 1. So we say that 1 is congruent to 6 modulo 5 and write it this way: 1 = 6 (mod 5). Also, we see that 16=11=6=1 (mod 5).
Now, for any integer n, how many different congruences mod n are there? It is easy to see that there are n different ones: {0,1,...,n-1}. In fact, {0,1,...,n-1} is a complete system of residues mod n; it even has a special name: least nonnegative residues mod n.
So, to find a complete system of residues mod n, all you need to do is find a set of n integers such that each integer is congruent to a unique number mod n. For 5, the set {0,1,2,3,4} is a system of residues mod 5 as is {0,11,22,103,99} but {10,11,12,27,39} are not since 12=27(mod 5).
So, to put it another way, a complete system of residues mod 5 is a set of integers such that each integer in the set has a different remainder upon division by 5.
So would it be like 5=0(mod5), 1=1(mod5), 12=2(mod5), 28=3 (mod5)
How exactly do you show the complete system?