# 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?

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.

• 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 ? – Yuugi Jul 3 '15 at 2:20
• @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}}^*$. – Jack D'Aurizio Jul 3 '15 at 2:24
• Got it. Thank you!! ( I did not know that fact about primitive roots of unity) – 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

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

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

• 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? – Yuugi Jul 3 '15 at 1:48
• Well, it's mod $18$ in the exponent, because $( \mathbb{F}_p )^x \cong C_{18}$. – lhf Jul 3 '15 at 1:52
• I'm not exactly sure what means $\operatorname{mod} 18$ in the exponent. I'm mostly confused because $15^{18}= 9 \operatorname{mod} 18$ – Yuugi Jul 3 '15 at 1:53