# reducible polynomial modulo every prime

how to show that $x^4+1$ is irreducible in $\mathbb Z[x]$ but it is reducible modulo every prime $p$.

For example i know that $\mod 2$, $x^4+1=(x+1)^4$ . Also $\mod 3$,we have that $0,1,2$ are not solutions of $x^4+1=0$ then if it is reducible then the factors are of degree $2$ this gives that $x^4+1=(x^2+ax+b)(x^2+cx+d)$ and solving this system of equations $\mod 3$ gives that $x^4+1=(x^2+x+2) (x^2+2 x+2) \pmod 3$ but is there a simpler method to factor $x^4+1$ modulo a prime $p$ ?

-

For every odd prime $p$ we have $8\mid p^2-1$. The multiplicative group of the finite field $F=GF(p^2)$ is cyclic of order $p^2-1$. Putting these two bits together tells us that there is a primitive root $u$ of order $8$ in $F$. We must have $u^4=-1$, because $-1$ is the only element of multiplicative order two. Because $F$ is a quadratic extension of $\mathbf{Z}/p\mathbf{Z}$, the minimal polynomial of $u$ is of degree $\le 2$. That minimal polynomial is then a factor of $$x^4+1=(x-u)(x-u^3)(x-u^5)(x-u^7)=(x-u)(x-u^3)(x+u)(x+u^3).$$

====================

Edit: Here's an idea for finding the factorization. I split it into cases according to the residue class of $p$ modulo 8. Assume first that $p\equiv 1\pmod 4$ (or $p$ equivalent to $1$ or $5$ modulo 8). In that case all we need is a square root $i$ of $-1$ modulo $p$. IIRC there is an algorithm for finding two integers $x,y$ such that $p=x^2+y^2$, and then $i=x*y^{-1}$ is the desired square root in the prime field $F_p=GF(p)$. A factorization is then $$x^4+1=(x^2+i)(x^2-i).$$ Observe that if $p\equiv1\pmod8$ then both quadratic factors will split further.

If $p\equiv 3\pmod 8$, then $u$ is not in the prime field, and its conjugate is $u^p=u^3$. Therefore the minimal polynomial is $$m(x)=(x-u)(x-u^p)=(x-u)(x-u^3)=x^2-[u+u^3]x + u^4= x^2-ax-1,$$ where $a$ is some unknown element of the prime field. Because $u^5=-u$ and $u^7=-u^3$, the other factor of $x^4+1$ must be $m(-x)=x^2+ax-1$. We need to find the coefficient $a$. Let's multiply $$(x^2-ax-1)(x^2+ax-1)=(x^2-1)^2-a^2x^2=x^4-(2+a^2)x^2+1.$$ We see that we have found the factorization, if we can find $a=\sqrt{-2}$. It is well known that when $p\equiv 3\pmod 8$, then $-2$ is a quadratic residue modulo $p$ confirming our finding.

In the last case $p\equiv 7\pmod8$ the minimal polynomial of $u$ over $F_p$ is $$m(x)=(x-u)(x-u^p)=(x-u)(x-u^7)=x^2-[u+u^7]x+u^8=x^2-bx+1$$ for some $b\in F_p$. Again the other factor is $m(-x)$, and a similar calculation shows that we need $b=\sqrt{2}$. Again this fits together with the known fact that in this case $2$ is a quadratic residue modulo $p$.

==================

Edit(2): TonyK described the following methods for finding the square roots. They depend on the fact that if $p$ is an odd prime, and $gcd(a,p)=1$, then $a^{(p-1)/2}\equiv\pm1\pmod p$. Here we have the plus sign, if and only if $a$ is a quadratic residue (=QR) modulo $p$.

If $p\equiv 3\pmod8$, then we know that $2$ is not a QR modulo $p$. Therefore $2^{(p-1)/2}\equiv -1\pmod p$. Hence $2^{(p+1)/2}\equiv -2\pmod p$. But here $(p+1)/2$ is an even integer, so writing $z=2^{(p+1)/4}$ we get $z^2\equiv 2^{(p+1)/2}\equiv -2$, and we have found a square root of $-2$.

Similarly, if $p\equiv 7\pmod 8$, we know that $2$ is a quadratic residue modulo $p$. This time $2^{(p+1)/2}\equiv 2$, and the same calculation shows that $z=2^{(p+1)/4}$ is a square root of $2$ in $F_p$.

If $p\equiv 5\pmod 8$, then again $2$ is not a QR modulo $p$, so $2^{(p-1)/2}\equiv -1\pmod p$ and $(p-1)/2$ is even. Thus $z=2^{(p-1)/4}$ is a square root of $-1$. If $p\equiv 1\pmod 8$, then we cannot use $2$ (but could use any non-QR in its place, or the method mentioned earlier).

-
why $[F:\mathbf{Z}/p\mathbf{Z}]=2$? –  palio Oct 30 '11 at 12:51
@palio $F$ has $p^2$ elements, so it is a 2-dimensional space over the prime field. But it may happen that $u\in\mathbf{Z}/p\mathbf{Z}$. This happens, when $p\equiv 1\pmod 8$, because then the prime field already has a primitive root of unity of order 8. I am thinking about finding the factorization... –  Jyrki Lahtonen Oct 30 '11 at 13:01
ok i see what you mean.. thank you –  palio Oct 30 '11 at 13:06
If $p\equiv 3\pmod 4$, then the square root of $2$ or $-2$ (whichever one exists) is simply $2^{(p+1)/4}$. –  TonyK Oct 30 '11 at 14:32
@PraphullaKoushik: So to get the splitting field we want to adjoin the eighth roots of unity to the prime field (unless they are already there). That will never take higher than a quadratic extension, because $8\mid p^2-1$. If you prefer a Galois theoretic point of view it goes like: over the rationals adjoining the eighth roots (powers of $(1+i)/\sqrt2$) gives us all $i$, $\sqrt2$ and $\sqrt{-2}$. Over $\Bbb{F}_p$ there is only one quadratic extension, so it does not matter whether we need to adjoin one or more of $i$, $\sqrt2$ or $\sqrt{-2}$ we get all three for the price of one. –  Jyrki Lahtonen Mar 9 at 15:02

I think you can solve formally the (non-linear) system obtained imposing $x^4+1=(x^2+ax+b)(x^2+cx+d)$ using the fact that $\mathbb Z_p$ is a field. Start from the last equation: $b=d^{-1}$ and so on..

-
in the example i worked out above, writing $b=d^{-1}$ modulo $3$ gives that $b=1,d=2$ or $b=2,d=1$ suppose we choose $b=1$ and $d=2$ then what? –  palio Oct 30 '11 at 13:03
You can do this, and you either need $b^2 + 1 = 0$ to have a solution, or $a^2 + 2 = 0$ or $a^2 - 2 = 0$. So either $-1,-2$ or $2$ are a square in $F_p$, which is always true (even though not always the same is a square), because the product of two non-squares is a square. –  Bogdan Oct 9 '12 at 3:24