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}$?
 A: 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.
A: 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).
A: 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$. 
