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/