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.