Tag Archives: factorization

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.

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.

Factor a given ideal in an algebraic integer ring

Let K = \mathbb{Q}(\sqrt{-6}) and let \mathcal{O} = \mathbb{Z}[\sqrt{-6}] be the ring of integers in K. Factor the ideals (2) and (5) in \mathcal{O}.


We claim that (2) = (2,\sqrt{-6})^2. Indeed, 2 = -\sqrt{-6}^2 - 2^2, so that (2) \subseteq (2,\sqrt{-6})^2. The reverse inclusion is clear.

Now we claim that (2,\sqrt{-6}) is maximal. By Corollary 9.11, N((2)) = 4, and by Theorem 9.14, we have N((2,\sqrt{-6}))^2 = 4, so that N((2,\sqrt{-6})) = 2. By Corollary 9.15, (2,\sqrt{-6}) is a prime ideal.

Thus (2) = (2,\sqrt{-6})^2 is the prime factorization of (2) in \mathcal{O}.

Now we claim that (5) = (5,1+2\sqrt{-6})(5,1-2\sqrt{-6}). Indeed, we have (5,1+2\sqrt{-6})(5,1-2\sqrt{-6}) = (25,5+10\sqrt{-6}, 5-10\sqrt{-6}, 25) = (25, 5+10\sqrt{-6}, 10) = (5).

Next we claim that Q_1 = (5,1+2\sqrt{-6}) and Q_2 = (5,1-2\sqrt{-6}) are proper. Suppose to the contrary that 1 \in Q_1; then we have 1 = 5(a+b\sqrt{-6}) + (1+2\sqrt{-6})(h+k\sqrt{-6}) for some a,b,h,k \in \mathbb{Z}. Comparing coefficients, 5a+h-12k = 1 and 5b+k+2h = 0, which yields a contradiction mod 5. So Q_1 is proper. Likewise, Q_2 is proper. In particular, neither Q_1 nor Q_2 have norm 1 as ideals. Now 25 = N((5)) = N(Q_1)N(Q_2), and neither factor is 1, so that N(Q_1) = N(Q_2) = 5. By Corollary 9.15, Q_1 and Q_2 are prime ideals.

Thus (5) = (5,1+2\sqrt{-6})(5,1-2\sqrt{-6}) is the prime factorization of (5) in \mathcal{O}.

Factor the principal ideals in an algebraic integer ring which are generated by ramified rational primes

Let K = \mathbb{Q}(\sqrt{-5}) and let \mathcal{O} be the ring of integers in K. Factor (p) in \mathcal{O}, where p is a ramified rational prime.


By Theorem 9.6, if p does not divide the discriminant d = -20 of K (using Theorem 6.11), then p is not ramified. Now 20 = 2^2 \cdot 5, so that if p is ramified in K, it is either 2 or 5.

We claim that (2) = (2,1+\sqrt{-5})^2. Indeed, the (\supseteq) direction is clear, and we have 2 = -(1+\sqrt{-5})^2 + 2 \cdot (1+\sqrt{-2}) - 2 \cdot 2. We claim also that P = (2,1+\sqrt{-5}) is maximal. To this end, let a+b \sqrt{-5} \in \mathcal{O}, and say a - b \equiv c mod 2 where c \in \{0,1\}. Evidently, a+b\sqrt{-5} \equiv c mod P; if c \equiv 0 mod 2 then a+b\sqrt{-5} \equiv 0 mod P, and if c \equiv 1 mod 2 then a+b\sqrt{-5} \equiv 1 mod P. Now suppose 1 \in P; then 1 = 2(a+b\sqrt{-5}) + (1+\sqrt{-5})(h+k\sqrt{-5}). Comparing coefficients mod 2, we have 0 \equiv h+k \equiv 1 mod 2, a contradiction. So \mathcal{O}/(2,1+\sqrt{-5}) = \{ \overline{0}, \overline{1}\}, and thus \mathcal{O}/(2,1+\sqrt{-5}) \cong \mathbb{Z}/(2) is a field. Hence P is maximal, and (2) = (2,1+\sqrt{-5})^2 is the prime factorization of (2).

Certianly (5) = (\sqrt{-5})^2. We claim that Q = (\sqrt{-5}) is prime. To see this, note that 5 \in (\sqrt{-5}). If a+b\sqrt{-5} \in \mathcal{O}, then a+b\sqrt{-5} \equiv a \equiv a_0 mod Q, where a_0 \in \{0,1,2,3,4\}. Suppose t \in Q \cap \mathbb{Z}. Then t = (a+b\sqrt{-5})\sqrt{-5} for some a,b \in \mathbb{Z}. Comparing coefficients, we have t \equiv 0 mod 5. In particular, r \not\equiv s mod Q, where r,s \in \{0,1,2,3,4\} are distinct. Thus \mathcal{O}/(\sqrt{-5}) \cong \mathbb{Z}/(5) is a field, so that (\sqrt{-5}) is maximal. Thus (5) = (\sqrt{-5})^2 is the prime factorization of (5).

Factor some ideals in ZZ

