This is a problem similar to one of my homework problems, but not on the homework. The problem states that:

Find a primitive root $\beta$ of $F_2[x]/(x^4+x^3+x^2+x+1)$.


  1. I know what a primitive root of a prime number is, but what is a primitive root of a polynomial (or is it called something like a field extension here)?

  2. My book gives this hint: $[x]=\alpha$ doesn't work because $\alpha^5=1$. There are eight choices of $\beta$. I am basically lost on the hint. What is $\alpha$? Why doesn't it work? Why are there 8 choices for $\beta$? Wouldn't there be $2^4 =16$ choices? (or that's the number of polynomials in the field?)

Sorry for the long questions, since I am quite lost right now. Hopefully my questions make sense, and any help would be appreciated!

  • $\begingroup$ It's not "primitive root of a polynomial", it's "primitive root of a finite field." $\endgroup$ – Arturo Magidin May 3 '11 at 4:19
  • $\begingroup$ I guess it means to find an element whose powers give all nonzero elements of the extension. (This is analogous to how a primitive root modulo $p$ is an element of $\mathbb{F}_p$ whose powers give all nonzero elements of the extension.) $\endgroup$ – Qiaochu Yuan May 3 '11 at 4:20
  • $\begingroup$ thanks for the comments! I also changed the title from "polynomial" to "finite field" :) $\endgroup$ – user8969 May 4 '11 at 7:34
  • $\begingroup$ Added the finite-fields tag $\endgroup$ – Jyrki Lahtonen Jun 25 '11 at 12:32

The multiplicative group of nonzero elements of a finite field is always cyclic. A "primitive root" of a finite field is a generator for the multiplicative group of nonzero elements.

Note that $x^4+x^3+x^2+x+1$ is irreducible over $\mathbb{F}_2$: it has no roots, and it is not the product of two irreducible quadratics (the quadratics are $x^2$, $x^2+1$, $x^2+x$, and $x^2+x+1$, and the only irreducible one is the latter; but $(x^2+x+1)^2 = x^4 + x^2 + 1$). So $\mathbb{F}_2[x]/(x^4+x^3+x^2+x+1$ is a field of degree $4$ over $\mathbb{F}_2$ (hence, of order $2^4 = 16$). So you are looking for an element in the field of $16$ elements whose multiplicative order is exactly $15$. The book is noting that even though this field equals $\mathbb{F}_2(\alpha)$ (where $\alpha$ is the class of $x$ in the quotient), $\alpha$ doesn't work because it is of order $5$. That is: while it is true that if $\beta$ is a primitive root for the field $GF(p^k)$, then $GF(p^k) = \mathbb{F}_p(\beta)$, the converse does not necessarily hold as this example shows.

  • 3
    $\begingroup$ Why $8$ choices for $\beta$? The reason is hidden in Arturo's answer; let me make it a little more explicit. The field has $16$ elements; its multiplicative group is everything but zero, so it has $15$ elements; this group is cyclic, so we're dealing with the cyclic group of $15$ elements, and we want a generator (synonym, in this context, for primitive element). Of the $15$ elements of a cyclic group of order $15$, how many are generators? $\endgroup$ – Gerry Myerson May 3 '11 at 6:27
  • $\begingroup$ @Gerry $\phi(15)=8$? lol, I am guessing... $\endgroup$ – user8969 May 4 '11 at 7:31
  • $\begingroup$ by 8 choices for $\beta$, do you mean 8 primitive roots or 8 elements that can potentially be primitive roots? thanks! $\endgroup$ – user8969 May 4 '11 at 8:32
  • $\begingroup$ @mathcat, yes, $\phi(15)=8$. Now, does a cyclic group of order $15$ have $8$ generators, or does it have $8$ elements that can potentially be generators? $\endgroup$ – Gerry Myerson May 4 '11 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy