Prime Cyclotomic Polynomials Modulo p (12.2.20)

Dummit and Foote Abstract Algebra, section 12.2, exercise 20:

Let $n$ be prime, and let $Φ_n(x) = \dfrac{x^n-1}{x-1} = x^{n-1}+...+1$ be the $n^{th}$ cyclotomic polynomial, which is irreducible over $\mathbb{Q}$. Fix a prime $p$. This exercise determines when $Φ_n(x)∈\mathbb{F}_p[x]$ is irreducible and thus provides information about the conjugacy classes of matrices of prime order over prime fields.

(a) Let $p = n$. Show $x-1$ divides $Φ_n(x)$.
(b) Let $p \neq n$. Let $f$ be the multiplicative order of $p$ in $\mathbb{F}_n^\times$. Show that $m=f$ is the smallest integer for which $\text{GL}_m(\mathbb{F}_p)$ contains a matrix $A$ of order $n$.
(c) Show that no polynomial in $\mathbb{F}_p[x]$ of degree less than $f$ divides $Φ_n(x)$, and that $m_A(x)$ is an irreducible polynomial of degree $f$ dividing $Φ_n(x)$.
(d) In particular, prove $Φ_n(x)$ is irreducible over $\mathbb{F}_p$ if and only if $p$ is a primitive root modulo $n$, i.e. $p$ generates $\mathbb{F}_n$.

Proof: (a) Since $Φ_n(1)≡0$, $x-1$ divides $Φ_n(x)$.

(b) We have $|GL_m(\mathbb{F}_p)|=(p^m-1)...(p^m-p^{m-1})$. By Lagrange's and Cauchy's theorems, $GL_m(\mathbb{F}_p)$ has a matrix of order $p$ if and only if its order is divisible by $p$, so - since $\mathbb{F}_p$ is an integral domain - if and only if $n \mid p^m-p^k=p^k(p^{m-k}-1)$ for some $0≤k≤m$. Since this first occurs when $m=f$ and $k=0$, the claim is proven.

(c) Assuming $g(x)~|~Φ_n(x)~|~x^n-1$ implies $m_B(x)~|~c_B(x) = g(x)~|~x^n-1$ where $B$ is the companion matrix of $g(x)$. Thus $B^n=1$ and by (b) $g(x)$ is of degree $≥f$. Letting $A$ be as in (b) we see $m_A(x)~|~x^n-1=(x-1)Φ_n(x)$ and by the restriction of polynomials dividing $Φ_n(x)$ and the size of $A$ we have $m_A(x)$ is of degree $f$. Since $m_A(x)$ is a monomial of minimal degree dividing $Φ_n(x)$ it must be irreducible, and since $A \neq 1$ we have $m_A(x) \neq x-1$ and now $m_A(x)~|~Φ_n(x)$.

(d) The case is clear when $p=n$. Otherwise, let $p$ be a primitive root. Then $f=n-1$ and no polynomial of degree smaller than $n-1$ divides $Φ_n(x)$, and thus $Φ_n(x)$ is irreducible. If $Φ_n(x)$ is irreducible, then a polynomial of degree smaller than $n-1$ divides $Φ_n(x)$ and thus the order of $p$ in $\mathbb{F}_n$ is smaller than $n-1$.$~\square$