Prove that $n$th cyclotomic polynomial has no roots modulo $p$

Question

If $p$ is a prime, $p \nmid n$ and $n \nmid (p - 1)$, how can I prove that the $n$th cyclotomic polynomial $\Phi_n(x)$ has no roots modulo $p$? I know that $n \nmid (p - 1)$ implies that there are no elements of order $n$ modulo $p$, and I also know that $x^n - 1 = \prod_{d \mid n}\Phi_d(x)$, which means that if we suppose by contradiction there was a root $a$, it would satisfy $a^n - 1 \equiv 0 \pmod p$ which means it has order $d$ for some divisor $d$ of $n$ and therefore it is also a root of $\Phi_d(x)$. Can I somehow derive a contradiction here?

Answer 1

Trying to fix my incorrect argument in the comments.

We know that we have the factorization $$ P(x):=x^n-1=\prod_{d\mid n}\Phi_d(x).\qquad(*) $$ This factorization holds over both $\Bbb{Q}$ and $\Bbb{Z}_p$, but we are only interested in it over $\Bbb{Z}_p$.

Because $p\nmid n$, the derivative $P'(x)=nx^{n-1}$ has no common factors with $P(x)$ in the ring $\Bbb{Z}_p[x]$. Therefore all the zeros of $P(x)$ (in any extension field of $\Bbb{Z}_p$) are simple.

Assume that $a\in \Bbb{Z}_p$ is a zero of $\Phi_n(x)$. Necessarily $a\neq0$, so $a$ is also a zero of $x^{p-1}-1$. If the order of $a$ is $\ell$, then $\ell\mid p-1$. Furthermore, $a$ is then also a zero of $$x^\ell-1=\prod_{m\mid \ell}\Phi_\ell(x),$$ so $a$ is also a zero of some factor $\Phi_m(x), m\mid\ell$.

So unless $\ell=n=m$ the element $a$ will be a zero of two factors on the right hand side of $(*)$, contradicting the fact that all the zeros of $P(x)$ are simple.

Therefore $\ell=n$. But this implies that $n=\ell\mid p-1$, which was ruled out in the assumptions.

Answer 2

We consider the following theorem

Theorem. Let $P(x)$ be a polynomial over either $\mathbb{R}[x], \mathbb{Q}[x], \mathbb{Z}[x]$ or $\mathbb{Z}_p[x]$. Then there exists a non constant polynomial $m(x)$ so that $m(x)^2 \mid P(x)$ if $\gcd (P(x),P'(x)) \ne 1$.

Proof. Let $g(x) \mid \gcd (P(x),P'(x))$ with all root of $g(x)$ are zeros with multiplicity $1$, or this means $\gcd (g(x),g'(x))=1$.

Then $P'(x)=g(x)h(x)$, we also have $P(x)=g(x)H(x)$ so $P'(x)= g'(x)H(x)+g(x)H'(x)$. This implies $g(x) \mid g'(x)H(x)$. Since $\gcd (g(x),g'(x))=1$ so $g(x) \mid H(x)$. Hence, $g(x)^2 \mid P(x)$. $\square$

From this lemma, we can prove the following proposition.

Proposition. Let $m,n$ be two positive integers and $p$ be a prime so that $p \nmid nm$. Then $\gcd (\Phi_m(x),\Phi_n(x))=1$ over $\mathbb{Z}_p[x]$.

Proof. By applying the theorem over $\mathbb{Z}_p[x]$ we find $x^{mn}-1$ has no repeated factors. Now suppose $\gcd (\Phi_m(x),\Phi_n(x))=g(x) \ne 1$ then $g(x)^2 \mid x^{mn}-1$, a contradiction. $\square$

From this proposition, we can say that for such $m,n,p$, $\Phi_m(x)$ and $\Phi_n(x)$ cannot be both divisible by $p$ for the same value of $x$.

Now, back to the problem. From what you found, $a$ is root modulo $p$ of $\Phi_n(x)$ and $\Phi_d(x)$, or $\Phi_n(a) \equiv \Phi_d(a) \equiv 0 \pmod{p}$, a contradiction since $p \nmid nd$.

In fact, your statement can be rephrase as

Let $p$ be a prime. For all positive integer $n$ and integer $a$ so that $\gcd (n,p)=1$ we have $$p \mid \Phi_n(a) \iff \text{ord}_p(a)=n.$$