Are cyclotomic polynomials irreducible modulo a prime?

Question

I am actually interested on cyclotomic polynomials of the form $x^n+1$ (i.e. $n$ is a power of 2, for large $n$).

Are these polynomials irreducible modulo a prime $q$? I already saw that $X^2+1$ is not irreducible modulo 5 because $Z_5$ contains roots of -1. What about $x^{512}-1$? Is there a general criterion?

Thanks

Answer 1

For any $n \in \mathbb{N}$ and $p$ a prime that does not divide $n$,

$$ \Phi_n(x) \text{ is irreducible in } \mathbb{Z}_p \iff p \text{ is a primitive root modulo } n$$

Wikipedia article: Primitive root modulo n.

For powers of $2$, only $2$ and $4$ have primitive roots. Primitive roots modulo $n$ correspond to generators of $\mathbb{Z}_n^*$. For $n=2^k$ and $k\geq 3$, $\mathbb{Z}_n^*$ is not cyclic and thus there are no primitive roots modulo $n$.

Thus for higher powers of $2$, the cyclotomic polynomial will be reducible modulo any odd prime.

Answer 2

I find this relatively general answer from the Finite Field book by Rudolf, theorem 2.47, helpful:

The cyclotomic field $K^{(n)}$ is a simple algebraic extension of $K$. If $K=\mathbb{F}_q$ with $\gcd(q,n)=1$, then the cyclotomic polynomial $Q_n$ factors into $\phi(n)/d$ distinct monic irreducible polynomials in $K[x]$ of the same degree $d$. Here $d$ is the least positive integer such that $q^d \equiv 1 \mod n$.