# How to prove a set of numbers is a complete system of residues modulo of a number?

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

Example: The division algorithm shows that the set of $0, 1, 2, ..., m - 1$ is a complete system of residues modulo m.

What I did not understand is "congruent modulo m to exactly one integer of the set". Could anyone give me a counter example to this?

And here is the problem:

Prove that the set $0, 1, 3, 3^2, 3^3, ...., 3^{15}$ is a complete system of residues modulo $17$.

I really have no idea how to start and what to prove :(. To be a complete system of residues modulo, what property does this set have to have? A hint would be greatly appreciated.

Thanks,

-

HINT: $\left(\frac{3}{17}\right) = -1$. Essentially you want to prove all the remainders are distinct $\bmod 17$.

-
@Chan: You should essentially prove that all the remainders are distinct $\bmod 17$ –  user17762 Feb 28 '11 at 6:24
Ambikasaran: Many thanks, I got the idea now. –  Chan Feb 28 '11 at 6:25
Ambikasaran: Could you explain the notation that you used in your hint. How could 17 divides 3 = -1? –  Chan Feb 28 '11 at 6:32
@Chan: en.wikipedia.org/wiki/… –  user17762 Feb 28 '11 at 6:33
Ambikasaran: Thanks ;) –  Chan Feb 28 '11 at 6:33
By the pigeonhole principle, $\rm\:S\:$ is a CSR $\rm\ (mod\ m)\$ if $\rm\:S\:$ has $\rm\:m\:$ elements that are distinct $\rm (mod\ m)\:.\:$ Hence, for your problem, you need to show that $\rm\ \ i\ne j\ \Rightarrow\ 3^{\:i}\: \not\equiv 3^{\:j}\ (mod\ 17)\:,\$ for $\rm\ 0\le i,\:j\le 15\:,\$ i.e. you need to show mod $\:17\:,\:$ that $\:3\:$ has order $\rm 16\:$. If its order $\rm\:n\:$ is $< 16\:$ then $\rm\:n\: |\: 16\$ so $\rm\: n\: |\: 8\:,\:$ but $\rm\ 3^4 \equiv -4\ \Rightarrow\ 3^8\equiv -1\:.\:$ So, indeed, $3\:$ has order $16\:$. Combining this with $\rm\ 3^{\:i}\:\not\equiv 0\ (mod\ 17)\$ (why?) completes the proof.