3
$\begingroup$

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.

  • 0
    Please put the question in the body of the message, not just the title.2011-05-18
  • 0
    @Arturo, thanks for edit.2011-05-18
  • 2
    What is a primitive root of a polynomial, in some general context?2011-05-18
  • 0
    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.2011-05-18
  • 1
    @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.2011-05-18
  • 0
    @KCd, not a paradox, per se. However, an important observation in applications where the object of interest is the multiplicative group, not the field. E.g., coding theory.2011-05-18
  • 0
    See also my [answer here](http://math.stackexchange.com/questions/3805/powers-of-x-as-members-of-galois-field-and-their-representation-as-remainders/3813#3813) to a closely related question.2011-05-18

1 Answers 1

7

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.

  • 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.2011-05-18
  • 0
    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.2011-05-18
  • 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.2011-05-18
  • 0
    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?2011-05-18
  • 0
    If (as is common in some areas), by "primitive polynomial" you mean "monic irreducible polynomial over a finite field whose roots are primitive roots of the field they generate" (or words to that effect, connecting "primitivity" of the polynomial with the roots being generators), then yes. I mention it because there is another common meaning for "primitive polynomial" (gcd of the coefficients is a unit), and this polynomial is primitive by that definition.2011-05-18
  • 0
    @Arturo, it's definitely the former.2011-05-18
  • 0
    @Thomas: Yes, I figured. Just thought I would point out that there is another "standard meaning", in case you run into confused looks elsewhere. (-:2011-05-18
  • 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).2011-05-18
  • 0
    In fact I have the same answer in [this question](http://math.stackexchange.com/questions/3805/powers-of-x-as-members-of-galois-field-and-their-representation-as-remainders/3813#3813), so this question is essentially a duplicate.2011-05-18