# Irreducible polynomials over finite fields

1. Oct 29, 2005

### gonzo

Can someone explain to me why the following is true (ie, show me the proof, or at least give me a link to one):

Over the field Zq the following polynomial:

x^q^n-x

is the product of all irreducible polynomials whose degree divides n

Thanks.

2. Oct 31, 2005

### TenaliRaman

Somethings not quite right in the statement i think. First of all, i guess the q is prime. Secondly, do you mean over the field GF(q^n) and not Z_q ?

Now that i think about it, you did mean Z_q. Let me call it F_q rather.
The proof of this is carried out over some steps.

1. Lemma : If f belongs F_q[x] is an irreducible polynomial over F_q of degree m (say), then f(x) would divide x^q^n - x iff m divides n
This would imply that all monic irreducible polynomials over F_q that we see in the factorization of x^q^n-x (belonging to F_q[x]) are exactly those whose degree divides n

2. Lemma : An f belonging to F_q[x] has a multiple root iff (f,f') != 1
Now Consider g(x) = x^q^n-x. So g'(x) = -1. So from the above lemma, we get that all monic irreducible polynomials whose degree divides n, occur exactly once in factorization of g in F_q[x]

Hence proved.
I have avoided proofs of the above lemmas. I guess they should be simple enough to be proved.[/edit]

-- AI

Last edited: Oct 31, 2005
3. Oct 31, 2005

### gonzo

Thanks, but could you please show me the proof for lemma 1? And yes, q has to be prime, sorry for not stating that, I thought it was implied since I said Zq was a field.

4. Nov 1, 2005

### mathwonk

well the roots of that polynomial form a field extension of Fq, of degree n, hence their minimal polynomials are all factros of that polyno9mial. isnt that about it?

5. Nov 1, 2005

### mathwonk

oh and just because Fq is a field, it does not of course follow that q is prime, unless you think that Fq means Z/qZ.

usually Fq denotes the unique field of order q where q is a power of a prime p.

6. Nov 2, 2005

### TenaliRaman

Lemma 1 : If f belongs F_q[x] is an irreducible polynomial over F_q of degree m (say), then f(x) would divide x^q^n - x iff m divides n

Proof :
First half -->
Let k be a root of f(x)
F_q(k) is a subfield of F_q^n (why??)
[F_q(k):F_q] = m
but [F_q^n : F_q] = n
Therefore, m divides n (why??)

Converse,
given m|n
F_q^m is a subfield of F_q^n (why??)

If k is a root of f,
then F_q(k) = F_q^m (why??)

Therefore, k is a root of x^q^n - x (why??)
Hence, f divides x^q^n - x

I have left a lot of details in the proof, try to fill them in.

-- AI

7. May 21, 2008

### the_fox

Hi everyone. I have a question: How can we show that an element s of order q^n -1 belonging to GL(n,q) has a minimal polynomial of degree n? Or equivalently that it's characteristic polynomial is irreducible?

8. May 21, 2008

### matt grime

What are the definitions of all the things involved? Let's write them out.

1) What is the definition of min poly?

2) Suppose that f is reducible: f(x)=g(x)h(x) and that a is a root of f, i.e. f(a)=0.

3) Does that imply anything about g(a) or h(a)?

4) Remember this is a field

9. May 21, 2008

### the_fox

Sorry about that. I realized it was a dead thread after I posted. To answer 2) it would imply that a would either be a root of g(x) or h(x). But I still don't see how that would give us the irreducibility of the characteristic polynomial.

10. May 21, 2008

### matt grime

So, if it's a root of a poly of smaller degree, wouldn't that negate some part of the definition of _minimal_ (I think I mistakenly used characteristic in the last post) polynomial?

11. May 21, 2008

### the_fox

If you use the minimal polynomial, then what we need to show is that it's degree is n. I simply said that this is equivalent to showing that the characteristic polynomial is irreducible (that's because the minimal polynomial is irreducible and divides the characteristic polynomial). I will make the question more specific: Take GL(5,2)
and the element [01110]
[00011]
[00111]
[11000]
[01000]
which is of order 31. It's minimal polynomial is x^5 + x^4 + x^3 + x^2 + 1. How can we assure that it's degree is 5 without evaluating it. It could as easily be 2 or 3 or whatever.

12. May 21, 2008

### matt grime

Ah, got you. Not having a good time with my return to this kind of mathematics.

13. May 21, 2008

### matt grime

Well, the obvious observation is that if $a$'s char poly is reducible, then it implies that $a$ lies in a proper subfield of F_{q^n}, i.e. the splitting field of the char poly is not F_{q^n}. But I'm not seeing a way to write that in a way that doesn't just say 'nah, because it is'.

14. May 21, 2008

### matt grime

I suppose the more formal proof goes along the lines of:

the roots of a poly of degree k form a subfield of degree q^k, and hence any element has order at most q^k-1, if k is not n, then this is a contradiction.

15. Aug 22, 2008

### sd522527

If z is an element of order p^n-1 in GF(p^n), it is the generator of the cyclic multiplicative group, and by the Primitive element theorem, GF(p^n) = Zp[z]. Therefore it's irr. polynomial is of degree n.

16. Aug 22, 2008

### sd522527

I mean Zp(z), the field, of course.

Steve