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

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