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?


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.

  • $\begingroup$ The book I am using does not discuss primitive roots of unity (the book is a collection of notes). Anyway, I am having a hard time following that any eighteenth primitive root of unity belongs to $\mathbb{F}_q^x$. What exactly do you mean by "any" ? And how do you know they are as in the form given ? $\endgroup$ – Yuugi Jul 3 '15 at 2:20
  • $\begingroup$ @Yuugi: if $\eta$ and $\xi$ are two different primitive $18$-th roots of unity, then $\eta=\xi^n$ for some $n$ such that $\gcd(n,18)=1$. The group of primitive $18$-th roots of unity is isomorphic to $\mathbb{Z}_{/18\mathbb{Z}}^*$. $\endgroup$ – Jack D'Aurizio Jul 3 '15 at 2:24
  • $\begingroup$ Got it. Thank you!! ( I did not know that fact about primitive roots of unity) $\endgroup$ – Yuugi Jul 3 '15 at 2:32

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


The theory of polynomials over a field show that your polynomial factors into


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.)


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$.

  • $\begingroup$ The statement 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$ makes me believe that I should be using $\operatorname{mod} 18$. Why is this incorrect? What am I misreading in the statement? $\endgroup$ – Yuugi Jul 3 '15 at 1:48
  • $\begingroup$ Well, it's mod $18$ in the exponent, because $( \mathbb{F}_p )^x \cong C_{18}$. $\endgroup$ – lhf Jul 3 '15 at 1:52
  • $\begingroup$ I'm not exactly sure what means $\operatorname{mod} 18$ in the exponent. I'm mostly confused because $15^{18}= 9 \operatorname{mod} 18$ $\endgroup$ – Yuugi Jul 3 '15 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.