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


2 Answers 2


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

  • $\begingroup$ great answer (+1), for future reference (as I am learning), what does this $\mathbb{F}$ mean? and what does it have to do with factoring? thank you! $\endgroup$
    – Amad27
    Jun 20, 2015 at 18:50
  • $\begingroup$ @Amad27: $\mathbb{F}$ stands for field, so $\mathbb{F}_{13}$ is the field with $13$ elements. $\endgroup$ Jun 20, 2015 at 18:53
  • 1
    $\begingroup$ It's the field of congruence classes modulo 13. Jack uses this fact to express 3 as $16$ and get that nice factoring. $\endgroup$ Jun 20, 2015 at 18:54
  • $\begingroup$ @JackD'Aurizio, so its basically saying that: $16 \equiv 3 \pmod{13}$? $\endgroup$
    – Amad27
    Jun 20, 2015 at 18:56
  • $\begingroup$ @Amad27: exactly so. $\endgroup$ Jun 20, 2015 at 18:57

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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .