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$.
- How can you find a primitive element?
- Make a list of the elements of $\mathbb F_9$ together with a primitive element and all the powers of the primitive element.
4 Answers
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$.
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$.
Again you can do this easily with the help of the Frobenius.
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,
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]$.
