# Follow up question to finding primes $p$ such that $f(x)=x^6 - x^3 +1$ factors (in various ways) in $\mathbb{F}_p$

I asked this question yesterday, however, I am not sure how to compare the solution given on this site to the "worked example" solution as in my notes.

$\textbf{Problem Statement:}$ Let $f(x)= x^6 - x^3 +1$. Find primes $p$ with each of the following behaviors: $f$ is irreducible in $\mathbb{F}_p[x]$, $f$ factors into irreducible quadratic factors.

$\textbf{Worked Example:}$ Recognize $f(x)=x^6 - x^3 +1$ as the $18$th cyclotomic polynomial $\Phi_{18}(x)$. For a prime $p$ not dividing $18$, the roots of $\Phi_{18}(x)$, are exactly the elements of order $18$, i.e. the $18$th primitive roots mod $p$.

Thus, if $p^d-1 \equiv 0 \operatorname{mod} 18$ but no smaller exponent $d$ achieves this effect, then $\mathbb{F}_{p^d}^x$ has an element of order $18$", whose minimal polynomial divided $\Phi_{18}(x)$

I have no idea where the motivation for $p^d-1 \equiv 0 \operatorname{mod} 18$ is coming from. How is this related to the fact that the roots of $\Phi_{18}(x)$ are the $18$-th primitive roots mod $19$ ?

• tested primes up to 75, turns out: irreducible, $p \equiv 5, 11 \pmod {18};$ two cubic factors, $p \equiv 7, 13 \pmod {18};$ three quadratic factors, $p \equiv 17 \pmod {18};$ six linear factors, $p \equiv 1 \pmod {18}.$ You should try to prove all that. – Will Jagy Jul 3 '15 at 21:46

Which finite fields $GF(p^d)$ will have a primitive $18$'th root of unity, and thus a root of $\Phi_{18}(x)$? A primitive $18$'th root of unity is an element of order $18$ in the multiplicative group of the field. That group has order $p^d - 1$, and the order of any element must divide the order of the group, so $18$ must divide $p^d - 1$, i.e. you certainly need $p^d - 1 \equiv 0 \mod 18$.