Find the prime factorizations of the ideals A = (70) and B = (150) in \mathbb{Z}. Compute ((70),(150)).


Evidently 70 = 2 \cdot 5 \cdot 7 and 150 = 2 \cdot 3 \cdot 5^2, so that (70) = (2)(5)(7) and (150) = (2)(3)(5)^2. Since \mathbb{Z} is a unique factorization domain, (2), (3), (5), and (7) are prime since 2, 3, 5, and 7 are prime.

Now ((70),(150)) = (70,150) = (10), since 70 = 7 \cdot 10, 150 = 15 \cdot 10, and 10 = 150 - 2 \cdot 70.

Factor (10) in QQ(sqrt(-6))

Find two distinct factorizations of 10 in \mathbb{Q}(\sqrt{-6}). Factor 10 as a product of four ideals in \mathbb{Q}(\sqrt{-6}).


Evidently 10 = 2 \cdot 5 = (2 + \sqrt{-6})(2 - \sqrt{-6}); moreover, these factorizations are distinct since, as the only units in \mathbb{Q}(\sqrt{-6}) are \pm 1, 2 is not associate to either of 2 \pm \sqrt{-6}.

We claim that (10) = (2,2+\sqrt{-6})(2,2-\sqrt{-6})(5,2+\sqrt{-6})(5,2-2\sqrt{-6}). To see the (\supseteq) direction, note that this ideal product is generated by all 2^4 possible selections of one generator from each factor. Name the generators \alpha_1,\alpha_2,\beta_1,\beta_2 such that \alpha_1\alpha_2 = \beta_1\beta_2 = 10. Now any selection which includes \alpha_1 (without loss of generality) and does not include \alpha_2 must include both \beta_1 and \beta_2, and so this ideal product is in (10).

Note also that 5 \cdot 5 \cdot (2 + \sqrt{-6}) \cdot (2 - \sqrt{-6}) - 6 \cdot 2 \cdot 2 \cdot (2 + \sqrt{-6}) \cdot (2 - \sqrt{-6}) = 10.

Factor some given algebraic integers in a quadratic field

Factor 5 + \sqrt{3} in \mathbb{Q}(\sqrt{3}) and 7 + \sqrt{-5} in \mathbb{Q}(\sqrt{-5}).


Note that N(5+\sqrt{3}) = 5^2 - 3 = 22 = 2 \cdot 11. If \alpha = \beta\gamma, then N(\beta)N(\gamma) = 2 \cdot 11, so (without loss of generality) N(\beta) = 2. Suppose \beta = h+k\sqrt{3}; then h^2-3k^2 = 2. Mod 3, we have h^2 \equiv 2. This is a contradiction since 2 is not a square mod 3. That is, no algebraic integer in \mathbb{Q}(\sqrt{3}) has norm 2. (Similarly, no integer has norm 11.) Thus 5+\sqrt{3} is irreducible as an integer in \mathbb{Q}(\sqrt{3}).

Evidently, (1+\sqrt{-5})(2-\sqrt{-5}) = 7+\sqrt{-5}. Now N(1+\sqrt{-5}) = 6 and N(2-\sqrt{-5}) = 9. We claim that no integer in \mathbb{Q}(\sqrt{-5}) has norm 3; to that end, suppose h^2+5k^2 = 3. We must have k = 0, so that h^2 = 3, a contradiction. In particular, both 1+\sqrt{-5} and 2-\sqrt{-5} are irreducible in \mathbb{Q}(\sqrt{-5}).

A bound on the number of irreducible factors of an element in an algebraic integer ring

Let \alpha be an algebraic integer in an algebraic number field K. Let N denote the norm over K. Prove that the number of factors in any irreducible factorization of \alpha over K is at most \log_2|N(\alpha)|.


Note that \log_2|N(\alpha)| is some real number between t and t+1, where 2^t \leq |N(\alpha)| < 2^{t+1}. No natural number less than 2^{t+1} can have t+1 prime factors (including multiplicity), and since N is multiplicative, the number of irreducible factors of \alpha is bounded above by the number of prime factors of N(\alpha). So the number of irreducible factors of \alpha in K is at most \log_2|N(\alpha)|.

In a quadratic field, rational primes have at most two irreducible factors

Let K be a quadratic extension of \mathbb{Q} and let p be a rational prime. Prove that, as an algebraic integer in K, p has at most two irreducible factors.


Recall that the conjugates of p for K are p itself with multiplicity 2. So the norm of p over K is p^2. Since (by Lemma 7.1) the norm of an algebraic integer is a rational integer and the norm is multiplicative, p has at most two irreducible integer factors in K.

Factor a given polynomial over two rings

Show that p(x) = x^4 + 1 is irreducible over \mathbb{Q} and reducible over \mathbb{Q}[i].


Note that p(x+1) = x^4 + 4x^3 + 6x^2 + 4x + 2 is Eisenstein at 2 and thus irreducible; so p(x) is irreducible over \mathbb{Q}. On the other hand, p(x) = (x^2+i)(x^2-i). Thus p(x) is reducible over \mathbb{Q}[i].