# Finite fields and primitive elements

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.
• 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 \}$). Commented Apr 26, 2013 at 8: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! Commented Apr 26, 2013 at 11:38
• @Jyrki: What does "FF speak" mean? Commented Apr 26, 2013 at 11:47
• I guess it stands for Finite Field speak.. :P Commented Apr 26, 2013 at 23:00

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$.

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.

• Remark: This is not as elegant as Andreas Caranti's answer. The only advantage is that you don't have to know in advance that the group is cyclic. Commented Apr 26, 2013 at 8:29
• I think I understand your answer, but where does frobenius help finding the primitive element? Commented Jun 27, 2018 at 3:03
• How is $1-x^2=-1$? Is it because $1-x^2=1+2x^2=1+2(-1)=1$ ? where $-1=2$ and $x^2=-1$
– MAS
Commented Dec 6, 2020 at 16:28

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,

• This is not correct, $x=i$ has multiplicative order $4$. Commented Apr 26, 2013 at 8: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. Commented Apr 26, 2013 at 8:10
• @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. Commented Apr 26, 2013 at 8:24
• @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. Commented Apr 26, 2013 at 8:29
• @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. Commented Apr 26, 2013 at 23:02

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]$.

• in the solution of the question F9 is defined as F9={a+bx:a,b in Commented Apr 26, 2013 at 8:30