# When is a cyclotomic polynomial over a finite field a minimal polynomial?

When is the cyclotomic polynomial $f(x)$ over a finite field $\mathrm{F}_q$ also the minimal polynomial of some element $\alpha \in \mathrm{F}_q$?

-

In general, a polynomial $f\in F[X]$ is the minimal polynomial of its roots over $F$ if and only if $f$ is irreducible over $F$. Cyclotomic polynomials provide no exception.

However, while cyclotomic polymomials are irreducible over $\mathbb Q$, not all of them are irreducible when considered as a polynomial over a finite field. For example, over $\mathbb F_2$ the $7$th cyclotomic polynomial $\Phi_7 = X^6 + X^5 + X^4 + X^3 + X^2 + X + 1$ factors into two factors of degree $3$: $$\Phi_7 = (X^3 + X + 1)(X^3 + X^2 + 1)$$ Hence $\Phi_7\in\mathbb F_2[X]$ is not irreducible and therefore not the minimal polynomial of its roots.

Note: This was written as a response to an earlier version of the question.

-
Please explain it for the following example. Given finite field $\mathrm{F}_q$, I have a decomposition $x^n-1=\prod_{i=0}^{m-1}f_i(x)$ over $\mathrm{F}_q$, where all $f_i(x)$ are cyclotomic. I am not sure that all $f_i(x)$ are minimal polynomials for some elements from extension $[\mathrm{F}_q^r : \mathrm{F}_q]$, where $r$ is a smallest number that $n$ divides $q^r - 1$. What is wrong in that? – Piotr Semenov Oct 21 '13 at 11:41
@PiotrSemenov: I've added information on cyclotomic polynomials over finite fields to my answer. – azimut Oct 21 '13 at 11:54
Thanks! So I did a mistake while suggesting that cyclotomic polynomials are also irreducible in case of finite fields. – Piotr Semenov Oct 21 '13 at 12:18
+1: In some sense an even smaller counterexample is $$\Phi_3(X)=X^2+X+1=(X-2)(X-4)\in\Bbb{F}_7[X].$$ Or even $\Phi_3(X)=(X-1)^2\in \Bbb{F}_3[X].$ – Jyrki Lahtonen Oct 22 '13 at 7:00
@JyrkiLahtonen: That's true. For my example, I decided to go with an example over $\mathbb F_2$. Here, the smallest reducible one is $\Phi_4 = (X + 1)^2$, which might be a bit misleading. So I ended up with $\Phi_7$. – azimut Oct 22 '13 at 7:10

One can show that the cyclotomic polynomial $\Phi_n(X)$ is irreducible over $\mathbf F_p$ precisely when $p$ has multiplicative order $\varphi(n)$ modulo $n$. This follows from the theory of cyclotomic extensions of $\mathbf Q$.

In particular, if $(\mathbf Z/n\mathbf Z)^\times$ is not cyclic (i.e. unless $n$ is an odd prime power, twice an odd prime power, or $n=2$ or $4$), then $\Phi_n(X)$ is reducible modulo every prime $p$, despite being irreducible over $\mathbf Q$!

-