Irreducible Polynomials In $F_3$ Let us say I have some irreducible polynomials in $F_3$
$$p(x) = x^3 + 2x + 2$$
and 
$$p(x) - 1 = x^3 + 2x + 1.$$ 
Now, using the power of Maple and Wolfram Alpha, we can check that 
$$p(x^{13}) = x^{39} + 2x^{13} + 2$$
and 
$$p(x^{13}) - 1 = x^{39} + 2x^{13} + 1$$
are both irreducible in $F_3$. How can I show that more generally, that $p(x^{13^m})$ and $p(x^{13^m}) - 1$ are irreducible in $F_3$?
My first instinct was to suppose that this was not irreducible. And so there exists some irreducible polynomial $q(x)$ which defines a field extension $F_3/(q(x)) \supset F_3.$ Can we use this fact somehow? If we inductively assume that for each $k < m,$ that $p(x^{13^k})$ is irreducible, then can we construct a tower of fields to get some contradiction?
Secondly, I also found the so-called Rabin's Test for irreducibility.
However, this looks quite messy and very computationally intensive. However, would this be more approachable than the tower of field approach? 
 A: Let's write $p(x)=x^3-x-1$ and $q(x)=p(x)-1=x^3-x+1$.
If $\alpha$ is a zero of $p(x)$ in some extension field (easily seen to be $\Bbb{F}_{27}$),
then by the properties of the Frobenius automorphism
$$\alpha^3=\alpha^3-p(\alpha)=\alpha+1$$
is another. Repeating the dose we see that the last zero is
$$\alpha^9=(\alpha^3)^3=(\alpha+1)^3=\alpha^3+1=\alpha+2.$$
By Vieta relations the product of the zeros of the cubic $p(x)$ is the negative of the constant term, so
$$
-p(0)=1=\alpha\cdot\alpha^3\cdot\alpha^9=\alpha^{13}.
$$
It follows that $\alpha$ is a root of unity of order $13$. Because $\ell=3$ is the smallest positive integer with the property $13\mid 3^\ell-1$ this gives another proof for the fact that $\Bbb{F}_3(\alpha)=\Bbb{F}_{27}$.
Claim 1. The zeros of $p(x^{13^n})$ in some extension field of $\Bbb{F}_3$ are roots of unity of order $13^{n+1}$.
Proof. Let $\beta$ be such a zero. It follows that $\beta^{13^n}$ is one of the zeros of $p(x)$, hence a root of unity of order $13$. Without loss of generality we can assume that $\beta^{13^n}=\alpha$.
A fact from the first course on cyclic groups is that
$$
\operatorname{ord}(c^k)=\frac{\operatorname{ord}(c)}{\gcd(k,\operatorname{ord}(c))}.
$$
Applying this to $c=\beta, k=13^n$, we see that $m=\operatorname{ord}(\beta)$ satisfies
the equation
$$
13=\operatorname{ord}(\alpha)=\frac{m}{\gcd(13^n,m)}.
$$
This implies first that $m$ must be a power of $13$, and then that we must have $m=13^{n+1}$.
Claim 2. The order of $3$ in the group $\Bbb{Z}_{13^\ell}^*$ is equal to $3\cdot13^{\ell-1}.$
Proof. We already saw that the claim holds when $\ell=1$. More precisely,
$$3^3=1+2\cdot13.\qquad(*)$$ For a power $3^m$ to be congruent to $1$ modulo $13^a$ it obviously also needs to be congruent to $1$ modulo $13^b$ for all $b, 0<b<a$. In particular it needs to be a multiple of $3$. When $\ell$ increases by one, the order of $G=\phi(13^\ell)=12\cdot13^{\ell-1}$ is multiplied by $13$. By considering the projection from $G$ to $\Bbb{Z}_{13}^*$ it follows that the order of $3$ is of the form $3\cdot 13^a$ for some $a<\ell$.
But, an easy induction on $k$ using $(*)$ as the base case, the binomial formula, and the fact that $\binom{13}k$ is divisible by $13$ when $0<k<13$, shows that
$$
3^{3\cdot 13^k}\equiv1+2\cdot13^{k+1}\pmod{13^{k+2}}
$$
for all $k=0,1,2,\ldots$. The claim follows.
Claim 3. Let again $\beta$ be a zero $p(x^{13^n})$. Then $\Bbb{F}_3(\beta)=\Bbb{F}_{3^\ell},$ where $\ell=3\cdot 13^n$.
Proof. By Claim 1 $\beta$ is a root of unity of order $13^{n+1}$. Let
$K=\Bbb{F}_q=\Bbb{F}_3(\beta)$. It is well known that the group $K^*$ is cyclic of order $q-1$. For $K$ to contain an element of order $13^{n+1}$ it is therefore necessary that
$13^{n+1}\mid q-1=3^\ell-1$. It follows that $\ell$ is the smallest positive integer with the property $3^\ell\equiv1\pmod{13^{n+1}}$. By Claim 2 we can conclude that $\ell=3\cdot13^n$.
Irreducibility of $p(x^{13^n})$ over $\Bbb{F}_3$ follows then easily. By Claim 3 the minimal polynomial of $\beta$ over $\Bbb{F}_3$ has degree $\ell=3\cdot13^n$. But the degree of $p(x^{13^n})$ is exactly $3\cdot13^n$, so we can conclude that $p(x^{13^n})$
is the minimal polynomial. In particular $p(x^{13^n})$ must be irreducible.
Irreducibility of $q(x^{13^n})$ follows from this. You can verify that $q(x)=-p(-x)$,
and there is a similar connection between $p(x^{13^n})$ and $q(x^{13^n})$.
