Find $n$ such that $x^n \equiv 2 \pmod{13}$ has a solution I am stuck on the following problem:

Consider the congruence $x^n\equiv 2\pmod{13}$. This congruence has a solution for $x$ if

*

*$n=5$

*$n=6$

*$n=7$

*$n=8$

Can someone explain in detail? Thanks in advance.
 A: Hint: $13$ is prime, so we know there is some primitive root $g$ modulo $13$. Thus, there is some $k$ such that $g^k\equiv 2\bmod 13$, and if there is a solution $x$ to the congruence $x^n\equiv 2\bmod 13$, then there is some $\ell$ such that $g^\ell\equiv x\bmod 13$. Thus, $$(g^\ell)^n\equiv g^{\ell n}\equiv g^k\bmod 13.$$
This is true iff $\ell n\equiv k\bmod 12$, by Fermat's little theorem and the definition of primitive root:
$$g^{\ell n}\equiv g^k\bmod 13\iff g^{\ell n -k}\equiv 1\bmod 13\iff (\ell n -k)\text{ is a multiple of 12}$$
A: As $2^3=8,2^4=16\equiv3,2^6=64\equiv-1\pmod{13}$
$2$ is  a primitive root of $13$
Applying Discrete Logarithm wrt $2,$ on $x^n\equiv2\pmod{13}$
$$n\cdot \text{ind}_2x\equiv1\pmod {12}\text{ as } \phi(13)=12$$
Using Linear congruence theorem (Proof), the above equation is solvable for $\text{ind}_2x$ iff $(n,12)|1\implies (n,12)=1$

Using Fermat's Little Theorem, $x^{12}\equiv1\pmod{13}$ if $(x,12)=1$
The prime divisors of $12$ is $2,3$
If $3|n, x^{4n}\equiv1\pmod{13},$ but $x^{4n}\equiv 2^4\not\equiv1\pmod{13}\implies12\not|4n\implies3\not|n\implies (n,3)=1$
Similarly, $2\not|n\implies (n,2)=1$
$\implies (n,6)=1$
A: I have a solution which does not need any advanced concept:
First of all, we know that for no $n$, the $x$ which $ x^n \equiv 2 \pmod{13}$  is equal to $0$. So we can work in the group $\mathbb{Z}_{13}^*$ (the numbers mod $13$ except $0$). It's a group of order $12$, so for every $x$ we have $x^{12} \equiv 1  \pmod{13}$. Now we can see that it's enough to consider the $n$ to be $1, 2, 3, \ldots, 11$, because for example $x^{28}\equiv x^{16} \equiv x^4 \pmod{13}$. Now using a calculator or by writing a simple program, you can find all the $n$'s.
