10

Let $\mathbb F_9$ be a finite field of size $9$ obtained via the irreducible polynomial $x^2 + 1$ over the base field $\mathbb F_3$.

  1. How can you find a primitive element?
  2. Make a list of the elements of $\mathbb F_9$ together with a primitive element and all the powers of the primitive element.
azimut
  • 22,696
juliet
  • 349
  • I think there is confusion between the answers ; do you mean primitive element in the field-theoretic sense (i.e. $\mathbb F_9 = \mathbb F_3(\theta)$) or in the group-theoretic sense (i.e. $\mathbb F_9^{\times} = \langle \theta \rangle = { \theta^j , | , 0 \le j \le 7 }$). – Patrick Da Silva Apr 26 '13 at 08:14
  • @PatrickDaSilva: In the context of finite fields a primitive element is a generator of the multiplicative group. This is standard FF speak. Unfortunately it is a bit at odds with the rest of field theory. If you haven't seen it before, there is no way to know about the varying practices, so don't feel bad! – Jyrki Lahtonen Apr 26 '13 at 11:38
  • @Jyrki: What does "FF speak" mean? – Martin Brandenburg Apr 26 '13 at 11:47
  • I guess it stands for Finite Field speak.. :P – Patrick Da Silva Apr 26 '13 at 23:00

4 Answers4

7

Let $\alpha$ be a root of $f = x^2 + 1$. You see immediately that this has period $4$ in $F_9^*$, so $\alpha$ is not a primitive element. However you know that $F_9^*$ is cyclic of order $8$, and thus $\langle \alpha \rangle$ is the unique subgroup of order $4$.

So take any $\beta \notin \langle \alpha \rangle$, and this will be primitive. For instance, take $\beta = \alpha + 1$. In computing the powers, just use $\alpha^2 = -1$. (Of course you mean computing the powers in the form $c + d \beta = (c+1) + d \alpha$, for $c, d \in F_3$.)

You can also note that the minimal polynomial of $\beta$ over $F_3$ is $g = (x -1)^2 + 1 = x^2 + x -1$, so that $\beta^2 + \beta - 1 = 0$. So you can use the relations $\beta^{i+2} = - \beta^{i+1} + \beta^{i}$ to quickly compute the powers of $\beta$.

Andreas Caranti
  • 68,873
6

  1. I assume that you are looking for a generator of $F^*$. You can just go through all the $8$ elements of $F^*=\{1,-1,x,x+1,x-1,-x,-x+1,-x-1\}$ and compute their multiplicative orders. But with a little bit of thought you can avoid most of these computations. The following method is also applicable in other finite fields. We have the Frobenius automorphism $a \mapsto a^3$. Remark that $a$ is a generator iff the order is $8$ iff $a^4=-1$. This already excludes $1,-1,x,-x$. So we should try $a=x+1$, and compute $a^3=x^3+1=x(-1)+1$, and $a^4=(-x+1)(x+1)=1-x^2=-1$. This shows that $x+1$ is a generator. The other generators are $x-1,-x+1,-x-1$.

  2. Again you can do this easily with the help of the Frobenius.

Martin Brandenburg
  • 163,620
3

Assuming the field-theoretic sense :

You want to find an element $\theta$ such that $\mathbb F_9 = \mathbb F_3(\theta)$.

Since $x^2 = -1$, all the elements of $\mathbb F_9$ are $$ 0,1,2, x,x+1,x+2, 2x,2x+1,2x+2 $$ and you multiply them together with the relation $x^2 +1 = 0$, or $x^2 = 2$. Since every element of $\mathbb F_9$ looks to be a linear polynomial in $x$... how about considering any of the last $6$ elements as primitive elements? If you need help understanding why they are primitive, ask.

Assuming the group-theoretic sense described in my comment for the question :

There is a theorem which tells you that $\mathbb F_9^{\times}$ is a cyclic group, and since $\mathbb Z / 8 \mathbb Z$ has $4$ possible generators under addition (namely $1,3,5,7$), you expect to possibly find $4$ generators of $\mathbb F_9^{\times}$.

