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 \ellth cyclotomic polynomial. (Remember that \Phi_\ell is irreducible over \mathbb{Z}.) Let p be a prime and let \zeta denote any fixed primitive \ellth 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 \ellth 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 \ellth 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 nth 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 nth cyclotomic polynomial.

We begin with a lemma.

Lemma: -1 is not an nth root of unity for odd n. Proof: (-1)^n-1=-1-1=-2. \square

Let \zeta be a primitive nth 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 nth root of unity, with n odd, the powers of \zeta are nth 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 2nth 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 \ellth 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 \ellth root of 1.