1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Will Jagy Jul 3 '15 at 21:46
1
$\begingroup$

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

$\endgroup$

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.