Proof of Irreducibility in Z_p[x]Date: 11/03/2006 at 23:42:39 From: Aline Subject: Irreducible in Z_p[x] Let f be a primitive polynomial in Z_[x]. For any prime p, let f_p be the image of f under the map Z[x]--->Z_p[x]. Then f is irreducible iff f_p is irreducible in Z_p[x] for some prime p. I'm already done with the part f_p irreducible implies f is irreducible in Z[x]. Now I need to show the other direction. It should have to due with the fact that the prime numbers are infinite. The difficulty is to show that if f is irreducible in Z[x] then there exists p prime such that f_p is irreducible in Z_p[x]. Please help me to finish this proof.... Date: 11/04/2006 at 04:56:08 From: Doctor Jacques Subject: Re: Irreducible in Z_p[x] Hi Aline, You would have a hard time finishing the proof--the assertion is false, as surprising as it may seem. The part you proved is true (any factorization over Z gives a factorization over Z_p), but the converse is false. A counter-example is given by the polynomial f(x) = x^4 + 1. It is easy to see that this polynomial is irreducible over Z (or Q): it factors over R as: f(x) = (x^2 + sqrt(2)*x + 1)(x^2 - sqrt(2)*x + 1) [1] which is a complete factorization. Since R[x] has unique factorization, and the coefficients above are not all rational, there cannot be a factorization over Q. We claim that, if p is any prime, f_p(x) is always reducible. This is obvious for p = 2 : f(x) = (x+1)^4 (mod 2). If p is odd, I know two proofs of this: one uses concepts from number theory (in particular, quadratic residues), and the second one uses Galois theory. I don't know how familiar you are with either of these areas; anyway, I will give you the outline of the first proof (the second one is more elegant, but it is less likely that you know the required concepts). As said before, we may assume that p is an odd prime. We use the following facts from the theory of quadratic residues: 1) If p = 1 (mod 4), the equation x^2 = -1 (mod p) has a solution a (-a is the other solution) 2) If p = 3 (mod 4), for any k not divisible by p, exactly one of the equations x^2 = k and x^2 = -k has a solution modulo p. In the first case, our polynomial factors as: x^4 + 1 = (x^2 + a)(x^2 - a) (mod p) [2] where a^2 = -1 (mod p). In the second case, we take k = 2. As said before, either there is a 'b' such that b^2 = 2 (mod p), or there is a 'c' such that c^2 = -2 (mod p) (Incidentally, the first case happens when p = 7 (mod 8), and the second case happens when p = 3 (mod 8)). In the first case, we have the factorization: x^4 + 1 = (x^2 + b*x +1)(x^2 - b*x + 1) (mod p) [3] where b^2 = 2 (mod p) and, in the second case, we have: x^4 + 1 = (x^2 + c*x - 1)(x^2 - c*x - 1) (mod p) [4] where c^2 = -2 (mod p). As examples of each of these cases, we have: x^4 + 1 = (x^2 + 2)(x^2 - 2) (mod 5) = (x^2 + x - 1)(x^2 - x - 1) (mod 3) = (x^2 + 3x + 1)(x^2 - 3x + 1) (mod 7) By the way, you should notice the similarity between [1] and [3]: in some sense, b is the square root of 2 (mod p). There is also a similarity between [4] and the complex factorization: x^4 + 1 = (x^2 + i*sqrt(2)*x - 1)(x^2 - i*sqrt(2) - 1) [5] (in this case, the factors are not irreducible over C). Both [1] and [5] arise from the complete factorization over C : x^4 + 1 = (x + u)(x - u)(x + v)(x - v) (where u = (1 + i)*sqrt(2)/2 and v is the complex conjugate of u), by grouping the factors in two different ways. Please feel free to write back if you require further assistance. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ Date: 11/04/2006 at 17:30:06 From: Aline Subject: Irreducible in Z_p[x] Thank you for the whole explanation, and for your time, too. One more thing I need to ask: can you please give me a good reference or website where I can learn more about the theory of quadratic residues? Thanks again... Date: 11/05/2006 at 03:13:30 From: Doctor Jacques Subject: Re: Irreducible in Z_p[x] Hi Aline, I would strongly recommend the excellent book "Elementary Number Theory" by David Burton. This book presents many useful concepts in number theory (including quadratic residues) without assuming much prior knowledge besides the high school level. The drawback is that it is rather expensive... I'm sure that you will also find lots of articles on the subject on the Internet by searching for that phrase (Google returned more that 80,000 hits). For example, you could start at: Quadratic Residue http://en.wikipedia.org/wiki/Quadratic_residue In particular, follow the link "Gauss' lemma" on that page. You can also find some references in our library. Start at our search page: http://mathforum.org/library/drmath/mathgrepform.html and type "quadratic residue" (without quotes) and check the "Exact phrase" option. Good luck! - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ Date: 10/27/2009 at 00:37:08 From: Sun Subject: Irreducibility in the finite field (with Galois thoery) I have some questions about this answer. Near the middle, you wrote "We claim that, if p is any prime, f_p(x) is always reducible. This is obvious for p = 2 : f(x) = (x + 1)^4 (mod 2). If p is odd, I know two proofs of this: one uses concepts from number theory and the second one uses 'Galois theory.'" So, my question is.... 1) How can I prove x^4 + 1 is reducible in the finite fields using the Galois theorem? 2) Please explain a general relation between them if there is any. Thanks ^^ Date: 10/27/2009 at 04:34:34 From: Doctor Jacques Subject: Re: Irreducibility in the finite field (with Galois thoery) Hi Sun, As stated in the article, this is obvious for p = 2; we may assume that p is odd. It is easy to verify that, if p is any odd prime (or, for that matter, any odd integer), then p^2 = 1 (mod 8): simply check all 4 possible values for p (mod 8). The multiplicative group of the field GF(p^2) has order p^2 - 1, and, like any finite multiplicative group in a field, that group is cyclic. As stated above, (p^2 - 1) is a multiple of 8. This means that the equation x^8 = 1 has all its roots in GF(q). However, over any field, we have the factorisation: x^8 - 1 = (x - 1)(x + 1)(x^4 + 1) This shows that the roots of x^4 + 1 are among the roots of x^8 - 1, i.e., they are 8th roots of unity. We have just seen that GF(p^2) contains all these roots. This means that the polynomial x^4 + 1 has all its roots in GF(p^2), an extension of degree 2. This implies that the irreducible factors of x^4 + 1 have degree at most 2, and the polynomial cannot be irreducible. There is another proof, which allows you to find infinitely many polynomials with the same characteristic (they are irreducible over Q, but reducible over any finite field). Consider a polynomial f(x), irreducible over Q, with Galois group G. Let p be a prime, and write f_p(x) for the polynomial reduced modulo p, and G_p for the Galois group of f_p over GF(p). We use two results from Galois theory: * The Galois group of any polynomial over a finite field is cyclic. * With the above notation, G_p is isomorphic to a subgroup of G (intuitively, this means that reducing modulo p replaces the Galois group with a subgroup). Over C, the roots of x^4 + 1 are ((+/-)1 (+/-)i)*sqrt(2)/2. This shows that the Galois group is C2 x C2, generated by the permutations (i,-i) and (sqrt(2),-sqrt(2)). As the group of G_p must be a cyclic subgroup of C2 x C2, it has order at most 2, which shows that the irreducible factors of x^4 + 1 have degree at most 2. Some time ago, I wrote a small paper on that subject; you can find it on: http://mathforum.org/dr.math/gifs/quasired.pdf Please feel free to write back if you require further assistance. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/