For which positive exponents $e$ is $2^e \equiv 1\pmod{17}$?

Question

For which positive exponents $e$ is $2^e \equiv 1\pmod{17}$?

We are currently covering a section on primitive roots, indices and power residues. I am really lost with this one, any hint/help is greatly appreciated.

Answer 1

Let's make a table... \begin{array}{c|c|c|c|c|c|c|c|c} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \cdots\\ \hline 2^n\mod 17 & 2 & 4 & 8 & 16\equiv-1 & -2 & -4 & -8 & -16\equiv1 &\cdots \end{array} Thus $e=8k$, where $k$ is a positive integer.

Answer 2

First of all, if

$$2^a \equiv 2^b \equiv 1 \pmod{17}$$

then using Bezout's identity:

$$2^{\gcd{(a,b)}}=2^{sa + tb}\equiv \left(2^a\right)^s\left(2^b\right)^t\equiv1\pmod{17}$$

Hence, if we find the smallest $n>0$ that satisfies $2^n\equiv1\pmod{17}$, then the solutions are exactly the multiples of $n$. $2^{16}=2^{\phi(17)}\equiv1\pmod{17}$ by Euler's theorem, and hence $n$ must be a divisor of $16$. Since $2^4=16\equiv-1\pmod{17}$, we get $$2^8\equiv(-1)^2\equiv1\pmod{17}$$

and hence $e=8k$ are the solutions.