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.

  • $\begingroup$ $\Phi'_n$ is confusing notation, it might interpreted as the derivative. $\endgroup$ – 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^*$.

| cite | improve this answer | |
  • $\begingroup$ 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\}}$? $\endgroup$ – Ramakrishna9403 Apr 8 '18 at 6:11
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Apr 8 '18 at 6:15
  • $\begingroup$ So when we reduce $\Phi_n(x)$ mod $p$, this equality still holds? $\endgroup$ – Ramakrishna9403 Apr 8 '18 at 6:17
  • 1
    $\begingroup$ @Ramakrishna9403 I changed my approach a bit, as you exposed a weakness. I think the new approach is clear. Thanks for keeping me honest! $\endgroup$ – Jyrki Lahtonen Apr 8 '18 at 6:38
  • 1
    $\begingroup$ Correct. But, I don't think hurts us here. $\endgroup$ – Jyrki Lahtonen Apr 8 '18 at 6:54

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.