Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$ ?

share|improve this question
add comment

2 Answers

up vote 14 down vote accepted

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

share|improve this answer
    
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
1  
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
1  
@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
show 10 more comments

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

share|improve this answer
    
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
2  
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. –  redfiloux Oct 9 '12 at 3:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.