# Does $\Phi_n(\alpha)=0$ in $\Bbb{F}_p$ for some $\alpha\in\mathbb{F}_p$ imply that $\mathrm{ord}_p(\alpha) = n$?

Let $$\Phi_n(x)$$ denote the $$n^\text{th}$$ cyclotomic polynomial. Suppose it has a root $$\alpha$$ in the finite field $$\Bbb{F}_p$$ and $$p \nmid n$$. Does it follow that $$\mathrm{ord}_p(\alpha) = n$$?

In the case where we're working with $$\Bbb{C}$$, then this is more or less a trivial result by definition of cyclotomic polynomials. However, it is no longer clear when working with finite fields. We clearly have $$\mathrm{ord}_p(\alpha) \mid n$$, but must equality hold? Also, what if we generalise it to $$\Bbb{F}_{p^n}$$?

• @EwanDelanoy thanks. Can you explain why that implies a negative answer to this question? Also, after some brief research it appears that we can only conclude that's the case if $\frac{n}{m}$ is a prime power (see this).
– user711891
Jun 30, 2020 at 9:49
• @yellowello I have added an answer using elementary arguments. Jun 30, 2020 at 10:17
• @yellowello I have deleted my comment, as it's made obsolete by Shubhrajit Bhattacharya's answer Jun 30, 2020 at 12:40
• Related. Given that I happened to answer that variant I should not use the dupehammer here. I don't want to suggest a merge either, because this question specifies the prime field and the other is a bit more general. Also, I think seeing these answers benefits those who stumble upon the other, so linking the two will do. +1 to y'all. Jun 30, 2020 at 18:53

The following statements are equivalent:

$$(1)$$ $$p\mid\Phi_n(\alpha)$$ for some $$\alpha\in\mathbb{Z}$$ and for some prime $$p$$ such that $$\gcd(p,n)=1$$.

$$(2)$$ $$\mathrm{ord}_p(\alpha)=n$$

Proof:

We proceed by induction on $$n$$. For $$n=1$$ it is trivial since $$\Phi_1(X)=X-1$$ and hence it has a root at $$x\equiv1\pmod{p}$$. Now suppose the hypothesis is true for all $$k. We will prove it for $$n$$.

Suppose $$p\mid\Phi_n(\alpha)$$. Since $$\Phi_n(X)\mid X^n-1$$, therefore $$\alpha^n\equiv1\pmod{p}$$. Then we have $$\mathrm{ord}_p(\alpha)\mid n$$. Let, if possible, $$\mathrm{ord}_p(\alpha)=r. Since $$r\mid n$$ we have $$\gcd(r,p)=1$$. Hence by induction hypothesis we have $$\Phi_r(\alpha)\equiv0\pmod{p}$$. Now $$p\nmid rn$$. Then letting $$P(X)=X^{rn}-1$$, we have $$\gcd(P(X),P'(X))=\gcd(X^{rn}-1,rnX^{rn-1})=1$$ in $$\mathbb{F}_p[X]$$. Hence $$X^{rn}-1$$ has no non-constant repeated factor in $$\mathbb{F}_p[X]$$. Let $$\gcd(\Phi_n(X),\Phi_r(X))=m(X)$$ in $$\mathbb{F}_p[X]$$. Then $$m(X)^2\mid X^{rn}-1$$ in $$\mathbb{F}_p[X]$$ implies $$m(X)=1$$. Hence $$\gcd(\Phi_n(X),\Phi_r(X))=1$$ in $$\mathbb{F}_p[X]$$. This contradicts the fact that $$\Phi_n(\alpha)\equiv\Phi_r(\alpha)\equiv0\pmod{p}$$. Therefore $$\mathrm{ord}_p(\alpha)=n$$

Conversely, let $$\mathrm{ord}_p(\alpha)=n$$. Then $$\alpha^n\equiv1\pmod{p}$$. Since $$\alpha^n-1=\prod_{d\mid n}\Phi_d(\alpha)$$ therefore $$\Phi_l(\alpha)\equiv0\pmod{p}$$ for some $$l\mid n$$. If $$l, then induction hypothesis would imply that $$\mathrm{ord}_p(\alpha)=l, which contradicts the assumption. Therefore $$l=n$$. This completes the inductive step and hence the proof.

• Brilliant answer, just what I'm looking for! Just one question, why does $m(X)^2 \mid X^{rn} - 1$?
– user711891
Jun 30, 2020 at 10:44
• Since both $\Phi_n(X)$ and $\Phi_r(X)$ divides $X^{rn}-1$ and both $\Phi_r(X)$ and $\Phi_n(X)$ are multiples of $m(X)$. Therefore $m(X)\mid X^{rn}-1$ Jun 30, 2020 at 10:46
• That doesn't sound right. $\gcd(X, X) = X$, and obviously $X \mid X$, but $X^2 \nmid X$. Jun 30, 2020 at 10:49
• $$X^{rn}-1=\prod_{d\mid rn}\Phi_d(X)$$ in the right hand side both $\Phi_r(X)$ and $\Phi_n(X)$. Jun 30, 2020 at 11:01
• I see, thanks a lot!
– user711891
Jun 30, 2020 at 11:11

For $$p \mid n$$: $$Φ_4 = X^2 + 1$$ has root $$1$$ in $$\mathbb F_2$$.

Otherwise, let $$q$$ be a power of $$p$$ and $$ζ$$ be a primitive $$q-1$$-st root of unity in an algebraic closure of $$ℚ_p$$. By Hensel’s lemma, since $$X^{q-1} - 1$$ is separable over $$\mathbb F_q$$, we have an isomorphism of the group of $$q-1$$-st roots of unity in $$ℚ_p(ζ)$$ and the multiplicative group in $$\mathbb F_q$$, so $$μ_{q-1,ℚ_p(ζ)} \cong \mathbb F_q^×$$.

Then, since $$p \not\mid n$$, $$X^n - 1$$ is also separable over $$\mathbb F_q$$ and so again by Hensel’s lemma, the above isomorphism restricts to $$μ_{n,ℚ_p(ζ)} \cong μ_{n,\mathbb F_q}$$, with the roots of $$Φ_n$$ in $$ℚ_p(ζ)$$ corresponding to its roots in $$\mathbb F_q$$.

• Thank you. Apologies, but I forgot to include the condition that $p \nmid n$.
– user711891
Jun 30, 2020 at 9:28
• @yellowello I added a solution, which is hopefully right. I’m rusty on $p$-adic theory. Jun 30, 2020 at 9:51