## Tag Archives: cyclotomic polynomial

### On the factors of a cyclotomic polynomial over ZZ/(p)

Let $\ell$ be a prime and let $\Phi_\ell(x) = \frac{x^\ell-1}{x-1} \in \mathbb{Z}[x]$ be the $\ell$th cyclotomic polynomial. (Remember that $\Phi_\ell$ is irreducible over $\mathbb{Z}$.) Let $p$ be a prime and let $\zeta$ denote any fixed primitive $\ell$th root of unity.

1. Show that if $p=\ell$ then $\Phi_\ell(x) = (x-1)^{\ell-1} \in \mathbb{F}_p[x]$.
2. Suppose $p \neq \ell$ and let $f$ denote the order of $p$ in $\mathbb{F}_\ell$. (That is, $f$ is minimal such that $p^f \equiv 1$ mod $\ell$.) Show that $f$ is minimal such that $\zeta \in \mathbb{F}_{p^f}$. Conclude that the minimal polynomial of $\zeta$ over $\mathbb{F}_p$ has degree $f$.
3. Show that $\mathbb{F}_p(\zeta) = \mathbb{F}_p(\zeta^a)$ for any integer $a$ not divisible by $\ell$. Conclude that, in $\mathbb{F}_p[x]$, $\Phi_\ell(x)$ is the product of $\frac{\ell-1}{f}$ distinct irreducible polynomials of degree $f$.
4. As an example, find the degrees of the irreducible factors of $\Phi_7(x)$ over $\mathbb{F}_p$.

1. Mod $p=\ell$, we have $x^\ell-1 = (x-1)^\ell$. So $\Phi_\ell(x) = (x-1)^{\ell-1}$ as desired.
2. Note that $\zeta \in \mathbb{F}_{p^f}$ precisely when $\zeta$ is a root of $x^{p^f-1}-1$. Since $p^f \equiv 1$ mod $\ell$, we have that $\ell$ divides $p^f-1$. By this previous exercise, $x^\ell - 1$ divides $x^{p^f-1}-1$. Since $\zeta$ is a $\ell$th root of unity, $\zeta \in \mathbb{F}_{p^f}$. Conversely, suppose $\zeta \in \mathbb{F}_{p^t}$. Now $\zeta^\ell \equiv 1$, so $\ell$ divides $p^t-1$ by Lagrange’s theorem in the group $\mathbb{F}_{p^t}^\times$. Thus $p^t \equiv 1$ mod $\ell$, and so $f$ divides $t$. So $f$ is minimal such that $\zeta \in \mathbb{F}_{p^f}$.

Next we claim that $\mathbb{F}_p(\zeta) = \mathbb{F}_{p^f}$. The $(\subseteq)$ inclusion is clear since $\zeta \in \mathbb{F}_{p^f}$. $(\supseteq)$ $\mathbb{F}_p(\zeta) = \mathbb{F}_{p^t}$ for some $t$, since finite fields are essentially unique. By the preceding argument, $f|t$, so $\mathbb{F}_{p^f} \subseteq \mathbb{F}_{p^t} = \mathbb{F}_p(\zeta)$ using this previous exercise.

