0
$\begingroup$

How can I solve $X^4\equiv 13 $ $mod$ $17$?

I know that it has solution because $13^\frac{\phi(17}{gcd(4,17)}\equiv 1 $ $mod$ $17$, but I dont know how to calculate the solutions...

Thanks for all ;)

$\endgroup$
  • $\begingroup$ what is $$gcd(4,17)$$? $\endgroup$ – Dr. Sonnhard Graubner Dec 25 '16 at 18:59
  • $\begingroup$ Greatest Common Divisor $\endgroup$ – Alopiso Dec 25 '16 at 19:01
2
$\begingroup$

Write $X^4-13\equiv X^4+4 = (X^2+2X+2)(X^2-2X+2)$.

Now solve $X^2\pm2X+2 \equiv 0 \bmod 17$ by completing the square.
(You'll need to solve $Y^2 \equiv -1 \bmod 17$, which is easy.)

$\endgroup$
  • $\begingroup$ This is ad hoc but it is nice to be able to use the somewhat surprising factorization of $X^4+4$. $\endgroup$ – lhf Dec 25 '16 at 19:11
  • $\begingroup$ And how can you solve $X^2+2X+2\equiv 0$ $mod$ $17$? :( $\endgroup$ – Alopiso Dec 25 '16 at 19:18
  • $\begingroup$ @Alopiso, $X^2\pm2X+2=(X\pm1)^2+1$ $\endgroup$ – lhf Dec 25 '16 at 19:35
  • $\begingroup$ I did it. Thank a lot :))) $\endgroup$ – Alopiso Dec 25 '16 at 19:37
2
$\begingroup$

we can try to find a generator for the ring.

Obviously we try $2$ first, we get $2,4,8,16,15,13,9,2$. So it didn't work, but since $2$ has order $8$, anuy element outside this list is a generator, so we take $3$.

$3,9,10,13,5,15,11,-1,-3,-9,-10,-13,-5,-15,-11,1$

Notice that $13$ turned out to be $3^4$, so the ones that work are $3,3^{1+4},3^{1+8},3^{1+12}$.

So the answers are $3,5,-3,-5$

$\endgroup$

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.