<s>[INST] Irreducible polynomial which is reducible 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 $x^4+1=(x+1)^4\bmod 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$?
 [/INST] 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).
</s>