$\newcommand\ord{\text{ord}_n(q)}$
I've got the following formula for the $n$'th cyclotomic polynomial over the field $\mathbb{F}_q$ ($q=p^r$ and $(n,p)=1$) assuming $q\equiv1(\bmod m)$ as well as prime decompositions $n=\prod_k p_k^{e_k}$ and $m=\prod_k p_k^{f_k}$ with $e_k\geq f_k\geq1$:
$$
\Phi_n(X)=\prod_{k=1}^{\phi(m)} (X^{n/m}-\zeta_k)
$$
where the $\zeta_k$ are the primitive $m$'th roots of unity. In the case that $\ord=n/m$ then these factors are irreducible and $\phi(m)=\phi(n)/\ord$.
I'm most interested in the case $q$ is prime (i.e. how $q$ splits into prime ideals in $\mathbb{Z}[X]/\Phi_n(Z)$), but any generality beyond $r>1$ is also interesting.
For any $m$ I'd like to use this formula to write $\Phi_n$ in two-layer tree form, that is factoring it as above but further factoring each factor $X^{n/m}-\zeta_k$ as a product of the irreducibles.
Something like the below with $\Psi_k$ something like the $k$'th factor above
$$
\Phi_n(X)=\prod_{i\in G} \Psi_i(X) \\
\Psi_i(X)=\prod_{j\in H} (X^{\ord}-\zeta^{ij})
$$
where $\zeta$ is a primitive $n/(\ord)$'th root of unity and $G$ and $H$ are indexing sets, preferably groups.
For example, I suspect $G$ could be $\mathbb{Z}_n^\times/\left<m+1\right>$ and $H$ could be $\left<m\cdot\ord+1\right>$ ($\left<\cdot\right>$ wrt $\mathbb{Z}_n^\times$) but I struggle to prove it.
How could I approach this? What are suitable $G$ and $H$?
Best Answer
$\newcommand\ord{\text{ord}_n(p)}$ $\newcommand\Z{\mathbb{Z}}$ $\newcommand\Q{\mathbb{Q}}$
Consider the case $q=p$, and let $m$ as above be a divisor of $\ord$. I posted the question, and I'm considering this factorization of $\Phi_n$ in order to consider how the ring $\Z_p/(\Phi_n(X))$ factors into a direct product of smaller rings. So really I'm interested in how the ideal $(\Phi_n(X))$ factors into larger ideals, and I will use parentheses to reflect this perspective.
Letting $\zeta$ be a primitive $(r:=n/\ord)$'th root of unity in the group $\Z_p^\times$, one may show $\eta:=\zeta^{r/m}$ is a primitive $m$'th root of unity in the same group.
Let $\Psi_i(X)=X^{n/m}-\eta^i$, let $G=\Z_n^\times/S_m$ and let $H=S_m/S_r$ where $S_x:=\{y\in{\Z_n^\times}\mid y\equiv 1(\bmod x)\}$ is the subgroup of $\Z_n^\times$ fixing the primitive $x$'th roots of unity. ($S_r$ is in fact the Galois group of the finite field $\Z_p[X]/(X^{\ord}-\zeta)$ and is therefore generated by $p$). Then we may write $$ (\Phi_n(X)) = \prod_{i\in\Z_n^\times/S_m} (\Psi_i(X)) = \prod_{i\in\Z_n^\times/S_m} (X^{n/m}-\eta^i) \\ (\Psi_i(X)) = \prod_{j\in S_m/S_r} (X^{\ord}-\zeta^{ij}) $$
For the first equation, consider the original formula in the question, and the fact that the primitive $m$'th roots of unity may be represented as $\eta^i$ for $i\in\Z_m^\times$. Then consider the isomorphism $\Z_x^\times\cong\Z_n^\times/S_x$ (with $x:=m$) had by the First Isomorphism Theorem with respect to the homomorphism $y\to y(\bmod x):\Z_n^\times\to\Z_n^\times$.
The second equation follows from the fact that both sides of the equation have the same degree, and any root of the right side is also a root of the left side. To justify the claim of equal degree one may conclude from the isomorphism $\Z_x^\times\cong\Z_n^\times/S_x$ that $|S_x|=n/x$. To justify that a root of some factor $X^{\ord}-\zeta^{ij}$ on the right side is also a root of $X^{n/m}-\eta^i$, consider the following $$ X^{\ord}=X^{(m/m)(n/r)}=\zeta^{ij} \implies \\ X^{n/m} = \zeta^{(r/m)ij} = \eta^{ij} = \eta^i $$ where the last equality holds because $j$ is a subset of $S_m$ which by definition fixes $\eta$.
Though not mentioned in the original question, in place of using these multiplicative groups and their quotient groups to index, I'd like to use subgroups of the Galois group (and analogous quotient groups) of the $n$'th cyclotomic number field $\Q_n/\Q$.
Automorphism $\sigma_k\in\text{Gal}(\Q_n/\Q)$ for $k\in\Z_n^\times$ sends $X\to X^k$ and fixes all else. Then $\sigma_k((X^{\ell}-\alpha))=(X^{k\ell}-\alpha)=(X^{\ell}-\alpha^{1/k})$. To show equality of these ideals, first note the roots of $X^{k\ell}-\alpha$ include those of $X^{\ell}-\alpha^{1/k}$ where $1/k$ is the inverse of $k$ modulo $n$. Root containment also holds in the opposite direction since $k(1/k)=1(\bmod n)$ and $X^n=1$ since $X$ is a primitive $n$'th root of unity by the fact $\Phi_n(X)=0$. Now we may index using the analogous Galois groups $Z_n^\times\to\text{Gal}(\Q_n/\Q)$ and $S_x\to GS_x$ as $$ (\Phi_n(X)) = \prod_{\sigma\in\text{Gal}(\Q_n/\Q)/GS_m} \sigma((\Psi_i(X))) = \prod_{\sigma\in\text{Gal}(\Q_n/\Q)/GS_m} \sigma((X^{n/m}-\eta^i)) \\ (\Psi_i(X)) = \prod_{\sigma'\in GS_m/GS_r} \sigma'((X^{\ord}-\zeta)) $$ This works because despite our factors now of the form $(X^{\ell}-\alpha^{1/k})$ instead of $(X^{\ell}-\alpha^k)$ as before, we are indexing over groups and thus for every $1/k$ there is exactly one inverse $k$.