Irreducible polynomials over finite fields

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.

TenaliRaman

[s]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 ?[/s]

[edit]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

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.

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?

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.

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

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?

matt grime

Resurrecting dead threads isn't usually a good idea.

But to answer your question...

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

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.

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?

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.

matt grime

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

matt grime

Well, the obvious observation is that if [itex]a[/itex]'s char poly is reducible, then it implies that [itex]a[/itex] 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'.

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.

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.

sd522527

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

Steve