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" :) –  user8969 May 4 '11 at 7:34
    
Added the finite-fields tag –  Jyrki Lahtonen Jun 25 '11 at 12:32

1 Answer 1

up vote 7 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... –  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

Your Answer

 
discard

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