# Polynomial factorization over finite fields

How can i factorize the polynomial $x^{12}-1$ as product of irreducibles polynomials over $\mathbb{F}_4$? Anyone can help me?

-
Do you mean that you want to write $x^{12}-1$ as a product of things in $\mathbb{F}_4[x]$? –  Daenerys Naharis Feb 16 '13 at 2:32
yes I mean that i want to write $x^{12}-1$ as product of thins in $\mathbb{F}_4[x]$ –  Dimitri Feb 16 '13 at 2:34

Let $\alpha$ and $\beta = \alpha^2 = \alpha+1$ denote the two elements of $\mathbb F_4-\mathbb F_2$. Then, $\alpha$ and $\beta$ are roots of $x^2+x+1$ and we have that $$x^3-1 = (x-1)(x^2+x+1) = (x-1)(x-\alpha)(x-\beta).$$ In a field of characteristic $p$, $(a-b)^{p^i} = a^{p^i} - b^{p^i}$ and so we have that $$x^{12} - 1 = (x^3-1)^4 = (x-1)^4(x-\alpha)^4(x-\beta)^4$$ factors into $12$ linear factors that are three distinct polynomials each occurring with multiplicity $4$.

Modified approach using cyclotomic polynomials

In a field of characteristic $p$, $(a-b)^{p^i} = a^{p^i} - b^{p^i}$ and so we have that $x^{12} - 1 = (x^3-1)^4$. But, $$x^3-1 = Q_1(x)Q_3(x) = (x-1)(x^2+x+1)$$ where $Q_1(x) = x-1$ and $Q_3(x) = x^2+x+1$ are cyclotomic polynomials. Also, $\mathbb F_4$ is the splitting field of $x^3-1$ since the multiplicative group $\mathbb F_4^{\times}$ is a cyclic group of order $3$, and so $x^3-1 = (x-1)(x-\alpha)(x-\beta)$ where $\alpha, \beta \in \mathbb F_4 - \mathbb F_2$. So, $x^{12}-1 = (x^3-1)^4$ factors into $12$ linear factors over $\mathbb F_4$, and these factors are three distinct polynomials each occurring with multiplicity $4$.

-
Yes, i get the same answer (different way) but the problem is that I suppose to use cyclotomic polynomials somehow to solve the problem (i don´t really see how) –  Dimitri Feb 16 '13 at 3:46
In a field of characteristic $2$, no element can have order that is an even number. Since $12$ has factors $1,2,3,4,6,12$, the only cyclotomic polynomials that we need be concerned with are $Q_1(x) = x-1$ and $Q_3(x) = x^2 + x + 1$; and $Q_3(x)$ factors into two linear factors in $\mathbb F_4$, as discussed above. –  Dilip Sarwate Feb 16 '13 at 3:54
@dilipsarwate above comment desire an upvote. It will be useful to include it into the answer proper. –  achille hui Feb 16 '13 at 4:29
Yes @DilipSarwate that cpmment was really helpul, i think that is the answer i was looking for, thanks :) –  Dimitri Feb 16 '13 at 4:36

Hint, by difference of squares:

$$X^{12}-1=(X^6-1)(X^6+1)=(X^3-1)(X^3+1)(X^6+1)$$

Now, use the formula for sum and difference of cubes, and you get two linear terms, three quadratics and a fourth degree.

Then simply check if you can factor those or not.

-

Since $\text{char}(\mathbb{F}_4) = 2$, we have $x^6 + 1 = x^6 - 1$ and $x^3 + 1 = x^3 - 1$. This means: $$x^{12} - 1 = (x^6 + 1 )(x^6 - 1) = (x^6 - 1)^2 = \left((x^3+1)(x^3-1)\right)^2 = (x^3-1)^4$$ Another way to look at this is for any finite field $F$ with $\text{char}(F) = p$, the map $$f: F \ni x \mapsto x^p \in F$$ is known to be a field automorphism (Frobenius automorphism) . This again implies: $$x^{12} - 1 = f(f(x^3)) - 1 = f(f(x^3 -1)) = (x^3-1)^4$$

Back to the factor $x^3 - 1$, for any finite group $F$, it is known that $F_\times$, the multiplicative submonoid of its non-zero elements, forms a cyclic group. Let $\omega$ be any generator for $F_\times$, then $F_\times = \{ 1, \omega, \ldots, \omega^{|F|-2} \}$ and $$x^{|F|-1} - 1 = \prod_{i=0}^{|F|-2} (x - \omega^{i})$$

Apply this to $\mathbb{F}_4$ and take any $\omega \in \mathbb{F}_4 \setminus \{ 0, 1 \}$, we have: $$(x^{12}-1) = (x^3-1)^4 = (x - 1)^4(x-\omega)^4(x-\omega^2)^4$$

-

The roots of $x^{12} -1$ are the 12-th roots of unity.

$\mathbb{F}_4$ has characteristic $2$, so the factor of $4$ is redundant; each of the cube roots of unity appears as a factor four times. The same fact could also be discovered by observing $x^{12} - 1 = (x^3)^4 - 1^4 = (x^3 - 1)^4$.

The cube roots of unity in characteristic lie in the smallest field $\mathbb{F}_{2^n}$ such that $3 \mid 2^n - 1$. That is $n=2$, so they lie in $\mathbb{F}_4$.

Therefore,

$$x^{12} - 1 = (x-1)^4 (x-\omega)^4 (x-\omega^2)^4$$

where $\omega$ is a primitive cube root of unity. Both elements of $\mathbb{F}_4 \setminus \mathbb{F}_2$ happen to be such things.

-