# primitive root of a finite field

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)$.

Questions:

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!

-
It's not "primitive root of a polynomial", it's "primitive root of a finite field." – Arturo Magidin May 3 '11 at 4:19
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.) – Qiaochu Yuan May 3 '11 at 4:20
thanks for the comments! I also changed the title from "polynomial" to "finite field" :) – user8969 May 4 '11 at 7:34
Added the finite-fields tag – Jyrki Lahtonen Jun 25 '11 at 12:32

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.
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? – Gerry Myerson May 3 '11 at 6:27
@Gerry $\phi(15)=8$? lol, I am guessing... – user8969 May 4 '11 at 7:31
by 8 choices for $\beta$, do you mean 8 primitive roots or 8 elements that can potentially be primitive roots? thanks! – user8969 May 4 '11 at 8:32
@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? – Gerry Myerson May 4 '11 at 13:14