## The smallest degree of a factor of a cyclotomic polynomial mod a prime

Let $\ell$ be a prime and let $\Phi_\ell(x) = \dfrac{x^\ell-1}{x-1} \in \mathbb{Z}[x]$ be the $\ell$th cyclotomic polynomial. In this exercise, we will determine the smallest degree of a factor of $\Phi_\ell$ mod $p$, and in particular determine when $\Phi_\ell$ is irreducible mod $p$. (Recall that $\Phi_\ell$ is irreducible over $\mathbb{Q}$ by Eisenstein’s criterion.)

1. Show that if $p = \ell$ then $\Phi_\ell$ is divisible by $x-1$ in $\mathbb{F}_\ell[x]$.
2. Suppose $p \neq \ell$ and let $f$ denote the order of $p$ in $\mathbb{F}_\ell^\times$ (that is, $f$ is minimal such that $p^f \equiv 1$ mod \ell\$). Show that $f$ is minimal such that $\mathsf{GL}_f(\mathbb{F}_p)$ contains an element $A$ of order $\ell$.
3. Show that $\Phi_\ell$ is not divisible by any polynomial of degree smaller than $f$ in $\mathbb{F}_p[x]$. Let $m_A(x) \in \mathbb{F}_p[x]$ denote the minimal polynomial for a matrix $A$ as in (2) and conclude that $m_A(x)$ is irreducible of degree $f$ and divides $\Phi_\ell(x)$ in $\mathbb{F}_p[x]$.
4. Prove that $\Phi_\ell(x)$ is irreducible mod $p$ if and only if $\ell-1$ is the smallest power of $p$ which is congruent to 1 mod $\ell$; that is, $p$ is a primitive root mod $\ell$.

1. As we showed in this previous exercise, $(x-1)^\ell = x^\ell - 1$ in $\mathbb{F}_\ell[x]$. So we have $\Phi_\ell(x) = (x-1)^{\ell-1}$.
2. Suppose $f$ is the order of $p$ mod $\ell$. Recall that $|\mathsf{GL}_f(\mathbb{F}_p)| = \prod_{i=1}^f (p^f - p^{f-i})$. In particular, $|\mathsf{GL}_f(\mathbb{F}_p)| \equiv 0$ mod $\ell$ since $p^f - 1 \equiv 0$. By Cauchy’s Theorem, there exists an element $A$ of order $\ell$ in $\mathsf{GL}_f(\mathbb{F}_p)$.

Now suppose $\mathsf{GL}_m(\mathbb{F}_p)$ has an element $A$ of order $\ell$. Then we have $\prod_{i=1}^m (p^m - p^{m-i}) \equiv 0$ mod $\ell$, and so $p^m - p^{m-i} \equiv 0$ mod $\ell$ for some $i$. Then $p^i \equiv 0$ mod $\ell$. If $m < f$, we have a contradiction, since $f$ is minimal such that $p^f \equiv 1$ mod $\ell$.

3. Suppose $\Phi_\ell(x)$ is divisible by a polynomial $q(x)$ of degree $m < f$ over $\mathbb{F}_p$. Then the companion matrix of $q$ has dimension $m < f$ and satisfies $x^\ell - 1 = 0$. This contradicts (2), which showed that $f$ is minimal such that $\mathsf{GL}_f(\mathbb{F}_p)$ contains an element of order $\ell$.

Now let $m_A(x)$ be the minimal polynomial of the matrix $A$ of order $\ell$ in $\mathsf{GL}_f(\mathbb{F}_p)$. The degree of $m_A$ is at least $f$, by the first paragraph of (3). Moreover the degree of $m_A$ is at most $f$, since the characteristic polynomial of $A$ has degree $f$. So the degree of $m_A$ is exactly $f$. Moreover, $m_A$ must be irreducible, since any proper divisor of $m_A$ also divides $\Phi_\ell(x)$ over $\mathbb{F}_p$ and has degree less than $f$.

4. By part (3), the smallest degree of a (nonunit) divisor of $\Phi_\ell(x)$ over $\mathbb{F}_p$ is precisely the order of $p$ mod $\ell$. So $\Phi_\ell$ is irreducible over $\mathbb{F}_p$ if and only if the order of $p$ mod $\ell$ is $\ell-1$; that is, if $p$ is a generator of $\mathbb{F}_\ell$ or a primitive $\ell$th root of 1.