To Factorize $x^{27}-x$ over $\mathbb F_3$.

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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 ...