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

-

I proved this by first listing the numbers 0 through 16 and then listing the numbers 0 through 3^15 (it's not necessary to calculate the powers of three).

The goal is to find all the numbers in the first list by calculating the numbers that are congruent to each of the numbers in the second list, mod 17.

In both lists, you already have the numbers 0,1,3, and 9. So you could write that 0 is congruent to 0 mod 17 and so on, of course.

For the next number in your second list, which is 27, you take 27-17=10. So 3^3 is congruent to 10 mod 17. For the next number in your second list (17+10)x3 = 3(17)+30 = 4(17) + 13. So 3^4 is congruent to 13 mod 17. For the next number in your second list 3(4(17)+13) = 12(17) + 39 = 14(17) + 5, so 3^5 is congruent to 5 mod 17.

Repeatedly performing these steps until you reach the final number on your second list (3^15 is congruent to 6 mod 17) you will have proved the required statement by meeting the goal stated here.

-

## protected by Zev ChonolesMay 14 '15 at 3:41

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).