3. It is clear that $\mathbb{F}_p(\zeta^a) \subseteq \mathbb{F}_p(\zeta)$. Conversely, since $\ell$ does not divide a$, by Bezout’s identity there exist $x,y \in \mathbb{Z}$ such that $ax + \ell y = 1$. Now $(\zeta^a)^x = \zeta^{ax}$ $= \zeta^{1-\ell y}$ $= \zeta$. So $\mathbb{F}_p(\zeta) = \mathbb{F}_p(\zeta^a)$ provided $\ell$ does not divides $a$. Now consider $\Phi_\ell(x)$ as a polynomial over $\mathbb{F}_p$. Let $\zeta_i$ be the distinct primitive $\ell$th roots of unity. By part (b), $\mathbb{F}_p(\zeta_i)$ has degree $f$ over $\mathbb{F}_p$ for each $i$, so the minimal polynomial of $\zeta_i$ over $\mathbb{F}_p$ has degree $f$. So the irreducible factors of $\Phi_\ell$ have degree $f$, and there are $\frac{\ell-1}{f}$ such factors. Moreover, since $\Phi_\ell$ is separable, its factors are distinct. 4. If $p \equiv 1$ mod 7, then $\Phi_7(x) = (x-1)^6$ by part (a). Evidently 2 and 4 have order 3 mod 7, so if $p \in \{2,4\}$ mod 7 then $\Phi_7(x)$ factors into two irreducible cubics. Similarly, 3 and 5 have order 6 mod 7, so that if $p \in \{3,5\}$ mod 7 then $\Phi_7(x)$ is irreducible. Since 6 has order 2 mod 7, if $p \equiv 6$ mod 7, then $\Phi_7(x)$ factors into three irreducible quadratics. ### An alternate characterization of cyclotomic polynomials Prove that $\Phi_n(x) = \prod_{d|n} (x^d-1)^{\mu(n/d)}$, where $\Phi_n$ is the $n$th cyclotomic polynomial and $\mu$ is the Möbius function on $\mathbb{N}^+$ defined by $\mu(1) = 1$, $\mu(m) = (-1)^r$ if $m$ is squarefree with $r$ distinct prime factors, and $\mu(m) = 0$ if $m$ is divisible by a square. [I consulted this document from the Berkeley Math Circle when preparing this solution.] Before we approach this (seemingly magical) identity, let’s build up some machinery. Given an abelian group $A$, let $A_0^\mathbb{N}$ denote the set of all functions $\mathbb{N}^+ \rightarrow A$. Recall that $A^\mathbb{N}_0$ is itself an abelian group under pointwise addition. Now let $R$ be a commutative ring with 1 and let $M$ be a left $R$-module. Define an operator $R_0^\mathbb{N} \times M_0^\mathbb{N} \rightarrow M_0^\mathbb{N}$ by $(f \ast_{R,M} g)(n) = \sum_{st=n} f(s) g(t)$. Note that since $n$ is positive, this sum is finite, and that $s$ and $t$ are nonzero. We will usually drop the subscripts on $\ast$. This operator is called the Dirichlet convolution of $f$ and $g$. Lemma 1: Let $f,g \in R^\mathbb{N}_0$ and $h \in M^\mathbb{N}_0$. Then $f \ast_{R,M} (g \ast_{R,M} h) = (f \ast_{R,R} g) \ast_{R,M} h$. Proof: We have  $(f \ast (g \ast h))(n)$ = $\sum_{st=n} f(s)(g \ast h)(t)$ = $\sum_{st=n} f(s) \sum_{uv=t} g(u)h(v)$ = $\sum_{st=n} \sum_{uv=t} f(s)g(u)h(v)$ = $\sum_{suv=n} f(s)g(u)h(v)$ = $\sum_{tv=n} \sum_{su=t} f(s)g(u)h(v)$ = $\sum_{tv=n} (\sum_{su=t} f(s)g(u)) h(v)$ = $\sum_{tv=n} (f \ast g)(t)h(v)$ = $((f \ast g) \ast h)(n)$ As desired. $\square$ Lemma 2: Let $f,g \in R^\mathbb{N}_0$ and $h,k \in M^\mathbb{N}_0$. Then (using pointwise addition) we have $(f+g) \ast h = (f \ast h) + (g \ast h)$ and $f \ast (h + k) = (f \ast h) + (f \ast k)$. Proof: We have  $(f \ast (h+k))(n)$ = $\sum_{st=n} f(s)(h+k)(t)$ = $\sum_{st=n} f(s)(h(t)+k(t))$ = $\sum_{st=n} f(s)h(t) + \sum_{st=n} f(s)k(t)$ = $(f \ast h)(n) + (f \ast k)(n)$ = $((f \ast h) + (f \ast k))(n)$ as desired. The other equality is analogous. $\square$ Corollary 1: $R^\mathbb{N}_0$ is a ring with pointwise addition and Dirichlet convolution, and $M^\mathbb{N}_0$ is a left $R^\mathbb{N}_0$ module via Dirichlet convolution. Proof: Follows from Lemmas 1 and 2. $\square$ Let $\delta_{1,n}$ denote the Kronecker delta (whose value is 1 if $n=1$ and 0 otherwise) and let $\mu : \mathbb{N}^+ \rightarrow R$ be the Möbius function. Lemma 3: For all $g \in R^\mathbb{N}+0$, $\delta_{1,n} \ast g = g$. Proof: We have $(\delta_{1,n} \ast g)(n) = \sum_{st=n} \delta_{1,s}g(t)$. Now the delta function is 0 unless $s = 1$, in which case $t = n$, and so this sum is precisely $g(n)$ as desired. $\square$ Now let $1$ denote the constant function whose value is 1. Lemma 4: $\mu \ast 1 = \delta_{1,n}$. Proof: We have $(\mu \ast 1)(n) = \sum_{st=n} \mu(s)1(t)$ $= \sum_{s|n} \mu(s)$. If $n = 1$, then we have $(\mu \ast 1)(1) = \delta_{1,1}$. Now suppose $n = p_1^{e_1} \cdots p_k^{e_k}$, with the $p_i$ prime. Now $s = p_1^{d_1} \cdots p_k^{d_k}$, where $0 \leq d_i \leq e_i$. Note that if any $d_i$ is greater than 1, then (by definition) $\mu(s) = 0$. So the only summands which contribute to $(\mu \ast 1)(n)$ those with $d_i \in \{0,1\}$. Moreover, in this case, the value of $\mu(s)$ depends only on whether the number of nonzero $d_i$ is even or odd. There are $2^k$ subsets of $\{1,\ldots,k\}$, half of which have an even number of elements and half odd. So $\sum_{s|n} \mu(s) = \sum_{S \subseteq \{1,\ldots,k\}} (-1)^{|S|}$ $= 0$. Hence $\mu \ast 1 = \delta_{1,n}$. $\square$ Now given $f : \mathbb{N}^+ \rightarrow M$, define $F = 1 \ast f$– so $F(n) = \sum_{d|n} f(d)$. Then $\mu \ast F = (\mu \ast 1) \ast f$ $= f$. Now let $M$ be the abelian group $F(x)^\times$. (The nonzero rational functions over $F$ in one variable). This is an abelian group, hence a $\mathbb{Z}$-module, where we write our operator multiplicatively and our $\mathbb{Z}$-action by exponentiation. Let $f : \mathbb{N}^+ \rightarrow M$ be given by $f(n) = \Phi_n(x)$, and let $F(n) = (1 \ast f)(n) = \sum_{d|n} \varphi_n(x)$ $= x^n-1$. Now $\mu \ast F = f$, which expanded out gives the identity $\Phi_n(x) = \prod_{st=n} (x^s-1)^{\mu(t)}$ as desired. ### A fact about cyclotomic polynomials Let $n > 1$ be an odd integer. Prove that $\Phi_{2n}(x) = \Phi_n(-x)$, where $\Phi_n(x)$ denotes the $n$th cyclotomic polynomial. We begin with a lemma. Lemma: -1 is not an $n$th root of unity for odd $n$. Proof: $(-1)^n-1=-1-1=-2$. $\square$ Let $\zeta$ be a primitive $n$th root of unity. Now suppose $(-\zeta)^t = 1$, so that $(-1)^t\zeta^t = 1$, so $\zeta^t = (-1)^t$. Since $\zeta$ is a primitive $n$th root of unity, with $n$ odd, the powers of $\zeta$ are $n$th roots of unity. By the lemma, we must have $(-1)^t = 1$, so that $2|t$, and thus $\zeta^t=1$, so that $n|t$. Since $2$ and $n$ are relatively prime, $2n|t$, and so $-\zeta$ is a primitive $2n$th root of unity. In particular, $\Phi_n(-x)$ divides $\Phi_{2n}(x)$. Now $\Phi_n(-x)$ has degree $\varphi(n)$, and $\Phi_{2n}(x)$ has degree $\varphi(2n)$, where $\varphi$ denotes the Euler totient. Since $2$ and $n$ are relatively prime, we have $\varphi(2n) = \varphi(2)\varphi(n) = \varphi(n)$. So in fact $\varphi_{2n}(x) = \varphi_n(-x)$. ### The smallest degree of a factor of a cyclotomic polynomial mod a prime Let $\ell$ be a prime and let $\Phi_\ell(x) = \dfrac{x^\ell-1}{x-1} \in \mathbb{Z}[x]$ be the $\ell$th cyclotomic polynomial. In this exercise, we will determine the smallest degree of a factor of $\Phi_\ell$ mod $p$, and in particular determine when $\Phi_\ell$ is irreducible mod $p$. (Recall that $\Phi_\ell$ is irreducible over $\mathbb{Q}$ by Eisenstein’s criterion.) 1. Show that if $p = \ell$ then $\Phi_\ell$ is divisible by $x-1$ in $\mathbb{F}_\ell[x]$. 2. Suppose $p \neq \ell$ and let $f$ denote the order of $p$ in $\mathbb{F}_\ell^\times$ (that is, $f$ is minimal such that $p^f \equiv 1$ mod \ell$). Show that $f$ is minimal such that $\mathsf{GL}_f(\mathbb{F}_p)$ contains an element $A$ of order $\ell$.
3. Show that $\Phi_\ell$ is not divisible by any polynomial of degree smaller than $f$ in $\mathbb{F}_p[x]$. Let $m_A(x) \in \mathbb{F}_p[x]$ denote the minimal polynomial for a matrix $A$ as in (2) and conclude that $m_A(x)$ is irreducible of degree $f$ and divides $\Phi_\ell(x)$ in $\mathbb{F}_p[x]$.
4. Prove that $\Phi_\ell(x)$ is irreducible mod $p$ if and only if $\ell-1$ is the smallest power of $p$ which is congruent to 1 mod $\ell$; that is, $p$ is a primitive root mod $\ell$.

