To Factorize $x^{27}-x$ over $\mathbb F_3$. Problem 7.5 in Chapter 15 of Artin's Algebra asks to factorize $x^{27}-x$ over $\mathbb F_3$.
Here is what I have done.
$x^{27}-x=x(x^{26}-1)= x(x^{13}-1)(x^{13}+1)$.
In am having trouble factorizing $x^{13}-1$ and $x^{13}+1$ in $\mathbb F_3$.
$x^{13}-1=(x-1)(x^{12}+x^{11}+\cdots+x+1)$.
I know that $x^{12}+x^{11}+\cdots+x+1$ is reducible over $\mathbb F_3$ because the degree of this polynomial, which is $12$, does not divide $3$. ($3$ is the exponent of $3$ which gives $27$).
But I can't see how to factorize this polynomial.
Similarly for $x^{13}+1$.
Can somebody help?
 A: The irreducible factors of $x^{3^3}-x$ are precisely the monic irreducible polynomials of degree $1$ and $3$ over $\mathbb F_3$. So there are the $3$ linear factors and $8$ irreducible polynomials of degree $3$. Giving them all is only a matter of patience.
You can do it like this:
Make a list of all polynomials of the form $x^3+ax^2+bx+c$ with $c \neq 0$. Cancel all those polynomials with $f(1) = 0$ or $f(-1)=0$. What is left are precisely the $8$ polynomials you are looking for.
A: Shaking (not stirring) my bag of tricks for this problem. The following dropped out.
Start with 
$$
p_1(x)=x^3-x+1,\qquad p_2(x)=x^3-x-1.
$$
The irreducibility of these has been explained many times on our site (search for $x^p-x+a$ over $\Bbb{F}_p$).
The first trick is that if a polynomial $p(x)$ of degree $k>1$ is irreducible, then so is its reciprocal polynomial
$$
\tilde{p}(x):=x^kp(\frac1x).
$$
For you can easily check that $p(x)=a(x)b(x)\Leftrightarrow \tilde{p}(x)=\tilde{a}(x)\tilde{b}(x)$. (the reciprocal of the reciprocal is the original polynomial).
This gives us two more irreducibles:
$$
p_3(x)=\tilde{p_1}(x)=x^3-x^2+1,\qquad
p_4(x)=\tilde{p_2}(x)=x^3+x^2-1.
$$
The next trick is that if $p(x)$ is and irreducible cubic, then so are $p(x\pm1)$. These won't give us anything new on $p_1$ or $p_2$, because those polynomials are invariant under this linear substitution. However, we do get
$$
p_5(x)=p_3(x+1)=(x^3+1)-(x^2+2x+1)+1=x^3-x^2+x+1
$$
and
$$
p_6(x)=p_4(x+1)=(x^3+1)+(x^2+2x+1)-1=x^3+x^2-x+1.
$$
Leaving it to you to figure out which of the tricks you should reapply to get the missing two irreducible cubics.

I was planning on using  the following trick as well, but looks like we don't need it.
Assume that $\alpha$ is a zero of $p_1(x)$ in $\Bbb{F}_{27}$. Let's find the minimal polynomial of $\alpha^2$.
To that end consider the polynomial
$$
p_1(x)p_1(-x)=(x^3-x+1)(-x^3+x+1)=-x^6+2x^4-x^2+1=-q(x^2),
$$
where $q(x)=x^3+x^2+x-1$. We see that $q(\alpha^2)=-p_1(\alpha)p_2(\alpha)=0$. It is easy to see that $\alpha^2$ cannot be an element of the prime field, so its minimal polynomial is also a cubic ...
A: Claim: $x^{27}-x$ factors over $\Bbb{F}_3$ as the product of all irreducible polynomial of degree $1$ and $3$.
Proof:
First notice that $x^3-x \mid x^{27}-x$ since $3\mid 27$, so $\Bbb{F}_3\subset \Bbb{F}_{27}$ and so every element of $\Bbb{F}_3$ divides $x^{27}-x$. I.e.: $x-a\mid x^{27}-x \, \forall a \in \Bbb{F}_3$. So there are $3$ irreducible polynomial of degree $1$.
Let $g(x) \in \Bbb{F}_3[x]$ be a monic irreducible polynomial of degree $3$ and let $\beta$ be one of its roots in $\Bbb{F}_{27}$. Then $[\Bbb{F}_3(\beta):\Bbb{F}_3] = 3$, so, since all the finite fields of a fixed order are isomorphic to each other, $\Bbb{F}_3(\beta) \approx \Bbb{F}_{27}$. Therefore $x-\beta \mid x^{27}-x$. Since you can do this reasoning for all the roots of $g$ over $\Bbb{F}_{27}$ we have $g(x) \mid x^{27}-x$. Since there are $8$ irreducible polynomial of degree $3$ we are done, since the degree of the multiplication of all the monic irreducible polynomial of degree $1$ and $3$ is $3+8\cdot 3 = 27$.
This might also help you.
