Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Primitive polynomial?

  1. Sep 10, 2008 #1
    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.)

    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.
  2. jcsd
  3. Sep 12, 2008 #2
    I wonder why there's not much interest. Too hard, or boring maybe? Possibly I confused people with my erroneous statement:

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

    Since 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], the least common multiple of their orders divides the least common multiple of the [tex]q^{d_i} - 1[/tex]. The latter clearly divides [tex](q^{d_1} - 1)(q^{d_2} - 1) ... (q^{d_r} - 1)[/tex], and so a sufficient condition for a contradiction would be that

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

    which is easy to verify.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook