# Factorize $x^8-x$ over $F_3$ and $F_{81}$

Consider the polynomial $p(x)=x^8-x$ in $F_3$:

(a) find the splitting field of $p$ over $F_3$ and factorize $p$ over $F_3$

(b) factorize p over $F_{81}$

(a) If the roots of $p$ are all distinct, we need a field extension of $F_3$ with at least $8$ elements, the smallest one is $F_9$, but does it contain all the roots of $p$ ?

$p(x)=x(x^7-1)=x(x+2)(x^6+x^5+x^4+x^3+x^2+x+1)$ since $1$ is a root of $p$ and $x^7-1$ is divided by $x-1\equiv x+2$ (using Ruffini's rule).

The sextic polynomial has no roots on $F_3$, so the possibile factors are three of deg 2, one of deg 2 and one of deg 4, two of deg 3. How to show if it is irreducible or not? On $F_2$ is easy to show that it is reducible since there is only one quadratic irreducibile polynomial, and two cubic irreducible polynomials.

It is correct to say that it is irreducible in this way: the multiplicative order of $3$ modulo $7$ is $6$, so there is at least one cyclotomic coset of cardinality $6$ that correspondes to that sixtic polynomial, and so it is irreducible, otherwise the multiplicative order should be less than $6$.

If the sextic polynomial is irreducible then the splitting field of $p$ over $F_3$ would be $F_{3^6}$.

(b) how to proceed ?

• Any thoughts about the order of a non-trivial $7^{th}$ order root of unity in $\mathbf F_{3^n}$ ? – random Jul 6 '18 at 11:49
• Maybe the order divides $3^n-1$ – sound wave Jul 6 '18 at 12:00

The question is really about the factorization of the seventh cyclotomic polynomial $$\Phi_7(x)=1+x+x^2+x^3+x^4+x^5+x^6.$$ Its zeros have multiplicative order seven. So they reside in an extension field $$\Bbb{F}_{3^n}$$ such that $$7\mid 3^n-1$$. Because $$3$$ is a primitive root modulo $$7$$ the smallest $$n$$ satisfying this is $$n=6$$.

Consequently

• $$\Phi_7(x)$$ is irreducible in $$\Bbb{F}_3[x]$$.
• Because $$\operatorname{lcm}(6,4)=12$$ the field $$\Bbb{F}_{81}(\alpha)$$ where $$\alpha$$ is any root of $$\Phi_7(x)$$ is the field $$\Bbb{F}_{3^{12}}$$. Anyway, the minimal polynomial of $$\alpha$$ over $$\Bbb{F}_{81}$$ has degree $$12/4=3.$$ The conclusion is that over $$\Bbb{F}_{81}$$ the polynomial $$\Phi_7(x)$$ factors as a product of two cubics.

As $$81\equiv4\pmod7$$ the Galois conjugates of $$\alpha$$ over $$\Bbb{F}_{81}$$ are $$\alpha,\alpha^4$$ and $$\alpha^{16}=\alpha^2$$. $$4^3\equiv1\pmod7$$ so it ends at that point (confirming the above observation that the minimal polynomial must be cubic). The factors are $$p_1(x)=(x-\alpha)(x-\alpha^2)(x-\alpha^4)$$ and its reciprocal polynomial $$p_2(x)=(x-\alpha^3)(x-\alpha^5)(x-\alpha^6).$$ Because $$\alpha^7=1$$ we see that both have constant terms equal to $$-1$$. The other coefficients belong to the intermediate field $$\Bbb{F}_9$$. More precisely, the calculation from here shows that the sum $$S=\alpha+\alpha^2+\alpha^4$$ satisfies the equation $$S^2+S+2=0$$. In other words $$S=(-1\pm\sqrt{-7})/2=(-1\pm i)/2$$, where $$i$$ is a root of $$x^2+1$$ in $$\Bbb{F}_9$$. The sign depends on the explicit choice of $$\alpha$$, meaning that one sign applies to $$p_1(x)$$ and the other to $$p_2(x)$$. The coefficient of $$x^2$$ in $$p_1(x)$$ (resp. $$p_2(x)$$) is $$-S$$. The coefficient of the linear term of $$p_1(x)$$ is $$\alpha^3+\alpha^5+\alpha^6=-1-S.$$ In other words $$p_{1,2}(x)=x^3-Sx^2-(1+S)x-1$$ with the choice of conjugate values of $$S$$ is used in $$p_1$$ or $$p_2$$ respectively. Observe that in characteristic three we have $$2=-1$$, so $$S=1\mp i$$.

• Jyrki, can you elaborate on Consequently $\Phi_7(x)$ is irreducible in $\mathbb F_3[x]$? I see why the polynomial can't have a root in $\mathbb F_3$, but not immediately why it is irreducible. – mathcounterexamples.net Jul 6 '18 at 12:27
• @mathcounterexamples.net Because $7\mid 3^n-1$ does not hold when $n<6$ but $3\mid 3^6-1$, we see that the extension $\Bbb{F}_3(\alpha)/\Bbb{F}_3$ must be of degree six. Therefore its minimal polynomial has degree six also. The minimal polynomial is irreducible, and a factor of $\Phi_7(x)$, so... – Jyrki Lahtonen Jul 6 '18 at 12:30
• Capito! Understand! Compris! – mathcounterexamples.net Jul 6 '18 at 12:34
• Should read $7\mid 3^6-1$, of course (two comments up). – Jyrki Lahtonen Jul 6 '18 at 12:57