The $n$th cyclotomic polynomial remains irreducible when reduced modulo $p$ if and only if $p$ is a generator of $\mathbb{Z}_n^\times$. Suppose that is not the case, and I know that the polynomial can be factored over $\mathbb{F}_p$. What can I say about the degrees of the irreducible factors?
For example, the 13th cyclotomic polynomial is reducible modulo 3, since $3^3 \equiv 1$ modulo 13. A (long, tedious) factorisation attempt reveals that there are four cubic irreducible factors. Should I have known this a priori?
Let $p\nmid n$. Then the cyclotomic polynomial $\Phi_n$ factors over $\Bbb F_p$ into $\phi(n)/r$ irreducible factors each of degree $r$, where $r$ is the multiplicative order of $p$ modulo $n$.
To see this, consider a primitive $n$-th root of unity $\zeta$ in an extension of $\Bbb F_p$. The number of conjugates of $\zeta$ over $\Bbb F_p$ is the least positive integer $r$ with $\zeta^{p^r}=\zeta$, that is $p^r\equiv1\pmod n$.