4

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?

Yuugi
  • 2,143

3 Answers3

4

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.

Jack D'Aurizio
  • 353,855
  • 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 03 '15 at 02: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 03 '15 at 02:24
  • Got it. Thank you!! ( I did not know that fact about primitive roots of unity) – Yuugi Jul 03 '15 at 02:32
1

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

Rory Daulton
  • 32,288
0

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

lhf
  • 216,483
  • 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 03 '15 at 01:48
  • Well, it's mod $18$ in the exponent, because $( \mathbb{F}p )^x \cong C{18}$. – lhf Jul 03 '15 at 01: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 03 '15 at 01:53