Factorize $x^9 - 1 $ in $\mathbb F_3[x]$

Question

I was able to factorize $x^9-x$ in $\mathbb F_3[x]$, however, with $x^9-1$ I am not sure what to do.

My first intuition was to do $(x^3-1)(x^3+1)$ but this is clearly just the first step, if not completely misplaced.

Thanks for help!

Answer 1

This is a very "hands-on" answer.

There are only three elements of $\mathbb F_3$, i.e. $0$, $1$ and $2$.

The remainder theorem tells us that if $\mathrm f(a)=0$ then $(x-a)$ is a factor of $\mathrm f(x)$.

Let's try $x=0,1,2$ and see what happens:

\begin{eqnarray*} 0^9-1 &\equiv& 2 \pmod 3 \\ 1^9-1&\equiv& 0 \pmod 3 \\ 2^9-1 &\equiv& 1 \pmod 3 \end{eqnarray*}

Since $\mathrm f(1) \equiv 0 \pmod 3$, it follows that $(x-1)$ is a factor of $\mathrm f(x)$.

You need to use polynomial division, and reduce modulo $3$.

$$\frac{x^9-1}{x-1} = 1+x+x^2+\cdots +x^7+x^8$$

Next, we need to use the Factor Theorem on $\mathrm{g}(x):=1+x+x^2+\cdots +x^7+x^8$.

\begin{eqnarray*} \mathrm g(0) &\equiv& 1 \pmod 3 \\ \mathrm g(1) &\equiv& 0 \pmod 3 \\ \mathrm g(2) &\equiv& 1 \pmod 3 \end{eqnarray*}

It follows that $(x-1)$ divides $\mathrm g(x)$ modulo $3$. Using Polynomial division \begin{eqnarray*} \frac{\mathrm g(x)}{x-1} &=& x^7+2x^6+3x^5+4x^4+5x^3+6x^2+7x+8+\frac{9}{x-1} \\ \\ &\equiv& x^7+2x^6+x^4+2x^3+x+2 \pmod 3 \end{eqnarray*}

Let $\mathrm h(x) := x^7+2x^6+x^4+2x^3+x+2$ and proceed as before.

We see that $\mathrm h(x) \equiv 0 \pmod 3 \iff x \equiv 1 \pmod 3$, so consider

\begin{eqnarray*} \frac{\mathrm h(x)}{x-1} &=& x^6+3x^5+3x^4+4x^3+6x^2+6x+7+\frac{9}{x-1} \\ \\ &\equiv& x^6+x^3+1 \pmod 3 \end{eqnarray*}

Again, we see that $(x-1)$ divides $x^6+x^3+1 \pmod 3$, leaving $x^5+x^4+x^3+2x^2+2x+2$, which is divisible by $x-1$. This leaves $x^4+2x^3+2x+1$, which is divisible by $x-1$. This gives $x^3+2$. This is divisible by $x-1$ which leaves $x^2+x+1$. This is divisible by $x-1$, and that leaves $x+2$. This is congruent to $x-1$.

\begin{eqnarray*} (x-1)^9 &=& x^9-9x^8+36x^7-84x^6+126x^5-126x^4+84x^3-36x^2+9x-1 \\ &\equiv& x^9 + 2 \pmod 3 \\ &\equiv& x^9 -1 \pmod 3 \end{eqnarray*}

Answer 2

By Fermat's little theorem, over $\mathbb{F}_3$ we have $$ x^9-1 \equiv (x-1)^9.$$

Answer 3

$x\mapsto x^3$ is a field automorphism in characteristic $3$, hence $$x^9-1=x^{3^2}-1^{3^2}=(x-1)^{3^2}=(x-1)^9.$$

Answer 4

Note that \begin{eqnarray*} (x+2)^9=x^9+18x^8+144x^7+672x^6+2016x^5+4032x^4+5376x^3+4608x^2+2304x+512 \end{eqnarray*} Now notice that all of these coefficients are divisible by $3$ apart from the first and the last. So $x^9-1=(x+2)^9$ modulo 3.

Answer 5

Recall: $ $ Frobenius / Freshman's Dream: $\ \ (x+y)^{\large p} =\, x^{\large p} + y^{\large p}\, $ in $\,\Bbb F_p.\,$ Applied twice we have

$$\begin{align} (x-y)^{\large p} &= \ x^{\large p} - y^{\large p}\\ \overset {(\ \ \ )^{\Large p}}\Longrightarrow\ (x-y)^{\large p^{\Large 2}}\! &= x^{\large p^{\Large 2}}\!\! - y^{\large p^{\Large 2}} \end{align}$$