# Find a primitive element for the field extension $\mathbb{F}_{125}/\mathbb{F}_5$ - which elements of $\mathbb{F}_{125}$ are not in $\mathbb{F}_5$?

I want to find a primitive element for the field extension $\mathbb{F}_{125}/\mathbb{F}_5$.

I constructed $\mathbb{F}_{125}$ as $\mathbb{F}_5[X]/\langle X^3 + X + 1 \rangle$. Since the degree of the polynomial is $3$, there are no intermediate fields, so every element from $\mathbb{F}_{125}$ which is not in $\mathbb{F}_{5}$ should be a primitive element.

But how do I know which elements are in $\mathbb{F}_{5}$ and which are not? For example, is $X + \langle X^3+X+1 \rangle$ in $\mathbb{F}_{5}$?

• well certainly the image of $x$ is not in $\Bbb F_5$, since the polynomial is irreducible there. So $\Bbb F_5[x]$ is a subfield, and the degree is $3$ for the big field, hence... – Adam Hughes Jun 2 '15 at 1:02
• The only elements in $\mathbf{F}_{5}$ are the classes of $0$,$1$, $2$,$3$ and $4$.(ie $1+(x^{3}+x^{2}+1))$ – mich95 Jun 2 '15 at 1:04
• Please clarify. I think that this based on the wrong notion of a primitive element. In the context of finite fields it is standard to call an element primitive, iff it is a generator of the multiplicative group of the said finite field. Much like a primitive root modulo a prime $p$ is a generator of the multiplicative group $\Bbb{Z}_p^*$. I know that elsewhere in the theory of extension fields an element is called primitive, if it is not in any proper subfield. – Jyrki Lahtonen Jun 2 '15 at 6:15
• I meant "primitive" in the sense of the primitive element theorem, i.e. an element of $\mathbb{F}_{125}$ which generates the whole extension if I add it to $\mathbb{F}_5$. I didn't know that this is non-standard terminology and that there's a different usage of "primitive element" for finite fields. – Marc Jun 7 '15 at 19:27

The extension field $\mathbf{F}_{125}$ contains prime field as a subfield, and as a vector space over it has $\{1,\bar X, \bar X^2\}$ as its basis. This shows that $\bar X$ is not in the prime field.

When the degree of a field extension is a prime number any element that is not in the base field will be a primitive element, as you have guessed in this spacial case.

Another easy way to construct a cubic extension over any field of $p$ elements, (or for that matter any field) is to look at the function: $x\mapsto x^3$ which is a homomorphism of $\mathbf{F}_{p}^*$ to itself. Then for any $b$ not in the image the polynomial $X^3-b$ would be irreducible over $\mathbf{F}_{p}$. Of course this is practical only when $p$ is small and so listing them is possible.

Let $u$ be a root of $x^3 + x + 1$ in the algebraic closure of $\Bbb F_5$. Pretty much all we know about $u$ is that: $u^3 + u + 1 = 0$, that is: $u^3 = 4u + 4$.

Note that the vector space (over $\Bbb F_5$) spanned by $\{1,u,u^2\}$ has dimension $3$, giving us that $|\Bbb F_5[u]| = 125$ (we have $5$ choice for each "coordinate", giving $5^3$ vectors in all). You can show that $\Bbb F_5[u]$ is actually a field, that is, $\Bbb F_5[u] = \Bbb F_5(u)$.

Since it is a field $(\Bbb F_5)^{\ast}$ is a (finite) abelian group, which has order $124$. The divisors of $124$ are: $1,2,4,31,62$ and $124$. A primitive element of this group is an element of order $124$, which is most assuredly not every element of $\Bbb F_5(u) - \Bbb F_5$, since there are only $60$ generators, and $120$ elements in the set I just listed.

Let's look at $u$, just for grins. Now $u^2 \neq 1$ (these are linearly independent over $\Bbb F_5$), so $u$ isn't of order $2$. $u^4 = (u^3)(u) = (4u + 4)(u) = 4u^2 + 4u \neq 1$ (as this is a polynomial in $u$ of degree $< 3$). So $u$ is not of order $4$, either.

$u^{31}$ is more of a challenge:

$u^{31} = (u^6)^5(u) = ((u^3)^2)^5(u) = ((4u + 4)^2)^5(u) = (u^2 + 2u + 1)^5(u)$

$= (u^{10} + 2u^5 + 1)(u) = u^{11} + 2u^6 + u$. We pause to calculate some smaller powers of $u$:

$u^6 = (u^3)^2 = (4u + 4)^2 = u^2 + 2u + 1$ (we actually saw this above).

$u^{11} = (u^6)(u^5) = (u^2 + 2u + 1)(u^3)(u^2) = (u^2 + 2u + 1)(4u + 4)(u^2)$

$=(u^2 + 2u + 1)(4u^3 + 4u^2) = 4u^5 + 2u^4 + 2u^3 + 4u^2$.

Hmm....maybe we better calculate $u^5$, now:

$u^5 = u^3u^2 = (4u + 4)(u^2) = 4u^3 + 4u^2 = 4(4u + 4) + 4u^2 = 4u^2 + u + 1$.

So $u^{11} = 4(4u^2 + u + 1) + 2(4u^2 + 4u) + 2(4u + 4) + 4u^2$

$= u^2 + 4u + 4 + 3u^2 + 3u + 3u + 3 + 4u^2 = 3u^2 + 2$, and so:

$u^{31} = 3u^2 + 2 + 2(u^2 + 2u + 1) + u = 4$, so evidently, $u$ is not of order $31$, either.

However, $u^{62} = (u^{31})^2 = 4^2 = 1$, so $u$ is only of order $62$, and thus not a primitive element.

(Warning: I find this kind of arithmetic very difficult to do long-hand, so there may be mistakes).

• +1 for answering based on IMO standard interpretation of a primitive element in the context of finite fields. – Jyrki Lahtonen Jun 2 '15 at 6:16
• Sorry for the confusion and thanks for your effort. See my comment above for my use of terminology. – Marc Jun 7 '15 at 19:30

Keep in mind that $X$ is an element of $\Bbb F_5[X]$, and its coset $\overline{X}$ in $\Bbb F_5[X]/\langle X^3+X+1\rangle$ is not in $\Bbb F_5$.