# Solve this polynomial congruence

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

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

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

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

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$