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

I realise 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 [tex]f= f_1 \cdots f_r[/tex], a product of [tex]\ge 2[/tex] (non-trivial) irreducible polynomials over [tex]\mathbb{F}_q[/tex]. Let [tex]deg(f_i) = d_i[/tex], so [tex]d_1 + \cdots + d_r = n[/tex].

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

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Primitive polynomial?

**Physics Forums | Science Articles, Homework Help, Discussion**