Proving the Primality of a Polynomial over Finite Fields

[Hello Kitty]

Let f = X^n + a_{n-1}X^{n-1} + \cdots + a_1X + a_o be a polynomial over \mathbb{F}_q for some prime power q such that the least common multiple of the (multiplicative) orders of its roots (in \mathbb{F}_{q^n}) is q^n -1. I would like to show that one of these roots has order q^n -1. (I.e. the polynomial is primitive.)

I realize that it is sufficient to show that it is irreducible since the orders of roots of irreducible polynomials are all the same.

I assume for contradiction that f= f_1 \cdots f_r, a product of \ge 2 (non-trivial) irreducible polynomials over \mathbb{F}_q. Let deg(f_i) = d_i, so d_1 + \cdots + d_r = n.

Now the roots of f_i lie in \mathbb{F}_{q^{d_i}} and so have order dividing q^{d_i} - 1.

If all of the d_i divide n then all the roots lie in \mathbb{F}_{q^{max(d_i)}} (noting the subfield theorem for finite fields) and hence all have order dividing q^{max(d_i)}-1 which is a contradiction. So we may assume that some d_i does not divide n. Does this imply that q^{d_i}-1 does not divide q^{n}-1? (Certainly the converse of this statement is true.) If it did, I'd be done.

 

[Hello Kitty]

I wonder why there's not much interest. Too hard, or boring maybe? Possibly I confused people with my erroneous statement:

If all of the d_i divide n then all the roots lie in \mathbb{F}_{q^{max(d_i)}} (noting the subfield theorem for finite fields) and hence all have order dividing : q^{max(d_i)}-1...

Anyway, just in case anyone is interested, I think I've solved it. It's easier than I thought:

Since the roots of f_i lie in \mathbb{F}_{q^{d_i}} and so have order dividing q^{d_i} - 1, the least common multiple of their orders divides the least common multiple of the q^{d_i} - 1. The latter clearly divides (q^{d_1} - 1)(q^{d_2} - 1) ... (q^{d_r} - 1), and so a sufficient condition for a contradiction would be that

(q^{d_1} - 1)(q^{d_2} - 1) ... (q^{d_r} - 1) < (q^{d_1+ d_2 + \cdots + d_r} - 1),

which is easy to verify.