$1$, $2$, $x$ and $2x$ obviously don't generate $\mathbb F_9$ because $2^2 = 1$ and $x^2 = 2$, so $\langle 2 \rangle = \{ 1, 2\} \neq \mathbb F_9^{\times}$, $\langle x \rangle = \{ 1, 2, x, 2x \rangle \} \neq \mathbb F_9^{\times}$ and $\langle 2x \rangle = \langle x \rangle$. Therefore, the other $4$ elements, namely $x+1,2x+1, x+2,2x+2$ must all be primitive, because they would correspond to $1,3,5$ and $7$ under an isomorphism $\mathbb F_9^{\times} \cong \mathbb Z / 8 \mathbb Z$ (isomorphisms preserve the order of the elements).

Compute the powers of say, $x+1$ as follows : $(x+1)^2 = x^2 + 2x + 1 = 2 + 2x + 1 = 2x$ using the fact that $x^2 + 1 = 0$, hence $x^2 = 2$. Using your preceding calculations, $$ (x+1)^3 = (x+1)^2 (x+1) = (2x)(x+1) = 2x^2 + 2x = 2x+1,$$ and so on until you have all of them.

Hope that helps,

Patrick Da Silva
  • 41,413
  • This is not correct, $x=i$ has multiplicative order $4$. – Martin Brandenburg Apr 26 '13 at 08:05
  • Yes, but it is still a primitive element, because $\mathbb F_9 = \mathbb F_3(x)$. Right? (by the way, no need to call this element $i$ just because it comes from $x^2 + 1 = 0$... might as well just call it $x$) That is the definition of being a primitive element. I don't need the element $x$ to generate the multiplicative group , I need it to generate the field. – Patrick Da Silva Apr 26 '13 at 08:10
  • Ok, you are right. It is a primitive element in the sense of field theory, but not in the sense of group theory. And the latter is meant here because of part 2. – Martin Brandenburg Apr 26 '13 at 08:12
  • I assumed it was in the field-theoretic sense, otherwise we would've asked for a generator of the multiplicative subgroup instead, which is cyclic for finite fields, and of course this is a different question. – Patrick Da Silva Apr 26 '13 at 08:12
  • @Martin Brandenburg : I still think there is confusion... to be honest I've never seen the generator of the cyclic group be called "primitive element". The closest I've heard would be "primitive root" for the generator of the cyclic group of the $n^{\text{th}}$ roots of unity in $\mathbb C$. Although this term seems to exist in "litterature" (if we can call wiki that) : https://en.wikipedia.org/wiki/Primitive_element_%28finite_field%29 – Patrick Da Silva Apr 26 '13 at 08:16
  • 2
    @PatrickDaSilva, concerning calling the Wikipedia "literature", Terence Tao and Tim Gowers use it routinely as a reference in their blogs, so I think we common mortals can do the same without any worries. – Andreas Caranti Apr 26 '13 at 08:24
  • @Andreas : I wasn't concerned about quoting it, but more about calling it "literature" :P – Patrick Da Silva Apr 26 '13 at 08:25
  • 1
    @PatrickDaSilva,I see your point. IMVHO the only criterion for qualifying as literature is quality, and many (certainly not all) Wikipedia entries in Maths are certainly up to very high standards. – Andreas Caranti Apr 26 '13 at 08:29
  • You can simplify the calculations by not replacing $-1$ with $2$. – Martin Brandenburg Apr 26 '13 at 08:39
  • 1
    @Martin : Personally I think of $F_3$ as $\mathbb Z/3\mathbb Z$, hence its elements are $0,1,2$ in my head and I think of $2^2 = 1$. This simplifies computations for me... it's a matter of taste. – Patrick Da Silva Apr 26 '13 at 23:02
1

Let $A= \left( \begin{array}{cc} 0 & -1 \\ 1 & 0 \end{array} \right)$ be the companion matrix of $x^2+1$. You can show that $F$ is isomorphic to $F_3[A]$.

Seirios
  • 33,157