Check if set: $\{0, 1, 2, 2^2, ..., 2^{15} \pmod {17}\}$ forms a complete set of residues.

Question

Check if the set of numbers : $\{0, 1, 2, 2^2, ..., 2^{15} \pmod {17}\}$ form a complete set of residues.

My simple question: is there any short route to find the answer, rather than checking it individually. I mean that if there is any property that can be used to achieve the same.

Answer 1

The trick is to realize that for $0, 1=2^0; 2^1, ... 2^{15}$ to be complete residue system, the $2^k$ must be distinct. And if they aren't distinct then there must be $2^a \equiv 2^b$ for some $a \ne b$. (Or some $2^k \equiv 0 \mod 17$ but that means $17|2^k$ and that $2^{m;m\ge k} \equiv 0 \mod 17$ and that's obviously not the case.

If $a< b$ and $2^a \equiv 2^b \mod 17$ then $2^a(2^{a-b}-1) \equiv 0 \mod 17$ so $17|2^a(2^{a-b}-1)$ so $2^{k=a-b} \equiv 1 \mod 17$ for some $k$.

A little intuition should make us think that $b|16$. Why is that intuitive? Well, because if $2^0 \equiv 1\mod 17$ then $2^k\equiv 2^{2k} \equiv 2^{3k} \equiv 1 \mod 17$ will go in cycles. And as there are only $17$ residue classes and $0$ is not an equivalency class of a power of $2$ there are $16$ non-zero equivalency classes. That's not hard and fast but it should be an intuitive thought.

So try to test $2^8, 2^4, 2^2, 2^1$. As $2^4 = 16\equiv -1$ we have $2^8 \equiv 1 \mod 17$ and so the $2^0, ...., 2^{15}$ are not distinct.

It's not a complete residue system.

Answer 2

Note that $2^4=16\equiv-1\pmod{17}$ and that therefore $2^8\equiv1\pmod{17}$. So, the answer is negative.

Answer 3

You just need to check whether $2^8\equiv 1 \bmod 17$. If it is, the answer is no - if it is not, the answer is yes.

Here, $2^8\equiv 1 \bmod 17$, so the answer is no.

Why do you only need to check that one power? Since $\phi(17)$${} = 16=2^4$, the multiplicative order of every residue must divide $16$ with only primitive roots (whose powers form the desired complete set of non-zero residues) having order $16$. Because $2$ is the only prime factor of $16$, the residues $a$ that are not primitive roots must therefore have $a^8\equiv 1 \bmod 17$.

Answer 4

Alternative approach: $p=17$ is a prime $\equiv 1\pmod{8}$, hence $\left(\frac{2}{p}\right)=1$ and $2$ cannot be a generator of $\mathbb{Z}/(17\mathbb{Z})^*$, since it is a quadratic residue. It follows that the answer is negative.

Vice-versa, if $2$ is replaced by any non-quadratic residue $\!\!\pmod{17}$, the answer is positive.