Dtyjlui

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 $x^4+1=(x+1)^4bmod 2$. Also $bmod 3$ we have that $0,1,2$ are not solutions of $x^4+1=0$ then if it is reducible 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 $bmod 3$ gives that $x^4+1=(x^2+x+2) (x^2+2x+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 $8mid 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}/pmathbf{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 $pequiv 1pmod 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 $pequiv1pmod8$ then both quadratic factors will split further.

If $pequiv 3pmod 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 $pequiv 3pmod 8$, then $-2$ is a quadratic residue modulo $p$ confirming our finding.

In the last case $pequiv 7pmod8$ 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 $bin 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}equivpm1pmod p$. Here we have the plus sign, if and only if $a$ is a quadratic residue (=QR) modulo $p$.

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

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

If $-1$ is a square in $Bbb F_p$ (which includes the case $p=2$), say $a^2=-1$, then we have $$X^4+1=X^4-a^2=(X^2+a)(X^2-a).$$
If $p$ is odd and $2$ is a square in $Bbb F_p$, say $2=b^2$, then we have
$$X^4+1=(X^2+1)^2-(bX)^2=(X^2+bX+1)(X^2-bX+1) $$
If $p$ is odd and neither $-1$ nor $2$ is a square, then their product $-2$ is a square, say $-2=c^2$. (Without using anything even remotely as deep as quadratic reciprocity, this follows immediately from the fact that $Bbb F_p^times$ is a cyclic group of even order). Then we have
$$ X^4+1=(X^2-1)^2-(cX)^2=(X^2-cX-1)(X^2+cX-1)$$

When $p=2$ then just note $x^4+1=(x+1)^4$.

Now if $p$ is odd then $8mid p^2-1 implies x^4+1mid x^{p^2-1}-1mid x^{p^2}-x$. Let $a$ be a root of $x^4+1$ in some extension of $mathbb F_p$. So, $[mathbb F_p(a):mathbb F_p]=4$ if we let $x^4+1$ is irreducible over $mathbb F_p$. But from $x^4+1mid x^{p^2}-x$ we can say $ainmathbb F_{p^2} implies [mathbb F_p(a):mathbb F_p]leq 2$, a contradiction.