5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\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 '15 at 18:50
  • $\begingroup$ @Amad27: $\mathbb{F}$ stands for field, so $\mathbb{F}_{13}$ is the field with $13$ elements. $\endgroup$ – Jack D'Aurizio Jun 20 '15 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$ – YoTengoUnLCD Jun 20 '15 at 18:54
  • $\begingroup$ @JackD'Aurizio, so its basically saying that: $16 \equiv 3 \pmod{13}$? $\endgroup$ – Amad27 Jun 20 '15 at 18:56
  • $\begingroup$ @Amad27: exactly so. $\endgroup$ – Jack D'Aurizio Jun 20 '15 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.