Register to reply

Irreducible polynomials over finite fields

Share this thread:
gonzo
#1
Oct29-05, 06:54 AM
P: 277
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.
Phys.Org News Partner Science news on Phys.org
Flapping baby birds give clues to origin of flight
Prions can trigger 'stuck' wine fermentations, researchers find
Socially-assistive robots help kids with autism learn by providing personalized prompts
TenaliRaman
#2
Oct31-05, 07:41 AM
P: 646
[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
#3
Oct31-05, 10:12 AM
P: 277
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
#4
Nov1-05, 11:04 AM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,484
Irreducible polynomials over finite fields

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
#5
Nov1-05, 11:05 AM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,484
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
#6
Nov2-05, 03:13 AM
P: 646
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
#7
May21-08, 11:15 AM
P: 28
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
#8
May21-08, 11:33 AM
Sci Advisor
HW Helper
P: 9,396
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
#9
May21-08, 12:16 PM
P: 28
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
#10
May21-08, 12:48 PM
Sci Advisor
HW Helper
P: 9,396
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
#11
May21-08, 01:18 PM
P: 28
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
#12
May21-08, 02:57 PM
Sci Advisor
HW Helper
P: 9,396
Ah, got you. Not having a good time with my return to this kind of mathematics.
matt grime
#13
May21-08, 03:16 PM
Sci Advisor
HW Helper
P: 9,396
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
#14
May21-08, 03:46 PM
Sci Advisor
HW Helper
P: 9,396
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
#15
Aug22-08, 05:01 AM
P: 2
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
#16
Aug22-08, 05:01 AM
P: 2
I mean Zp(z), the field, of course.

Steve


Register to reply

Related Discussions
Irreducible polynomials Calculus & Beyond Homework 2
Irreducible Polynomials p 5 degree 4 Linear & Abstract Algebra 1
Are the following polynomials irreducible over Z2? Linear & Abstract Algebra 2
Irreducible polynomials Linear & Abstract Algebra 4