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

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?

• I think you more or less already derived a contradiction. It may be easier to think as follows. If $a$ where a root modulo $p$ of $\Phi_n(x)$, then $a^n-1\equiv0\pmod p$. Therefore the order $\ell$ of $a$ mod $p$ has to be a factor of $n$. Thus $\ell$ is a factor of $\gcd(n,p-1)=1$. So $\ell=1$. So $a=1$. But $p\nmid\Phi_n(1)$ unless $n$ is a power of $p$, which case was excluded. Nov 11, 2016 at 9:09
• @JyrkiLahtonen Thanks, but why can it not be the case that $n$ is a multiple of $p - 1$? In that case we would just get $(n, p-1) = p-1$ which doesn't help much since the order of any element divides $p-1 = \phi(p)$ Nov 11, 2016 at 9:33

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.

• Thank you, I knew it had to be exactly that contradiction but I had no idea how to show it was a contradiction. Can you provide reference for the statement in your third paragraph? I am not familiar with ring theory (even though in this case it appears to be just terminology), but either way it is not immediately clear to me why the fact that $P'(x)$ has no common factors with $P(x)$ implies that the roots are simple. Nov 11, 2016 at 11:11
• Actually maybe it is clear; If a root has multiplicity greater than $1$, after taking derivative it has multiplicity at least $1$? Can you confirm? Nov 11, 2016 at 11:13
• If $(x-a)^2\mid P(x)$, then $(x-a)\mid P'(x)$ (think: product rule of derivatives). Therefore $x-a$ would be a common factor of both $P(x)$ and $P'(x)$. Nov 11, 2016 at 11:13
• Right, that is what I was trying to say. Thanks! Nov 11, 2016 at 11:14
• @JyrkiLahtonen I wonder why $P'(x)$ has no common factors with $P(x)$? Can we conclude it from the form of $P'(x)$ and $P(x)$ directly? Nov 20, 2022 at 14:40

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

• Could you explain more about the gcd between two phynomial because I only know the gcd between two integers? Thank you so much. Nov 20, 2022 at 11:00