Solve the congruence relation $x^n\equiv 2\pmod {13}$.

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

(A) $n=5$.

(B) $n=6$.

(C) $n=7$.

(D) $n=8$.

I apply Chinese remainder theorem to solve it but I am fail. Can anyone help me please ?

Update :(18th Nov)

In the given answer I am unable to understand the step $2^A\equiv 1 \pmod{13}$ implies $12$ divides $A$. It's justification in comment is computational. I want an analytical answer.

Result: Let $p$ be a prime and $(a,p)=1$. Then the congruence $x^k\equiv a(\text{mod} ~p)$ has a solution iff $a^{(p-1)/d}\equiv 1(\text{mod}~p)$ where $d=(k,p-1)$

In your question $p=13$, $d=1,2,3,4,6$ Check for which $d$ the congruence $$2^{12/d}\equiv 1(\text{mod}~ 13)$$ has a solution.

You'll get $d=1$ so $(k,12)=1$ implies $k=5,7,11,...$

You can't do much better than the computional approach in the comment, but here is an approach that only requires two computations.

First, a lemma:

Lemma. If $2^{x} \equiv 1 \mod n$ and $2^{y} \equiv 1 \mod n$, then $2^{\gcd(x,y)} \equiv 1 \mod n$.

Proof. By Bezout's theorem, there exist $a,b$ such that $ax+by=\gcd(x,y)$. We clearly have $2^{ax} \equiv 1 \mod n$ and $2^{by} \equiv 1 \mod n$. Therefore $2^{ax}\cdot2^{by} = 2^{\gcd(x,y)} \equiv 1 \mod n$.

Note: one of $a,b$ is negative, but then we just take multiplicative inverse of it. But the multiplicative inverse of 1 is 1, so that doesn't give a problem.

We know by Fermat's Little Theorem that $2^{12} \equiv 1 \mod 13$. Now let $p$ be the smallest $n$ such that $2^{n} \equiv 1 \mod 13$. Then $p\mid12$. Otherwise, $\gcd(p,12)<p$ and by the lemma $p$ wasn't the smallest such $n$.

Now we calculate $2^{6}=64 \equiv -1 \not \equiv 1 \mod 13$. Therefore divisiors of 6 are not possible. Since $2^{4}=16 \equiv 3 \not \equiv 1 \mod 13$, we have checked all divisiors of 12. Therefore 12 is really the smallest possible.

The order of $a$ mod $p$ (where $a$ and $p$ are coprime) is the least positive integer $m$ such that $a^m \equiv 1 \mod p$. Every $n$ such that $a^n \equiv 1 \mod p$ is then a multiple of $m$. This is because for any integer $n$ we can write $n = q m + r$ where $q$ is an integer and $0 \le r < m$, and if both $a^n$ and $a^m \equiv 1 \mod p$, $a^r \equiv a^n (a^m)^{-q} \equiv 1 \mod p$, but by assumption $m$ is the least positive integer such that $a^m \equiv 1 \mod p$ so we must have $r = 0$.

In your case, by Fermat's theorem $2^{12} \equiv 1 \mod 13$, so the order of $2$ mod $13$ must be a divisor of $12$. But $2^6 = 64 \equiv 12 \mod 13$,so the order can't be $6$ or one of its divisors, and $2^4 = 16 \equiv 3 \mod 13$, so the order can't be $4$. The only other possibility is that the order is $12$. Thus every $A$ such that $2^A \equiv 1 \mod 13$ is a multiple of $12$.