# Factoring $x^n - 1$ and minimal polynomials

Let $$gcd(n,q) = 1$$

I'm trying to get to grips with factorising the polynomial $$x^n - 1$$ over $$\mathbb{F}_q$$. Firstly, it is a good idea to find an extension field containing all the roots of $$x^n - 1$$; this is always possible since splitting fields always exist.

Let $$\mathbb{F}_q$$ be a finite field and define $$ord_n(q)$$ to be the smallest positive integer $$t$$ such that $$q^t \equiv 1 mod n$$.

Then $$\mathbb{F}_{q^t}$$ is the splitting field for $$x^n - 1$$ over $$\mathbb{F}_q$$, which contains a primitive $$n^{th}$$ root of unity, $$\alpha$$.

So the irreducible factors of $$x^n - 1$$ must be the product of the distinct minimal polynomials of the $$n^{th}$$ roots of unities in $$\mathbb{F}_{q^t}$$.

I have two questions;

$$(1)-$$ Why is $$\mathbb{F}_{q^t}$$ the splitting field? What is so special about this $$t = ord_n(q)$$?

$$(2)-$$ Why are the irreducible factors of $$x^n - 1$$ the product of the distinct minimal polynomials?

• See also this question. – Dietrich Burde Feb 10 at 19:57
• You want the smallest extension field containing $\alpha$, i.e. $\Bbb{F}_q(\alpha)$. This has to be one of the fields $\Bbb{F}_{q^t}$ for some $t$, because those are the only (finite) extension fields that exist. The multiplicative group of $\Bbb{F}_{q^t}$ is cyclic of order $q^t-1$. Hence it contains an element of order $n$ if and only if $n\mid q^t-1$. – Jyrki Lahtonen Feb 11 at 4:10
• You may be expected to know about the factors of $x^n-1$ over $\Bbb{Q}$. Those are called cyclotomic polynomials. They may or may not factor further ovet $\Bbb{F}_q$, see here. Even if you don't know about the cyclotomic polynomials, you can try the process described here. I'm afraid the different context may make it a bit harder to follow. – Jyrki Lahtonen Feb 11 at 4:27
• Anyway, a general fact at play is that if a polynomial $p(x)$ with coefficients in $\Bbb{F}_q$ has $\alpha$ as a root, then $\alpha^q$ will also be a root of $p(x)$. When $\alpha$ is a root of unity of a prescribed order, this leads to a complete description of the roots of the minimal polynomial of $\alpha$. For example, if $q=4$, $n=17$, Then the roots will be $\alpha,\alpha^4,\alpha^{16}=\alpha^{-1},\alpha^{-4}$. The list stops there, because $\alpha^{-16}=\alpha$, and that was already included. – Jyrki Lahtonen Feb 11 at 4:37