Degrees of the irreducible factors of $X^{13}-1$

Question

I need some hints to determine the degrees of irreducible factors of $X^{13}-1$ in $\Bbb F_5[X]$. I know the first factor is $X-1$ and it is a single root. There are not other roots. I also checked from Mathematica that $1+X+ \dots X^{12}$ is not irreducible in $\Bbb F_5[X]$ but I lack proper argument to show it.

I know by Mathematica that $X^{13}-1$ can be factored as $$(X+4) \left(X^4+X^3+4 X^2+X+1\right) \left(X^4+2 X^3+X^2+2 X+1\right) \left(X^4+3 X^3+3 X+1\right)$$ How do I determine the degrees without Mathematica?

Answer 1

We know that $X^{5^n} - X$ is the product of all irreducible polynomials over $\mathbb{F}_5$ whose degree divides $n$. You can compute

$$\mathrm{gcd}(X^{13} - 1, X^5 - X) = X - 1,$$ $$\mathrm{gcd}(X^{13} - 1, X^{25} - X) = X - 1,$$ $$\mathrm{gcd}(X^{13} - 1, X^{625} - X) = X^{13} - 1$$ with the Euclidean algorithm and immediately read off that $X^{13} - 1$ has one factors of degree $1$, no factors of degree $2$ and $\frac{12}{4} = 3$ factors of degree $4$.

The fact that $X^{13} - 1$ divides $X^{625} - X$ mod $5$ is because $13 \mid 624$, as suggested in the comments.

Answer 2

Since the question is about working without Mathematica, I think the most natural theoretical approach is via Galois theory of finite fields. Over the prime field $\mathbf F_p$, the extension $\mathbf F_{p^n}$ is galois of degree $n$, with cyclic Galois group generated by the Frobenius automorphism $\phi$ defined by $\phi(x)=x^p$. As pointed out by @DanielSchepler, the subextensions of $\mathbf F_p{^n}/\mathbf F_p$ will be exactly the $\mathbf F_{p^d}$, for all $d$ dividing $n$. Here we have only a chain of two successive quadratic extensions $\mathbf F_5 \subset \mathbf F_{5^2}\subset \mathbf F_{5^4}$. To compute the irreducible factors of $X^{13} - 1/X-1$, mimicking the process over $\mathbf Q$, let us determine the orbits under $\phi$ of the primitive $13$-th roots of $1$.

Fix such a primitive root $w$. Its orbit will be $w\to w^5\to w^{5^2}= w^{-1} \to w^{-5} \to w$, and similarly for the orbits of $w^2$ and $w^3$. Note that there are only 3 orbits, since to each one will correspond an irreducible polynomial of degree 4, e.g. $(X-w)(X-w^{-1})(X-w^5)(X-w^{-5})$. Note that we regrouped the 2 first (resp. last) factors because they are in the same orbit under $\phi^2$. To go further than @user463109, it remains to develop the above product using the symmetric functions of its roots. I guess that it's here that Mathematica performs its magic.