Find all incongruent solutions of $x^8\equiv3\pmod{13}$.

Question

Find all incongruent solutions of $x^8\equiv3\pmod{13}$.

I know that $2$ is a primitive root of $13$ and that $2^4\equiv3\pmod{13}$, so we want to solve $x^8\equiv2^4\pmod{13}$.

Now, $\gcd(8,\phi(13))=\gcd(8,12)=4$ divides the exponent of $2$, which is $4$, so $x^8\equiv3\pmod{13}$ has exactly $4$ incongruent solutions modulo $13$.

I was able to find on my calculator (using brute force) that these solutions are $4,6,7,$ and $9$ (i.e. $\pm4,\pm6$), but how would I go about finding them without using a calculator?

Answer 1

$$x^8-3\equiv x^8-16\equiv \left(x^2-2\right)\left(x^2+2\right)\left(x^4+4\right)\pmod{13}$$

$x^2\equiv 2\pmod{13}$ and $x^2\equiv -2\pmod{13}$ are both unsolvable (by Quadratic Reciprocity), because $13\equiv 5\pmod{8}$.

$$x^4+4\equiv x^4-9\equiv \left(x^2+3\right)\left(x^2-3\right)\pmod{13}$$

$$x^2+3\equiv x^2-36\equiv (x+6)(x-6)\pmod{13}$$

$$x^2-3\equiv x^2-16\equiv (x+4)(x-4)\pmod{13}$$

Answer 2

We can just list all the values $x^8$ takes for $x\in\Bbb{Z}/13\Bbb{Z}$: $$\begin{array}{c|cccccccccccccc} x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10& 11& 12\\ \hline x^8 & 0 & 1 & 9 & 9 & 3 & 1 & 3 & 3 & 1 & 3 & 9 & 9 & 1 \\ \end{array}$$ If you use the fact that $(-x)^8=x^8$ and $(xy)^8=x^8y^8$, the only 'big' computations you need are $$2^8\equiv256\equiv9\pmod{13}\qquad\text{ and }\qquad3^8\equiv6561\equiv9\pmod{13},$$ and even these can be broken down. Anyway, the solutions are clearly $4$, $6$, $7$ and $9$.

Answer 3

We have that $Z/13Z$ it's a field. In $Z/13Z$ the inverse of $3$ is $9$ so if you multiply by $9$ will have $9x^8$ is congruent by 1 modulo 9. In Z/13Z, $x^{12}$ is congruent by 1 modulo 13. So $9x^8-x^{12}$ is congruent by 0 modulo 13. So $x^8(x^4-9)$ is congruent with 0 modulo 13. Result that x is congruent by 0 mod 13(is not solution) or $x^4-9=(x^2-3)(x^2+3)$ is congruent by 0 modulo 13 and now it is more clear.

Answer 4

One can easily see that $2$ is a primitive root of $13$.

Hence, we can write any number less than $13$ as some power of $2$.

$x^8\equiv3\equiv2^4\pmod{13}$.

Any solution will also be of the form $x=2^m$ for some $1\leq m\leq12$.

So, we have

$(2^m)^8=2^{8m}\equiv2^4\pmod{13}$.

Now, these powers will be congruent modulo $\phi(13)$, giving

$8m\equiv4\pmod{12}$

$8m\equiv16\pmod{12}$

$m\equiv2\pmod3$

$m\equiv2,5,8,$ or $11\pmod{12}$.

So, we have $x\equiv2^2,2^5,2^8,$ or $2^{11}\pmod{13}\implies x\equiv4,6,9,$ or $7\pmod{13}$.