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

2 Answers 2

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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