$x^n =2($mod $13)$ Consider the congruence $x^n =2($mod $13)$. Then for which n does it have a solution?


*

*n= 5

*n=6

*n=7

*n=8


Can we take any help from this fact  $x^{12 }=1 ($ mod $13),\forall x $?
Please give some hints.
 A: If $x$ is of the form $2^m$, then we have $$2^{mn}=2\mod 13\\ \Rightarrow 2^{mn-1}=1\mod 13$$ So, we need to have $12|mn-1$i.e. we need to solve the linear Diphontine equation $mn-12k=1$ clearly then, $n$ cannot be $6$ or $8$. For $n=5,$ a solution to $m,k$ is $m=5,k=2$. For $n=7$,  a solution is $m=7, k=4$. So, for $n=5,7$ the congruence equation has solutions for $x$ and such solutions are $2^5,2^7$ respectively.
A: As $\displaystyle2^2\equiv4;2^3\equiv8;2^4=16\equiv3;2^6=64\equiv-1\pmod{13}$
$\displaystyle2$ is itself a primitive root $\pmod{13}$
Taking discrete logarithm wrt $2\pmod{13}$ on $\displaystyle x^n\equiv2\pmod{13}$
$\displaystyle n\cdot\text{ind}_2x\equiv1\pmod{12}\implies (n,12)=1$
Using Bézout's Lemma, we can always find integer $\text{ind}_2x$ for $(n,12)=1$
A: From the fact you were given, you know that $$(x^6)^2=1\pmod{13}$$
So, for example, $x^6\neq 2\pmod{13}$ since $2^2\neq 1\pmod{13}$.
Because $13$ is prime, $x^2-1=0\pmod{13}$ has at most two solutions, the degree of the polynomial.  In fact it has exactly two: $1,-1$, found by inspection.
If $x^6=1$, then $x^7=2$ is equivalent to $x^1=2$.  $x^8=2$ is equivalent to $x^2=2$.  For $x^5=2$, we multiply both sides by $x$ to get $1=2x$.  Now we have three simpler modular equations to solve.
If $x^6=-1$, the situation is similar.
A: As you know from the theorem, $x^{p-1} = 1 (mod p)$ so if you want to get number 2 you can use $x^{p-1}+1 = 2 (mod p)$
  It's one kind of solution. Now you can extend $x^{p-1}+1$ type numbers. 
A: Here's a result : 

If $o(a)=p-1$ in the group $U(p)$ then the system $$x^n\equiv a (\text{mod } p)$$ has a solution if and only if $\text{gcd}(n,p-1)=1$ 

Verify that $o(2)=12$ in $U(13)$. Let's prove the result. 
Suppose $x$ is a solution. Then $o(x^n)=p-1$. Which means $o(x^n)=o(x)=p-1$ (every element must have order $\leq p-1$). So $\text{gcd}(n, p-1)=1$.
Conversely, let $\text{gcd}(n, p-1)=1$. Then $o(a^n)=o(a)=p-1$. So $a=a^{nk}$ for some $k$. Take $x=a^k$. 
