Show that $0, 1, 2, 2^2,...,2^9$ form a complete residue system 11 module.

Question

I have question about module congruence

I have no idea or where to begin to resolve this question.

Can anybody help me? Thanks.

You could try calculating the remainders of all those numbers when divided by $11$ to show they’re distinct — J. W. Tanner, Nov 19 '20 at 22:14
So if the rests are equal when divided by 11 they would not be a complete system of rest. Is that correct? — Thais, Nov 19 '20 at 22:17
Presumably "rest" should read "residue" in the question and your comments? — Rob Arthan, Nov 19 '20 at 22:25

lhf · Answer 1 · 2020-11-20T10:23:53.197

0

Hint: $2^2 \not \equiv 1, 2^5 \not \equiv 1 \bmod 11 \implies 1, 2, 2^2,\dots,2^9$ are all different mod $11$.

edited Nov 20 '20 at 10:23

answered Nov 19 '20 at 22:22

lhf

I believe that isn't sufficient, unless you also throw in $2^2 \not \equiv 1$. E.g. $10^5 \equiv -1 \pmod{11}$, but the result doesn't follow. – Calvin Lin Nov 19 '20 at 22:32
@CalvinLin. you're right. Fixed, thanks. – lhf Nov 20 '20 at 10:24

score 0 · Answer 2 · answered Nov 19 '20 at 22:48

Repeated multiplication by $2$ mod $11$ shows that the remainders of those powers of $2$

when divided by $11$ are distinct: $1, 2,4,8,5,10,9,7,3,6$. (To get the next number in this series,

simply multiply by $2$ and subtract $11$ if the result is more than $11$.)

Powers of $2$ cycle through all non-zero residues mod $11$; i.e., $2$ is a primitive root modulo $11$.

In contrast, $3$ is not a primitive root modulo $11$; the powers of $3$ mod $11$ are $1,3,9,5,4$,

and then that cycle repeats. (To get the next number in that series, multiply by $3$

and then subtract $11$ or $22$ if needed to get a number less than $11$.)

2 Answers2