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

1. n= 5
2. n=6
3. n=7
4. n=8

Can we take any help from this fact $x^{12 }=1 ($ mod $13),\forall x $?

Please give some hints.

Answer: 
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](https://proofwiki.org/wiki/B%C3%A9zout%27s_Lemma), we can always find integer $\text{ind}\_2x$ for $(n,12)=1$
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$.