I am trying to fully understand this particular case of cyclotomic polynomials. Given the cyclotomic polynomials $\phi(x) = x^n+1$, where $n$ is a power of $2$, I want to understand how this polynomial works being the quotient of $\mathbb{Z}_q[x]$, where $q$ is a prime number. Equivalently, how $R_q = \mathbb{Z}_q[x]/\langle x^n+1 \rangle$ works when $n$ is a power of $2$.
In particular:
- Is $R_q$ a field? Equivalently, when $x^{2^{\kappa}}+1$ is irreducible over $\mathbb{Z}_q$ with $\kappa \geq 1$ (should it be $\kappa \geq 2$?). I assume it never happens since we refer to $R_q$ as a ring.
- Are this cyclotomic polynomials irreducible over $\mathbb{Z}$? Anyways, as $\mathbb{Z}$ is not a field, the quotient $\mathbb{Z}[x]/\langle x^n+1 \rangle$ can not be a field even if $x^{2^{\kappa}}+1$ is irreducible over $\mathbb{Z}$.
Best Answer
(Small note: it's a standard convention that $q$ denotes a prime power so I'll write $p$ for the prime.)
All of the cyclotomic polynomials are irreducible over $\mathbb{Z}$.
The factorization of cyclotomic polynomials over $\mathbb{F}_p$ (and even over $\mathbb{F}_q$) can be completely understood by considering the action of the Frobenius map $x \mapsto x^p$ on their roots. In general, the irreducible factors of a polynomial over $\mathbb{F}_p$ correspond precisely to orbits of the Frobenius map acting on its roots over a splitting field (exercise). For cyclotomic polynomials $\Phi_n(x)$ we can be really explicit about the action of the Frobenius map because it sends a primitive $n^{th}$ root of unity $\zeta_n$ to $\zeta_n^p$. The degree of the irreducible factor containing $\zeta_n$ (equivalently, degree of the minimal polynomial of $\zeta_n$) is then the smallest $k$ such that $\zeta_n^{p^k} = \zeta_n$, hence the smallest $k$ such that
$$p^k \equiv 1 \bmod n.$$
This is exactly the multiplicative order $\text{ord}_n(p)$ of $p \bmod n$.
(This whole discussion requires that $\gcd(n, p) = 1$. If $p \mid n$ then $\Phi_n(x) \bmod p$ has repeated roots.)
If we now specialize to $n = 2^m$ a power of two, so that $\Phi_{2^m}(x) = x^{2^{m-1}} + 1$, we get the following:
The case $p = 2$ has to be handled separately but in that case $\Phi_{2^m}(x) = (x + 1)^{2^{m-1}}$. It follows that $\mathbb{F}_p[x]/\Phi_{2^m}(x)$ is a field iff either $m = 1$, or $m = 2$ and $p \equiv 3 \bmod 4$.
It's a little surprising that irreducible polynomials which are reducible $\bmod p$ for every prime $p$ exist, and $\Phi_8(x) = x^4 + 1$ is in some sense a minimal example of such a polynomial (in particular it has minimal degree; this is impossible for a quadratic or a cubic polynomial). You can check using WolframAlpha, for example, that
$$x^4 + 1 \equiv (x^2 + x - 1)(x^2 - x - 1) \bmod 3$$ $$x^4 + 1 \equiv (x^2 + 2)(x^2 - 2) \bmod 5$$ $$x^4 + 1 \equiv (x^2 + 3x + 1)(x^2 - 3x + 1) \bmod 7$$ $$x^4 + 1 \equiv (x^2 + 3x - 1)(x^2 - 3x - 1) \bmod 11$$ $$x^4 + 1 \equiv (x^2 + 5)(x^2 - 5) \bmod 13$$ $$x^4 + 1 \equiv (x + 2)(x - 2)(x + 8)(x - 8) \bmod 17$$
and so forth. In general there are four different patterns of factorization $\bmod p$ depending on the value of $p \bmod 8$:
If $p \equiv 1 \bmod 8$, then $\zeta_8^p = \zeta_8$ so $x^4 + 1$ splits into linear factors
$$(x - \zeta_8)(x - \zeta_8^3)(x - \zeta_8^{-3})(x - \zeta_8^{-1}).$$
This also happens for $p = 2$ but the argument is easier: $x^4 + 1 \equiv (x + 1)^4 \bmod 2$.
If $p \equiv 3 \bmod 8$ then $\zeta_8^p = \zeta_8^3 \neq \zeta_8$ but $\zeta_8^{p^2} = \zeta_8^9 = \zeta_8$ so $x^4 + 1$ splits into quadratic factors
$$(x - \zeta_8)(x - \zeta_8^3), (x - \zeta_8^{-3})(x - \zeta_8^{-1})$$
with constant terms $\zeta_8^4 = \zeta_8^{-4} = -1$. The linear terms turn out to be the two square roots of $-2$ (and you can check this by squaring them); this reflects the identity
$$x^4 + 1 = (x^2 - 1)^2 + 2x^2 = (x^2 + \sqrt{-2} x - 1)(x^2 - \sqrt{-2} x - 1)$$
over $\mathbb{Q}[\sqrt{-2}]$ which is one of the three quadratic subfields of $\mathbb{Q}(\zeta_8)$.
If $p \equiv -3 \bmod 8$ then $\zeta_8^p = \zeta_8^{-3} \neq \zeta_8$ but $\zeta_8^{p^2} = \zeta_8^9 = \zeta_8$ so $x^4 + 1$ splits into quadratic factors
$$(x - \zeta_8)(x - \zeta_8^{-3}), (x - \zeta_8^3)(x - \zeta_8^{-1})$$
with constant terms $\zeta_8^{-2} = \zeta_4^{-1}$ and $\zeta_8^2 = \zeta_4$ the two primitive $4^{th}$ roots of unity. The linear terms both vanish since $\zeta_8^4 = -1$; this reflects the identity
$$x^4 + 1 = (x^2 + i)(x^2 - i)$$
over $\mathbb{Q}(i)$, another one of the three quadratic subfields of $\mathbb{Q}(\zeta_8)$.
Finally, if $p \equiv -1 \bmod 8$ then $\zeta_8^p = \zeta_8^{-1} \neq \zeta_8$ but $\zeta_8^{p^2} = \zeta_8$ so $x^4 + 1$ splits into quadratic factors
$$(x - \zeta_8)(x - \zeta_8^{-1}), (x - \zeta_8^3)(x - \zeta_8^{-3})$$
with constant terms $1$. The linear terms turn out to be the two square roots of $2$ (you can again check this by squaring them); this reflects the identity
$$x^4 + 1 = (x^2 + 1)^2 - 2x^2 = (x^2 + \sqrt{2} x + 1)(x^2 - \sqrt{2} x + 1)$$
over $\mathbb{Q}(\sqrt{2})$, the final quadratic subfield of $\mathbb{Q}(\zeta_8)$.
Altogether the phenomena happening here for $x^4 + 1$ reflect three special cases of quadratic reciprocity (and these special cases can actually be proven this way), and one way to think about what's going on instead of using the Frobenius map is to argue that $\left( \frac{-1}{p} \right) \left( \frac{2}{p} \right) = \left( \frac{-2}{p} \right)$ which means at least one of $-1, 2, -2$ must always be a quadratic residue $\bmod p$, each of which leads to one of the three quadratic patterns of factorization above.