Solve $x^8 \equiv 3 \pmod {13}$ I need to find all solutions to $x^8 \equiv 3 \pmod {13}$.
What I've tried: I know $2$ is a primitive root modulo $13$.
So it is equivalent to solve
$2^{8t} \equiv 2^4 \pmod {13}$
Then I get $t = 2 + 3k$.
I think I'm wrong... and if not, what are the final solutions?? 
 A: In $\mathbb{F}_{13}$,
$$ x^8-3 = x^8-16 = (x^4-4)(x^4+4)=(x^2-2)(x^2+2)(x^2+2x+2)(x^2-2x+2) $$
hence we just have to check which of the numbers $-2,2,-1$ are quadratic residues. Since $13$ is a prime of the form $8k+5$, the only quadratic residue among the previous ones is $-1$, so $x^8-3$ splits as:
$$ x^8-3 = (x-4)(x+4)(x-6)(x+6)(x^2-2)(x^2+2) $$
and the solutions of $x^8\equiv 3\pmod{13}$ are given by $x\in\{\pm 4,\pm 6\}\pmod{13}$.
A: No, your answer is correct, $t = 2,5,8,11$ give respectively $x = 4,6,9,7$.

For the sake of Google, I will write out the method OP probably used, which is different from the one used in the other answer.
Knowing that $2$ is a primitive root modulo $13$ and that $3 \equiv 2^4 \pmod{13}$, we let $x = 2^t$ and we wish to find all values of $t$ such that
$$\left(2^t\right)^8 \equiv 2^{8t} \equiv 2^4 \pmod{13}.$$
We use the fact that if $a$ is a primitive root modulo $p$, then $a^x \equiv a^y \pmod p$ if and only if $x \equiv y \pmod{(p-1)}$, so we wish to solve
$$8t \equiv 4 \pmod{12}.$$
The method to solve congruences of the form $ax \equiv b \pmod n$ is well-known (see for example these notes) and we find that the solutions are $t \equiv 2 \pmod 3$, which yields $t = 2,5,8,11$. In turn, those values yield $x = 4,6,9,7$ (which matches the other answer).
