AAR Identifying irreducibles

Section 3.5 Identifying irreducibles

In previous sections we have discussed the notion of unique factorization of elements into a product of irreducibles, but in no context other that the integers,

Z,

do we have much experience identifying irreducibles. So we now take some time to explore tests for (ir)reducibility in polynomial rings

R [x],

where

R

is a UFD.

🔗

To get very far, we really need to leverage the notion of a greatest common divisor. In

Z,

this is a familiar notion based upon factorization and resulting in a unique positive integer when finding the gcd of nonzero integers. For example, we know that

gcd (12, - 30) = + 6,

where somehow that sign of the integers does not matter. Of course we recognize this as a matter of units which can be far more extensive in general rings, so we take an approach that defines a gcd in a more general setting.

🔗

Definition 3.5.1.

Let $R$ be an integral domain, and $a, b \in R,$ not both zero. A greatest common divisor of $a, b$ is an element $d \in R$ satisfying

$d ∣ a$ and $d ∣ b$ (i.e., $d$ is a common divisor)
If $d^{'} ∣ a$ and $d^{'} ∣ b,$ then $d^{'} ∣ d,$ meaning any other common divisor divides $d,$ making $d$ the greatest in terms of divisibility.

🔗

Remark 3.5.2.

It is an easy exercise that in an integral domain $R,$ any two gcds $d, d^{'}$ of elements $a, b$ differ by a unit, that is $d = d^{'} \cdot u$ for some $u \in R^{\times} .$ Since $Z$ has only two units, $\pm 1,$ this explains why in $Z,$ it is safe simply to choose the positive gcd.

🔗

Remark 3.5.3.

Also in the integers, unless someone asked you to compute the gcd of large numbers, your most likely method of finding a gcd was to factor both numbers, and determine the largest power of each prime dividing both numbers.

But as it turns out, factoring in $Z$ (and in other realms) is very hard, so hard that the security of certain cryptographic systems depends on that difficulty, so while in theory, it is a great way to write down a gcd, for practical purposes, it is not very good at all. We review how gcds manifest themselves in Euclidean domains, PIDs, and UFDs.

🔗

Exercise 3.5.1.

Greatest common divisors are guaranteed to exist in any UFD, but how they manifest themselves differs depending on whether the UFD has any more robust properties.

🔗

(a)

Let $R$ be a Euclidean domain with norm $d : R ∖ {0} \to Z_{\geq 0} .$ The division algorithm on $R$ gives rise to a Euclidean algorithm. Show that just as in the case of $Z,$ the last nonzero remainder from the Euclidean algorithm is a gcd of the given elements. Also note that backtracking through the Euclidean algorithm allows you to write $gcd (a, b) = a x + b y$ for some $x, y \in R .$

Hint.

Just as in $\Z\text{,}$ show that if $a = bq+r\text{,}$ then

\begin{equation*} \gcd(a,b) = \gcd(b,r) \end{equation*}

where by $\gcd(a,b)$ we mean any greatest common divisor.

🔗

(b)

Let $R$ be a PID, and $a, b \in R,$ not both zero. Since the ideal $(a, b)$ is a principal ideal, say

(d) = (a, b),

show that $d$ is a gcd of $a, b .$

Hint.

Observe that if the ideal $(a,b) = (d)\text{,}$ then $d$ is a common divisor of $a,b\text{.}$ Moreover, recall that

\begin{equation*} (a,b) = \{ax + by\mid x,y \in R\}\text{,} \end{equation*}

so if $(d) = (a,b),$ then $d = ax_0 + by_0$ for some $x_0, y_0 \in R\text{.}$ Use that to show that $d$ satisfies the other requirement of being a gcd.

🔗

(c)

Let $R$ be a UFD, and $a, b \in R,$ not both zero. Show how to use unique factorization to extract a gcd. In particular, after dispensing with the case that one of $a$ or $b$ may be zero, both $a$ and $b$ can be factored with the same set of irreducibles (up to units) if we allow exponents to be zero when an irreducible divides only one of $a$ or $b .$

🔗

We focus now on polynomial rings, characterizing irreducibles in them and applications. One difficulty that arises relates to the context in which we view a polynomial. We posed a number of interesting questions in Remark 3.4.12 surrounding the universe in which we view things. We now take some time to explore them.

🔗

In thinking about unique factorization and irreducibles, units invariably insert themselves into the picture. We stated in Proposition 3.3.15 that for an integral domain

R,

the unit group of the polynomial ring is the same as the unit group of the coefficient ring (

R [x]^{\times} = R^{\times}

). So when

R

is a field, every nonzero constant is a unit, so irreducible polynomials with coefficients in a field must have degree at least one. For rings such as

Z,

the unit group is much smaller and polynomials of degree zero can also be irreducible.

🔗

Because things are a bit simpler, we begin with polynomials with coefficients in a field

F .

Again by Proposition 3.3.15, any polynomial of degree one in

F [x]

must be irreducible. As we increase the degree, and factor a polynomial, irreducible factors of degree one correspond to roots of the given polynomial. Recall the theorem:

🔗

Theorem 3.5.4. Roots and linear factors.

Let $F$ be a field and $p \in F [x]$ a non-constant polynomial. Then $(x - a) ∣ p$ if and only if $p (a) = 0.$

🔗

(sketch).

Apply the division algorithm in $F[x],$ dividing $(x-a)$ into $p(x),$ and use the evaluation homomorphism at $a$ on the resulting equation.

🔗

It follows by a degree argument that for polynomials over a field, a polynomial of degree 2 or 3 is irreducible if and only if it has no roots. Since finding roots is of some interest, we remind the reader of the rational root test.

🔗

Theorem 3.5.5. Rational Root Test.

Let $R$ be a UFD and let $K$ be its field of fractions (e.g., $R = Z$ and $K = Q$ ). Let $p (x) = a_{n} x^{n} + \dots + a_{1} x + a_{0} \in R [x] .$ Let $r, s \in R$ with $gcd (r, s) = 1 .$ The element $α = r / s \in K$ is a (rational) root of $p$ only if $r ∣ a_{0}$ and $s ∣ a_{n} .$ In particular, if $p$ is monic, then its only possible rational roots belong to $R .$

🔗

Proof.

Assume that $\alpha$ is a root of $p\text{,}$ and evaluate $p$ at $\alpha$ and clear the resulting denominators to produce the equation:

\begin{equation*} a_nr^n + a_{n-1}r^{n-1}s + \cdots + a_1rs^{n-1} + a_0s^n = 0. \end{equation*}

If we move one of the end terms to the other side of the equation, we acquire two equations

\begin{align*} a_nr^n =\amp -( a_{n-1}r^{n-1}s + \cdots + a_1rs^{n-1} + a_0s^n)\\ a_0s^n =\amp -(a_nr^n + a_{n-1}r^{n-1}s + \cdots + a_1rs^{n-1}) \end{align*}

By inspection of those equations,

\begin{equation*} s \mid a_nr^n \text{ and } r \mid a_0s^n. \end{equation*}

However as $\gcd(r,s) = 1\text{,}$ we must have $r\mid a_0$ and $s\mid a_n.$

🔗

We are often in the situation of the previous theorem, having a polynomial with coefficients in a UFD

R

and wanting to determine whether it is irreducible. Viewing the same polynomial in

K [x],

where

K

is the field of fractions, affords us more tools since

K [x]

is a Euclidean domain. Thus it is important to understand the relationship of irreducibles in

R [x]

versus

K [x] .

🔗

This need is amplified as it provides an essential tool to prove Theorem 3.4.10. This relationship is completely described in Gauss's lemma. To state the theorem, we need a definition.

🔗

Definition 3.5.6.

Let $R$ be a UFD, and $p (x) = a_{0} + a_{1} x + \dots + a_{n} x^{n} \in R [x] .$ We say that $p$ is a primitive polynomial if $gcd (a_{0}, \dots, a_{n}) = 1,$ that is, there is no common divisor of all the coefficients except for units. It is immediate that for any $p \in R [x]$ we can write $p = C (p) p_{0}$ where $p_{0}$ is primitive and $C (p) \in R;$ the constant $C (p)$ is usually referred to as the content of $p .$

🔗

Theorem 3.5.7. Gauss's lemma.

Let $R$ be a UFD, and $K$ its field of fractions. Let $p (x) = a_{0} + \dots + a_{n} x^{n}$ be a primitive polynomial in $R [x] .$ Suppose that $p$ factors in $K [x]$ as the product of non-constant polynomials $p (x) = F (X) G (X) .$ Then there exists $α, β \in K^{\times}$ so that

f = α F \in R [x], g = β G \in R [x], and p = f g .

🔗

Remark 3.5.8.

In some texts, Gauss's lemma is phrased as the product of two primitive polynomials is primitive which implies that for two polynomials $p, q \in R [x],$ $C (p q) = C (p) C (q),$ the content is a multiplicative function.

This version of Gauss's lemma is necessary to prove the one above.

🔗

In the above notation, the following corollary clarifies the relationship between irreducibility of a polynomial in

R [x]

versus

K [x] .

🔗

Corollary 3.5.9.

Let $R$ be a UFD, $K$ its field of fractions, and $p \in R [x] .$ Then $p$ is irreducible in $R [x]$ if and only if $p$ is primitive (in $R [x]$ ), and irreducible in $K [x] .$

🔗

Proof.

If $p$ is irreducible in $R[x]\text{,}$ then it is necessarily primitive. If it were reducible in $K[x],$ then $p = FG$ for non-constant polynomials in $K[x].$ By Gauss’s lemma, there exists $\alpha, \beta\in K^\times$ so that

\begin{equation*} f = \alpha F\in R[x], g= \beta G \in R[x],\text{ and } p = fg. \end{equation*}

Since $\deg f, \deg g \ge 1,$ this would imply $p$ is reducible in $R[x]\text{,}$ a contradiction.

Conversely, suppose that $p$ is primitive and irreducible in $K[x].$ If it were reducible in $R[x],$ then $p = fg$ for $f,g \in R[x]$ with $\deg f, \deg g \ge 1$ since $p$ is primitive. Then neither $f$ nor $g$ are units in $K[x]\text{,}$ so the factorization shows $p$ is reducible in $K[x]\text{,}$ a contradiction.

🔗

So now we need some theorems which help us actually determine whether a polynomial is irreducible. Remember we have the rational root test which is useful for pulling off linear factors via Theorem 3.5.4, and can help resolve irreducibility of polynomials defined over a field of degree at most 3. However, even in the case of small degree, it may not be the tool of choice.

🔗

Example 3.5.10.

Consider the polynomial $p (x) = x^{3} + 82 x^{2} + 3456782 \in Z [x] .$ The rational root test would have us check $p (r)$ for all $r ∣ 3456782 .$ As it turns out, there are not that many divisors, but you would have to find them, and that looks painful.

🔗

The following is a very general criterion, but some luck is involved in its use.

🔗

Theorem 3.5.11. Reduction criterion.

Let $R$ be an integral domain, $p \in R [x]$ a monic, non-constant polynomial. Let $I$ be any proper ideal in $R,$ and consider the reduction map $R [x] \to (R / I) [x],$ denoted $p \mapsto \overset{―}{p} .$ If $\overset{―}{p}$ cannot be factored into the product of two non-constant polynomials, then $p$ is irreducible in $R [x] .$

🔗

Proof.

The proof is by contradiction. Suppose that $\overline p$ cannot be factored into the product of two non-constant polynomials, but $p$ is reducible in $R[x]\text{,}$ say $p = fg.$ Since $p$ is monic, the leading coefficients of $f,g$ must be units, which forces $\deg f, \deg g \ge 1$ to provide a witness to reducibility. Set

\begin{equation*} f(x) = a_mx^m + \cdots + a_0 \text{ and } g(x) = b_nx^n + \cdots + b_0. \end{equation*}

As we noted, $a_m, b_n \in R^\times.$

Consider the reduction modulo $I:$

\begin{equation*} p = fg \mapsto \overline p = \overline{fg} =\overline f\cdot \overline g\in (R/I)[x]. \end{equation*}

We note that

\begin{equation*} \overline f= (a_m+I)x^m + \cdots + (a_0+I) \text{ and } \overline g = (b_n+I)x^n + \cdots + (b_0+I). \end{equation*}

Since $a_m, b_n \in R^\times$ and $I$ is a proper ideal, we see $a_m + I \ne 0+ I$ and $b_n+I \ne 0+I,$ so $\deg \overline f, \deg \overline g \ge 1$ which gives a factorization of $\overline p$ into two non-constant polynomials, a contradiction.

🔗

Example 3.5.12.

Let's try the reduction criterion on the polynomial $p (x) = x^{3} + 82 x^{2} + 3456782 \in Z [x]$ on which we chose not to use the root test.

As a first guess, let $I = 2 Z .$ But then $\overset{―}{p} = x^{3} = x \cdot x^{2}$ which does not fit the hypotheses of the criterion, so we try again.

Let $I = 3 Z .$ Then $\overset{―}{p} = x^{3} + x + 2 \in Z / 3 Z [x] .$ It is easy to check that $\overset{―}{p}$ has no roots in $Z / 3 Z$ and since its degree is 3 and $Z / 3 Z$ is a field, we conclude $\overset{―}{p}$ is irreducible over $Z / 3 Z,$ and so of course cannot be written as the product of two non-constant polynomials. By the reduction criterion, $p (x) = x^{3} + 82 x^{2} + 3456782$ is irreducible in $Z [x] .$

🔗

The reduction criterion is surprisingly powerful. Consider the following example of a polynomial in two variables.

🔗

Example 3.5.13.

Let $p (x, y) = - 1 + x - y + x^{2} y + y^{3} \in Q [x, y] .$ We can view $p$ as

p = y^{3} + (x^{2} - 1) y + (x - 1) \in Q [x] [y] .

Let $R = Q [x] .$ So we see that $p$ is monic in $R [y] .$ Let $I = (x) ⊊ R .$ Now $R / I = Q [x] / (x) ≅ Q$ via the evaluation map $x \mapsto 0$ (see Proposition 3.3.1), so $\overset{―}{p} \in (R / I) [y] ≅ Q [y]$ is given by setting $x = 0,$ so

\overset{―}{p} = y^{3} - y - 1 \in Q [y] .

Since the degree is 3, $\overset{―}{p}$ will be irreducible if it has no roots, and the root test tells us the only possible roots are $\pm 1,$ neither of which are roots. The reduction criterion now says that $p$ is irreducible in $Q [x, y] .$

We soon give a different proof that this polynomial is irreducible using Eisenstein's criterion.

🔗

Theorem 3.5.14. Eisenstein's criterion.

Let $R$ be a UFD and $p = a_{n} x^{n} + \dots + a_{0} \in R [x]$ a primitive polynomial. Let $π \in R$ be an irreducible (hence prime (Proposition 3.4.6)), with

π ∣ a_{i}, i = 0 \dots, n - 1, π ∤ a_{n}, and π^{2} ∤ a_{0} .

Then $p$ is irreducible in $R [x] .$

🔗

Proof.

We proceed by contradiction and assume that $p$ is reducible in $R[x]\text{.}$ Since $p$ is primitive, this means

\begin{equation*} p = fg \text{ where } f,g \in R[x], \text{ with } \deg f, \deg g \ge 1, \end{equation*}

say

\begin{equation*} f = b_0+ \cdots + b_r x^r \text{ and } g=c_0+ \cdots + c_sx^s. \end{equation*}

Recalling that $\pi$ is a prime element, then since $\pi \mid a_0=b_0c_0\text{,}$ it must divide one of $b_0$ or $c_0\text{,}$ but $\pi^2 \nmid a_0$ says it can divide precisely one, say $\pi\mid b_0$ and $\pi \nmid c_0.$ Also since $\pi \nmid a_n = b_rc_s\text{,}$ we see $\pi \nmid b_r$ and $\pi \nmid c_s.$

Since $\pi \mid c_0\text{,}$ but $\pi \nmid c_s\text{,}$ let $\ell$ be the smallest index so that $\pi \nmid c_\ell.$ So

\begin{equation*} 0 \lt \ell \le s\lt n \text{ and } a_\ell = b_\ell c_0 + b_{\ell-1}c_1 + \cdots + b_0c_\ell. \end{equation*}

Since $\ell \lt n\text{,}$ we know that $\pi \mid a_\ell,$ and by the choice of $\ell\text{,}$ $\pi \mid c_0, \dots, c_{\ell-1}\text{,}$ which implies $\pi\mid b_0c_\ell\text{.}$ But $\pi$ prime then says $\pi \mid b_0$ or $\pi \mid c_\ell\text{,}$ a contradiction.

🔗

Example 3.5.15.

There exist irreducible polynomials of all degrees $n \geq 1$ in $Z [x] .$

Solution.

Let $p$ be a prime in $\Z.$ Then by Eisenstein, $x^n \pm p$ is irreducible in $\Z[x].$

🔗

Example 3.5.16.

Show that $x^{907} + 27 x^{3} + 15 x^{2} - 81 x + 6$ is irreducible in $Z [x] .$

Solution.

It is irreducible by Eisenstein with $p=3.$

🔗

Example 3.5.17.

Show that $p = - 1 + x - y + x^{2} y + y^{3}$ is irreducible in $Q [x, y] .$

Solution.

We looked at this polynomial when considering the reduction criterion. So here $R=\Q[x]$ is our UFD and we write $p$ as an element of $R[y]$ as

\begin{equation*} p = y^3 + (x^2-1)y + (x-1). \end{equation*}

Moreover, $\pi = (x-1) \in R=\Q[x]$ is an irreducible. We check that Eisenstein's criterion applies, and we are done.

🔗

Given an integral domain

R,

it is often possible to more easily check the irreducibility of a polynomial in

R [x]

by first applying an isomorphism to the ring. That is, if

φ : R [x] \to R [x]

is a ring isomorphism, we know that

p \in R [x]

is irreducible if and only if

φ (p)

is irreducible in

R [x] = φ (R [x]) .

A simple isomorphism is given by

f (x) \mapsto f (x \pm a)

for any

a \in R,

f (x)

is irreducible iff

f (x \pm a)

is irreducible.

🔗

Example 3.5.18.

Let $p$ be a prime in $Z .$ Then

f (x) = 1 + x + x^{2} + \dots + x^{p - 1} = \frac{x^{p} - 1}{x - 1}

is irreducible in $Z [x] .$

Solution.

Let $g(x) = f(x+1)\text{.}$ Then $f$ is irreducible iff $g$ is. We see that

\begin{align*} g(x) =\amp f(x+1) = \frac{(x+1)^p -1}{(x+1)-1}\\ =\amp \frac{x^p + \binom{p}{1}x^{p-1} + \cdots + \binom{p}{p-1}x + 1 -1}{x}\\ =\amp x^{p-1} + \binom{p}{1}x^{p-2} + \cdots + \binom{p}{p-1} \end{align*}

which is irreducible in $\Z[x]$ using Eisenstein with the prime $p$ since $p \mid \binom{p}{k}$ for $1\le k \le p-1$ and $\binom{p}{p-1}=p.$