Prove that $\{0,1,2^1,2^2,\dots,2^9\}$ forms a complete residue modulo $11$ but $\{0,1,2^2,3^2,\dots,10^2\}$ does not.

Question

Prove that $\{0,1,2^1,2^2,\dots,2^9\}$ forms a complete residue modulo $11$ but $\{0,1,2^2,3^2,\dots,10^2\}$ does not.

I think that: $$\gcd(11,2^n)=1$$ But how to proceed?

Answer 1

A complete residue set mod $11$ has $11$ different elements. So in each case we need to show either the values given are all distinct $\bmod 11$ or that some two of them match.

The simple way to demonstrate this is to calculate out each set, which is not really hard for this limited number of values. There is a simple shortcut to showing that the squares do not form a complete set by finding two elements the same, such as $1^2\equiv 10^2 \bmod 11$.

You can also prove that $2^k,k=0..9$, with zero, form a complete residue set without calculating them all. We know from Fermat's little theorem that since $\gcd(2,11)=1,\ \ 2^{10}\equiv 1 \bmod 11$. It's also clear that given $k_o>0$ is the smallest value for which $2^{k_o}\equiv 1 \bmod 11$, all subsequent values of $k>k_o$ will have $2^{k}\equiv 2^{k-k_o} \bmod 11$. and only multiples of $k_o$ will have $2^{sk_o}\equiv 1 \bmod 11$, so we know that $k_o$ divides $10$. Thus if $2^2\not \equiv 1$ and $2^5\not \equiv 1 \bmod 11 $ then we can be sure that $k_o=10$. And indeed $2^2\equiv 4 $ and $2^5\equiv 32\equiv 10 \bmod 11$ so there must be ten distinct residues from $2^k,k=0..9$ and this, along with zero, gives us the complete residue set.

Answer 2

You can just compute the powers of $2 \pmod {11}$ and show they form $\{0,1,2,3,4,5,6,7,8,9,10\}$ The second list has eleven members, so if you find two of them that are equal you again do not have a complete set. Since $10 \equiv -1 \pmod {11}$ and $(-1)^2=1=1^2 \ldots$

Answer 3

We can compute $2^5=32=-1\pmod{11}$, so the multiplicative order of $2$ modulo $11$ is $10$. Hence the classes of $1,2,\dots,2^9$ are all distinct (and nonzero, of course).

On the other hand $10^2\equiv1\pmod{11}$.