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.

Can a primitive root of a polynomial over $GF(2)$ ever not generate a multiplicative group?

I have some notes from my review of finite field extensions a while ago that I've been rereading. It's the last statement that's throwing me. I've included some preceding notes for context.

If $p(x)$ is an irreducible polynomial of degree $n$, then adjoining a root of $p$ to $GF(2)$ generates an extension of degree $n$, which is necessarily a field, $E$, with $2^n$ elements.

The multiplicative group of nonzero elements in $E$ has order $2^n - 1$.
Thus by Lagrange's Theorem, every nonzero element $a$ of $E$ satisfies $a^{2^n - 1} = 1$. Thus every element $a$ in $E$ is a root of $g(X) = > X^{2^n} - X$.

In other words, $E$ is exactly the set of all roots of $g(X)$. Now the roots of the original $p(x)$ are also roots of $g(X)$, and so $p(x)$ divides $g(X)$ (after making the variables the same).

Conversely, if $f(x)$ is any polynomial that divides $g(x)$, then the roots of $f(x)$ lie in $E$, so they generate a subfield of $E$. If they generate all of $E$, and if $f(x)$ is irreducible, then they must have degree $n$.

Now, let $\rho$ be a primitive root of $f$, where f is irreducible. So $\rho$ will generate $E$ as a field, but not necessarily generate $E-\{0\}$ as a multiplicative group.

share|improve this question
    
Please put the question in the body of the message, not just the title. –  Arturo Magidin May 18 '11 at 4:31
    
@Arturo, thanks for edit. –  ThomasMcLeod May 18 '11 at 4:33
2  
What is a primitive root of a polynomial, in some general context? –  KCd May 18 '11 at 4:36
    
I also don't see what the problem is. For example, looking at fields of size 9, we can use F_9 = F_3[i] = F_3[x]/(x^2+1). In this field, i generates the field F_9 over F_3 but i is not a generator of the group F_9*. Big deal. There is no paradox. –  KCd May 18 '11 at 4:38
    
@KCd, the problem is that someone new to the topic may expect that the question, "Is $\alpha$ a generator?" would have a yes/no answer, and is surprised to learn that both "yes" and "no" are correct, depending on whether one is generating the field or the multiplicative group of the field. A rose is a rose is a rose, but a generator is not a generator, pace Gertrude Stein. –  Gerry Myerson May 18 '11 at 6:32

1 Answer 1

up vote 4 down vote accepted

I think this is an example of what you're after. The polynomial $x^4+x^3+x^2+x+1$ is irreducible over the field of 2 elements, so any root $\alpha$ generates the field of 16 elements. But $\alpha^5=1$ (note that the given polynomial is a factor of $x^5-1$), so $\alpha$ doesn't generate the 15-element multiplicative subgroup as a group.

share|improve this answer
1  
And of course, the smallest example occurs in the field of 16 elements, since all smaller fields have multiplicative group that is either trivial or of prime order. –  Arturo Magidin May 18 '11 at 4:36
    
Um, a smaller example occurs in the field of 9 elements, as in my comments to the original question. The group F_9* is not trivial or of prime order. –  KCd May 18 '11 at 4:44
2  
@KCd: The original was only asking about fields of order $2^n$, and the question asks specifically about extensions of $GF(2)$, so I wasn't counting $F_{p^k}$ for odd primes. Though the comment does not make that clear. –  Arturo Magidin May 18 '11 at 4:46
    
This is precisely the answer. Was head scratching for an hour on this. So, can we say then that $x^4+x^3+x^2+x+1$ is irreducible but not primitive? –  ThomasMcLeod May 18 '11 at 4:58
1  
The one meaning of "primitive" only applies over finite fields, the other is useful only over non-fields (since over a field all the non-zero coefficients are units). –  Gerry Myerson May 18 '11 at 6:37

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.