1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Primitive polynomial?
  1. Primitive root ! (Replies: 2)

  2. Primitive polynomials (Replies: 25)

  3. Primitive matrix (Replies: 1)

  4. Primitive elements (Replies: 1)