# Irreducible cyclotomic polynomial

I want to know if there is a way to decide if a cyclotomic polynomial is irreducible over a field $\mathbb{F}_q$?

#### Solutions Collecting From Web of "Irreducible cyclotomic polynomial"

Yes there is. The $n^{th}$ cyclotomic polynomial $\Phi_n(x)\in\mathbb{Z}[x]$ will remain irreducible (after reduction mod $p$) in $\mathbb{F}_q[x]$ if and only if the residue class of $q$ generates the multiplicative group $\mathbb{Z}_n^*$ of residue classes coprime to $n$.

This is because if $z$ is a root of $\Phi_n(x)$ in an extension of $\mathbb{F}_q$, then its conjugates are $z^q, z^{q^2},$ et cetera. If you get the same number of conjugates as you would get over $\mathbb{Q}$, then you are done. But over $\mathbb{Q}$ the conjugates are exactly $z^a, \gcd(a,n)=1, 1\le a<n$.

More details. Let $z$ be a primitive $n^{th}$ root of unity in an extension $\mathbb{F}_q$. Let $\mathbb{F}_q[z]=\mathbb{F}_{q^k}$. Because the multiplicative group
of $\mathbb{F}_{q^k}$ is cyclic of order $q^k-1$, we know that $k$ is the smallest positive integer with the property that $n\mid q^k-1$. By the Galois theory of finite fields the minimal polynomial of $z$ is
$$m(x)=(x-z)(x-z^q)(x-z^{q^2})\cdots(x-z^{q^{k-1}}).$$
This will always be a factor of the cyclotomic polynomial $\Phi_n(x)$. The roots of the latter are $z^a, 1\le a<n, \gcd(a,n)=1$. The polynomial $\Phi_n(x)$ is thus irreducible precisely when the two sets of roots are the same.

Here $z^{q^i}=z^a$ if and only if $q^\ell\equiv a\pmod{n}$. Therefore all the primitive roots $z^a$ are zeros of $m(x)$ only, if all the exponents $a$ are congruent to a power of $q$ modulo $n$.

All of the above assumed that $\gcd(n,q)=1$. Let us next consider the case, where that is not true. Here $q$ is the order of a finite field, so it is a power of a prime number $p$.
Therefore $\gcd(n,p)>1$ if and only if $p\mid n$, so we can write $n=mp^\ell$ for some integer $\ell\ge1$, $m$ coprime to $p$. Then we have in the ring $\mathbb{F}_p[x]$ the factorization
$$x^n-1=(x^m-1)^{p^a}$$
as a consequence of Freshman’s dream:
$$(a+b)^p=a^p+b^p.$$
Therefore all the roots of $\Phi_n(x)$ in $\overline{\mathbb{F}_q}$ are actually roots of $x^m-1$ as well. Hence any one of them has at most $\phi(m)<\phi(n)$ conjugates. Therefore $\Phi_n(x)$ cannot be irreducible in $\mathbb{F}_q[x]$.