Question. Let $a\in \Bbb Z$. Show that if the congruence
$x^8\equiv a\bmod 13$ is solvable, then it has either one or four residue classes modulo 13 as solutions.
Attempt. We distinguish two cases based on $a$.
- If $13$ divides $a$. Then there is one solution, namely $a\equiv 0\bmod 13$.
- If $13$ doesn't divide $a$. Then, by letting $x:=2^i\bmod 13$ and observing $a:=2^j\bmod 13$, we have $$2^{8i}\equiv 2^j\bmod 13\Rightarrow 8i\equiv j\bmod 12.$$ As $\text{gcd}(8,12)=4$, we note that this congruence will have solutions when $4\vert j$. As we are working modulo $12$, there are three such $j$ terms that satisfy such a property, namely $j\equiv 0\bmod 12$, $j\equiv 4\bmod 12$, $j\equiv 8\bmod 12$.
I'm pretty sure that I am mostly right in what I've done here up until the part where I end up getting three such $j$ terms. There's meant to be four as per the question but I can't see where the fourth one comes from.
Anyone that can put me out of my misery and tell me just how much of a plonker I've been then that would be much appreciated.
Thanks in advance!
Best Answer
$2$ is a primitive root mod $13$, i.e. $2^{i} \equiv 1 \mod 13$ if and only if $i$ is divisible by $12$. Thus $(2^i)^8 \equiv 1 \mod 13$ if and only if $i$ is divisible by $3$, and $(2^i)^8 \equiv (2^j)^8 \mod 13$ if and only if $i-j$ is divisible by $3$. For any $a \ne 0$ and any solution $x$ of $x^8 \equiv a \mod 13$, the other solutions are $2^3 x$, $2^6 x$, and $2^9 x$. That makes four.