Irreducible factors of x^16 - 1 over GF(3)

Question

Just want to double check my work. I'm trying to list the irreducible factors of $x^{16} − 1 $ over $GF (3)$ of degree $1$ and $2$ . Here's what I have:

$$x + 1, x + 2, x^2 + x + 2, x^2 + 2x + 2$$

Is that all of them?

Answer 1

Not quite: $$ x^{16}-1=(x^8-1)(x^8+1)=(x^4-1)(x^4+1)(x^8+1). $$ You correctly factored $$ x^4+1=x^4+4=(x^4+4x^2+4)-4x^2=(x^2+2)^2-(2x)^2=(x^2-2x+2)(x^2+2x+2), $$ but you haven't fully factored $x^4-1$ yet.

The remaining factors are those of $x^8+1$. By repeating the above trick you can write it as a product of two quartics. Those quartics are irreducible though. This is because if $\alpha$ is a zero of $x^8+1$ in some extension field of $GF(3)$, then $\alpha$ is of order $16$. This means that $\alpha\in GF(81)\setminus GF(9)$. Consequently its minimal polynomial is of degree four.

Answer 2

You missed one.

In Maple:

select(t -> degree(t) <= 2, Factor(x^16-1) mod 3);

Answer 3

Since $$ x^{16}-1 = \Phi_{16}(x)\,\Phi_{8}(x)\,\Phi_4(x)\,\Phi_2(x)(x-1) $$ and $\Phi_{16}(x)$ completely splits over $\mathbb{F}_{3^4}$ since $16|(3^4-1)$, $\Phi_8(x)$ completely splits over $\mathbb{F}_{3^2}$ since $8|(3^2-1)$ and $\Phi_4(x)$ is irreducible over $\mathbb{F}_3$, we have that $x^{16}-1$ splits as a product of two quartic irreducible polynomials, three quadratic irreducible polynomials and two linear factors.