Find a prime $p$ such that $f(x)=x^6 - x^3 +1$ factors in to linear factors in $\mathbb{F}_p[x]$ Find a prime $p$ such that $f(x)=x^6 - x^3 +1$ factors in to linear factors in $\mathbb{F}_p[x]$
$\textbf{My attempt:}$ 
Notice that $f(x)$ is the $18$-th cyclotomic polynomial, $\Phi_{18}(x)$. For a prime, $p$, which does not divide $18$, the roots of $\Phi_{18}(x)$ are exactly the elements $\alpha \in \mathbb{F}_p$ such that $\alpha^{18} = 1$ in $( \mathbb{F}_p )^x$. 
If I let $p=19$, then $(\mathbb{F}_{19})^x \cong \mathbb{Z}_{18}$, which will have an element of order $18$. And so $\Phi_{18}$ will have at least one linear factor in $\mathbb{F}_{19}$. 
However, I have so far only shown $\Phi_{18}$ has at least one linear factor, but I need to show that $\Phi_{18}$ factors in to linear factors.   How do I go on from here? 
 A: If $18$ divides the order of $\mathbb{F}_{q}^*$, there is a eigtheenth primitive root of unity $\xi$ in $\mathbb{F}_{q}^*$, so any eigtheenth primitive root of unity belongs to $\mathbb{F}_{q}^*$, since they are just
$$ \xi,\quad \xi^5,\quad \xi^7,\quad \xi^{11},\quad \xi^{13},\quad \xi^{17}.$$
This gives, for instance, that $\Phi_{18}(x)$ splits completely over $\mathbb{F}_p$ is $p\equiv 1\pmod{18}$:
$$ \Phi_{18}(x) \equiv (x - 3) (x - 2) (x + 4) (x + 5) (x + 6) (x + 9)\pmod{19},$$
$$ \Phi_{18}(x) \equiv (x - 4) (x - 3) (x + 7) (x + 9) (x + 12) (x + 16)\pmod{37},$$
$$ \Phi_{18}(x) \equiv 
(x - 36) (x - 18) (x + 2) (x + 4) (x + 16) (x + 32)\pmod{73},$$
$$ \Phi_{18}(x) \equiv (x - 43) (x - 34) (x - 4) (x + 16) (x + 27) (x + 38)\pmod{109},$$
$$\ldots $$
On the other hand, Cauchy's theorem for groups gives that $\color{red}{p\equiv 1\pmod{18}}$ is also a necessary condition, since by assuming $p\not\equiv 1\pmod{18}$ we have that there are no elements of order $18$ in $\mathbb{F}_p^*$, that is a cyclic group.
A: If you want a brute force way, you just need to find $6$ members of $\Bbb Z_{19}$ for which $f(x)=0$. Just check all $19$ values and we get
$$x\in\{2,3,10,13,14,15\}$$
The theory of polynomials over a field show that your polynomial factors into
$$f(x)=(x-2)(x-3)(x-10)(x-13)(x-14)(x-15)$$
You could always multiply this out to be sure. (I used WolframAlpha to expand that expression in the integers, and checking the modulus of each coefficient modulo $19$ I see that it works.)
A: The roots of $\Phi_{18}$ are exactly the elements that have order $18$ (not merely the ones such that $\alpha^{18} = 1$).
The first prime $p$ for which $\mathbb{F}_p^x$ has elements of order $18$ is $p=19$. In this case, each of these elements will generate $\mathbb{F}_p^x$.
So, you're seeking the primitive roots mod $19$. These are $2,3,10,13,14,15$.
