Factoring Cyclotomic Polynomials Over $\mathbb{F}_p$. How can I show that the irreducible factors of the cyclotomic polynomial $\Phi_{p^d-1}(x)$ all have degree $d$ over $\mathbb{F}_p[x]$? I'm particularly interested in a proof using the fact that for prime $p\nmid mn$ we have $\Phi_m(x)$ and $\Phi_n(x)$ are coprime over $\mathbb{F}_p[x]$, where $m\neq n$.
 A: We'll need a couple intermediate lemmas first.
Lemma 1: If $p$ is a prime such that $p\nmid mn$, $m\neq n$, then $\Phi_m(x)$ and $\Phi_n(x)$ are coprime over $\mathbf{F}_p[x]$.
Proof: Suppose $\gcd(\Phi_m(x), \Phi_n(x))=g$ (over $\mathbf{F}_p[x]$). We have $x^{mn}-1=\prod_{d|mn}\Phi_d(x)$, so $\Phi_m(x)|x^{mn}-1$ and $\Phi_n(x)|x^{mn}-1$. Thus, $g^2|x^{mn}-1$. By considering formal derivatives, $x^{mn}-1$ has no repeated roots over $\mathbf{F}_p$ since $p\nmid mn$, so we must have $g=1$. $\Box$
Lemma 2:  $\Phi_n(\alpha)\equiv 0\pmod{p} \iff o_p(\alpha)=n$, where $\gcd(p,n)=1$.
Proof: By induction: $\Phi_1(x)=x-1$ has roots at $x\equiv 1\pmod{p}$. Suppose the lemma holds for all $k<n$. Set $\Phi_n(\alpha)\equiv 0\pmod{p}$, and suppose for the sake of contradiction that $o_p(\alpha)=k\neq n$. By induction, $\Phi_k(\alpha)\equiv 0\pmod{p}$, so $\Phi_k(\alpha)\equiv\Phi_n(\alpha)\equiv 0\pmod{p}$, contradiction by Lemma 1. Now, if $o_p(\alpha)=n$, we have $\alpha^n-1=0$, so $\alpha$ is a root of some $\Phi_k(x)$, $k|n$. By induction, $\alpha$ is a root of $\Phi_n(x)$ over $\mathbf{F}_p$, done. $\Box$
Now, consider the linear factors $(x-\xi)$ of $\Phi_{p^d-1}(x)$ in a sufficiently large extension of $\mathbf{F}_p$. Clearly, $p\nmid p^d-1$, so there are no repeated factors (again, consider formal derivatives). The multiplicative group $\mathbf{F}_{p^d}^{\times}$ is cyclic, and in fact there are $\varphi(p^d-1)$ elements with order $p^d-1$, which by Lemma 2 are roots of $\Phi_{p^d-1}(x)$. We have $\deg(\Phi_{p^d-1}(x))=\varphi(p^d-1)$, so these are exclusively the roots.Now, no subfield $\mathbf{F}_{p^e}\subset\mathbf{F}_{p^d}$ contains any elements with order $p^d-1$, since $e|d$ and $|\mathbf{F}_{p^e}^{\times}|=p^e-1<p^d-1$. Therefore, for any linear factor $x-\xi$ of $\Phi_{p^d-1}(x)$, we have $[\mathbf{F}_p(\xi):\mathbf{F}_p]=d$, so the minimal polynomial $m(x)$ of $\xi$ over $\mathbf{F}_p$ has degree $d$.
Now, we claim that $m(x)|\Phi_{p^d-1}(x)$. Let $\Phi_{p^d-1}(x)=m(x)q(x)+r(x)$, $q, r\in\mathbf{F}_p[x]$, $\deg(r)<\deg(m)$. We have $r(\xi)=0$, but since $m(x)$ is the minimal polynomial of $\xi$ over $\mathbf{F}_p$, we must have $r(x)=0\implies m(x)|\Phi_{p^d-1}(x)$.
Therefore, any linear factor of $\Phi_{p^d-1}(x)$ over a field extension of $\mathbf{F}_p$ is a factor of a degree $d$ irreducible in $\mathbf{F}_p[x]$, and the desired conclusion follows.