1. As we showed in this previous exercise, $(x-1)^\ell = x^\ell - 1$ in $\mathbb{F}_\ell[x]$. So we have $\Phi_\ell(x) = (x-1)^{\ell-1}$.
2. Suppose $f$ is the order of $p$ mod $\ell$. Recall that $|\mathsf{GL}_f(\mathbb{F}_p)| = \prod_{i=1}^f (p^f - p^{f-i})$. In particular, $|\mathsf{GL}_f(\mathbb{F}_p)| \equiv 0$ mod $\ell$ since $p^f - 1 \equiv 0$. By Cauchy’s Theorem, there exists an element $A$ of order $\ell$ in $\mathsf{GL}_f(\mathbb{F}_p)$.

Now suppose $\mathsf{GL}_m(\mathbb{F}_p)$ has an element $A$ of order $\ell$. Then we have $\prod_{i=1}^m (p^m - p^{m-i}) \equiv 0$ mod $\ell$, and so $p^m - p^{m-i} \equiv 0$ mod $\ell$ for some $i$. Then $p^i \equiv 0$ mod $\ell$. If $m < f$, we have a contradiction, since $f$ is minimal such that $p^f \equiv 1$ mod $\ell$.

3. Suppose $\Phi_\ell(x)$ is divisible by a polynomial $q(x)$ of degree $m < f$ over $\mathbb{F}_p$. Then the companion matrix of $q$ has dimension $m < f$ and satisfies $x^\ell - 1 = 0$. This contradicts (2), which showed that $f$ is minimal such that $\mathsf{GL}_f(\mathbb{F}_p)$ contains an element of order $\ell$.

Now let $m_A(x)$ be the minimal polynomial of the matrix $A$ of order $\ell$ in $\mathsf{GL}_f(\mathbb{F}_p)$. The degree of $m_A$ is at least $f$, by the first paragraph of (3). Moreover the degree of $m_A$ is at most $f$, since the characteristic polynomial of $A$ has degree $f$. So the degree of $m_A$ is exactly $f$. Moreover, $m_A$ must be irreducible, since any proper divisor of $m_A$ also divides $\Phi_\ell(x)$ over $\mathbb{F}_p$ and has degree less than $f$.

4. By part (3), the smallest degree of a (nonunit) divisor of $\Phi_\ell(x)$ over $\mathbb{F}_p$ is precisely the order of $p$ mod $\ell$. So $\Phi_\ell$ is irreducible over $\mathbb{F}_p$ if and only if the order of $p$ mod $\ell$ is $\ell-1$; that is, if $p$ is a generator of $\mathbb{F}_\ell$ or a primitive $\ell$th root of 1.