Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
@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.

share|improve this answer

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.

share|improve this answer

protected by Zev Chonoles May 14 at 3:41

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.