# Is the image of $\Phi_n(x) \in \mathbb{Z}[x]$ in $\mathbb{F}_q[x]$ still a cyclotomic polynomial?

Let $\Phi_n(x) \in \mathbb{Z}[x]$ denote the $n$-th cyclotomic polynomial, and let $\mathbb{F}_q$ be the finite field with $p^k = q$ elements ($p$ prime). Let $\Phi'_n(x)$ be the reduction of $\Phi_n(x)$ mod $p$ (i.e., $\Phi'_n(x)$ is the image of $\Phi_n(x)$ in $\mathbb{F}_q[x]$). Is it true that $\Phi'_n(x)$ is the $n$-th cyclotomic polynomial in $\mathbb{F}_q$; that is, are the roots of $\Phi_n'(x)$ precisely the primitive $n$-th roots of unity in $\mathbb{F}_q$? If so, I want to prove this is the case, but I'm not sure how I'd go about doing this.

• $\Phi'_n$ is confusing notation, it might interpreted as the derivative. – lhf Apr 8 '18 at 11:18

You need $\gcd(p,n)=1$ for otherwise there are no roots of unity of order $n$ in any field $\Bbb{F}_q,q=p^n$. Basically this is because $1$ is the only root of $x^p-1=(x-1)^p$.

But, assuming $\gcd(n,p)=1$, the claim is true. If $\alpha\in\Bbb{F}_q$ is a root of unity of order $n$ (implying $n\mid q-1$), then the powers $\alpha^k$, $0<k<n,\gcd(k,n)=1$ are also of order $n$. Therefore we can deduce that there are $\phi(n)$ such elements in $\Bbb{F}_q$. Because they all have order $n$, they are zeros of $x^n-1$, but they are not zeros of any $x^d-1, d\mid n$.

In the ring $\Bbb{Q}[x]$ we have the factorization $$x^n-1=\prod_{d\mid n}\Phi_d(x),$$ and we know that $\gcd(\Phi_{d_1},\Phi_{d_2})=1$ whenever $d_1\neq d_2$. Because reduction modulo $p$ is a homomorphism of polynomial rings we get the factorization in $\Bbb{F}_p[x]$ $$x^n-1=\prod_{d\mid n}\Phi'_d(x).\qquad(*)$$ As we assumed $\gcd(n,p)=1$ we have, for $f_n(x)=x^n-1$, $$\gcd(f(x),f'(x))= \gcd(x^n-1,nx^{n-1})=1,$$ so we know that the zeros of $x^n-1$ in any field of characteristic $p$ are also simple. Therefore we still have no common factors and $\gcd(\Phi_{d_1}'(x),\Phi_{d_2}'(x))=1$ whenever $d_1\neq d_2$.

Any root of unity of $\alpha$ order $n$ in $\Bbb{F}_q$ is a zero of the left hand side of $(*)$, so it must also be a zero of one of the factors $\Phi_d'(x)$. Because $\Phi_d'(x)\mid x^d-1$ it follows that $\alpha$ cannot be a zero of $\Phi_d'(x)$ for any proper divisor $d\mid n$. Therefore $\Phi_n'(\alpha)=0$.

Because $\deg\Phi_n(x)=\phi(n)$ equals the number of roots of unity of order $n$ in $\Bbb{F}_q$, we can conclude that $$\Phi_n'(x)=\prod_{\alpha\in\Bbb{F}_q\ \text{of order n}}(x-\alpha).$$

What changes from characteristic zero setting is that the polynomials $\Phi_n(x)$ are usually not irreducible. It remains irreducible after reduction modulo $p$ if and only if $p$ is a generator of the multiplicative group of residue classes $\Bbb{Z}_n^*$.

• How did you obtain the equality $\Phi_n'(x) = \frac{x^n-1}{\text{lcm}\{x^d-1\mid 0<d<n, d\mid n\}}$? – Ramakrishna9403 Apr 8 '18 at 6:11
• Because over $\Bbb{Q}$ we have $$\Phi_n(x)=\frac{x^n-1}{\text{lcm}\{x^d-1\mid 0<d<n, d\mid n\}}.$$ I try to think of a way of making this clearer. – Jyrki Lahtonen Apr 8 '18 at 6:15
• So when we reduce $\Phi_n(x)$ mod $p$, this equality still holds? – Ramakrishna9403 Apr 8 '18 at 6:17
• @Ramakrishna9403 I changed my approach a bit, as you exposed a weakness. I think the new approach is clear. Thanks for keeping me honest! – Jyrki Lahtonen Apr 8 '18 at 6:38
• Correct. But, I don't think hurts us here. – Jyrki Lahtonen Apr 8 '18 at 6:54