Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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" :) –  mathcat May 4 '11 at 7:34
    
Added the finite-fields tag –  Jyrki Lahtonen Jun 25 '11 at 12:32
add comment

1 Answer

up vote 8 down vote accepted

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.

share|improve this answer
3  
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... –  mathcat 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! –  mathcat 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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.