Solve $x^8 \equiv 3 \pmod {13}$

Question

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??

Answer 1

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}$.

Answer 2

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).