LEC ALG3 10

Gauss’s Lemma: Factoring in $\mathbb{Z}[x]$

Remark 115.1(Remark).

In $\mathbb{C}[x]$, every polynomial of positive degree has a root $\alpha$, and therefore a divisor in the form $x-\alpha$. The irreducible polynomials are linear, and the irreducible factorization of a monic polynomial has the form $f(x)=(x-{\alpha }_1)\dots (x-{\alpha }_n)$.

In $\mathbb{R}[x]$, the irreducible polynomials are the linear polynomials and quadratic polynomials with negative discriminant. No polynomial of degree $>2$ is irreducible.

In $\mathbb{Q}[x]$, there exist irreducible polynomials of arbitrary degree.

We have two tools to study factoring in $\mathbb{Z}[x]$:

1. The inclusion $\mathbb{Z}[x]\subseteq \mathbb{Q}[x]$, and
2. the unique homomorphism ${\psi }_p:\mathbb{Z}[x]\to {\mathbb{F}}_p[x]$ that sends $x$ to $x$.

Definition 115.2(Definition).

A polynomial $f(x)={\sum }_{i=0}^n{a}_i{x}^i\in \mathbb{Q}[x]$ is called primitive if

1. it is an integer polynomial of positive degree,
2. the gcd of its coefficients in $\mathbb{Z}$ is $1$, and
3. $a_n>0$.

cde440

It is clear that if $f$ is an integer polynomial of positive degree with positive leading coefficient, then $f$ is primitive iff ${\psi }_p(f)\ne 0$ for every prime $p$.

Lemma 115.3(Lemma).

An integer $p$ is a prime element of $\mathbb{Z}[x]$ iff it is a prime integer.

Proof.

Any integer that is irreducible in$\mathbb{Z}[x]$ must be prime. Let $p$ be prime and suppose $p$ divides $fg$. Then, ${\psi }_p(fg)=0$. Since ${\mathbb{F}}_p[x]$ is an integral domain, this implies either ${\psi }_p(f)=0$ or ${\psi }_p(g)=0$. Thus, $p$ divides $f$ or $p$ divides $g$.□

7e31c7

Theorem 115.4(Gauss's Lemma).

The product of primitive polynomials is primitive.

Proof.

Suppose$f$ and $g$ are primitive polynomials. Since their leading coefficients are positive, the leading coefficient of $fg$ is positive. Moreover, no prime $p\in \mathbb{Z}$ divides $f$ or $g$, so no prime divides $fg$.□

87f54e

Lemma 115.5(Lemma).

Every polynomial $f(x)$ of positive degree with rational coefficients can be written uniquely as $f(x)=c{f}_0(x)$, where $c\in \mathbb{Q}$ and $f_0(x)$ is a primitive polynomial. $c\in \mathbb{Z}$ iff $f(x)\in \mathbb{Z}[x]$. If $f(x)\in \mathbb{Z}[x]$, then the gcd of the coefficients of $f$ is $\pm c$.

Proof.

Let$f(x)\in \mathbb{Q}[x]$. Proving existence of primitive $f_0(x)$ and $c$ such that $f(x)=c{f}_0(x)$ is trivial.

Suppose we are given rational numbers $c$ and $c^{\prime }$ and primitive polynomials $f_0$ and $f_0^{\prime }$ such that $c{f}_0=c^{\prime }{f}_0^{\prime }$. We will show that $f_0=f_0^{\prime }$. Since $\mathbb{Q}[x]$ is a domain, it will follow that $c=c^{\prime }$.

Multiply both sides of $c{f}_0=c^{\prime }{f}_0^{\prime }$ by integers to reduce to the case that $c$ and $c^{\prime }$ are integers. If $c\ne \pm 1$, let $p$ be a prime dividing $c$. Then, $p$ divides $c^{\prime }{f}_0^{\prime }$, and by Lemma 3, $p$ divides $c^{\prime }$ or $f_0^{\prime }$. $p$ cannot divide $f_0^{\prime }$ by definition, so $p$ must divide $c^{\prime }$. Cancel $p$ from both sides. Induction reduces to the case that $c=\pm 1$. The same reasoning shows that then $c^{\prime }=\pm 1$. Both $c$ and $c^{\prime }$ must be the same unit, since $f_0$ and $f_0^{\prime }$ have positive leading coefficients. So $c=c^{\prime }$ and $f_0=f_0^{\prime }$.□

c806f3

Theorem 115.6(Theorem).

1. Let $f_0$ be a primitive polynomial, and let $g\in \mathbb{Z}[x]$. If $f_0$ divides $g$ in $\mathbb{Q}[x]$, then $f_0$ divides $g$ in $\mathbb{Z}[x]$.

2. If $f,g\in \mathbb{Z}[x]$ have a common nonconstant factor in $\mathbb{Q}[x]$, they have a common nonconstant factor in $\mathbb{Z}[x]$.

Proof.

$(1)$ Suppose $g=f_{0}q$ for some $q\in \mathbb{Q}[x]$. Write $g=c{g}_0$ and $q=c^{\prime }{q}_0$ with $g_0$ and $q_0$ primitive by Lemma 5. Note that since $g,g_0\in \mathbb{Z}[x]$, $c\in \mathbb{Z}$. We have $c{g}_0=c^{\prime }{f}_0{q}_0$. By Gauss’s lemma, $f_0{q}_0$ is primitive. By the uniqueness assertion of Lemma 5, $c=c^{\prime }$. Thus, $c^{\prime }$ is an integer, and $q\in \mathbb{Z}[x]$, so $f_0$ divides $g$ in $\mathbb{Z}[x]$.

$(2)$ If $f,g$ have a common nonconstant factor $h=c{h}_0$ in $\mathbb{Q}[x]$, then $h_0$ also divides $f$ and $g$ in $\mathbb{Q}[x]$, so by $(1)$, $h_0$ divides $f$ and $g$ in $\mathbb{Z}[x]$.□

98ad92

Proposition 115.7(Proposition).

3. Let $f\in \mathbb{Z}[x]$ have positive leading coefficient. Then $f$ is an irreducible element of $\mathbb{Z}[x]$ iff it is either a prime integer or a primitive polynomial that is irreducible in $\mathbb{Q}[x]$.

4. Every irreducible element of $\mathbb{Z}[x]$ is a prime element.

Proof.

$(1)$ Lemma 3 proves this when $f\in \mathbb{Z}$. If $f$ is irreducible and not a constant, it cannot have an integer factor different from $\pm 1$, so if its leading coefficient is positive, it will be primitive. Suppose that $f$ is a primitive polynomial and that it has a proper factorization in $\mathbb{Q}[x]$, say $f=gh$. Write $g=c{g}_0$ and $h=c^{\prime }{h}_0$, with $g_0$ and $h_0$ primitive. Then $g_0{h}_0$ is primitive. Since $f$ is also primitive, $f=g_0{h}_0$. Therefore $f$ has a proper factorization in $\mathbb{Z}[x]$ too. So if $f$ is reducible in $\mathbb{Q}[x]$, it is reducible in $\mathbb{Z}[x]$. The fact that a primitive polynomial that is reducible in $\mathbb{Z}[x]$ is also reducible in $\mathbb{Q}[x]$ is clear.

$(2)$ Let $f$ be a primitive irreducible polynomial that divides a product $gh$ of integer polynomials. Then $f$ is irreducible in $\mathbb{Q}[x]$. Since $\mathbb{Q}[x]$ is a PID, $f$ is a prime element of $\mathbb{Q}[x]$. So $f$ divides $g$ or $h$ in $\mathbb{Q}[x]$. By Theorem 6 $f$ divides $g$ or $h$ in $\mathbb{Z}[x]$. Thus, $f$ is a prime element.□

b33f2e

The proof of the following theorem is immediate from Proposition 7 and Proposition 114.10.

Theorem 115.8(Theorem).

$\mathbb{Z}[x]$ is a UFD. Every nonzero polynomial $f(x)\in \mathbb{Z}[x]$ that is not $\pm 1$ can be written as a product

$$f(x)=\pm p_1\dots p_m{q}_1(x)\dots q_n(x),$$

where $p_i$ are integer primes and $q_j(x)$ are primitive irreducible polynomials.

2a6362

Generalization to multivariable polynomial rings over fields

Regard $\mathbb{F}[t,x]$ as the ring $\mathbb{F}[t][x]$ of polynomials in $x$ whose coefficients are polynomials in $t$. The analogue of the field $\mathbb{Q}$ will be $\mathbb{F}(t)$, the field of fractions of $\mathbb{F}[t]$. Denote this field by $\mathcal{F}$. Then, $\mathbb{F}[t,x]$ is a subring of the ring $\mathcal{F}[x]$ of polynomials

$$f=a_n(t)x^n+\cdots +a_1(t)x+a_0(t)$$

whose coefficients are rational functions in $t$. This is useful, since $\mathcal{F}[x]$ is a PID (recall we needed the fact that $\mathbb{Q}[x]$ is a PID in the proof of Proposition 7!).

We will retrace the steps we took to prove that $\mathbb{Z}[x]$ is a UFD. First, we have to define a notion of being ‘primitive’:

Definition 115.9(Definition).

The polynomial $f=a_n(t)x^n+\cdots +a_1(t)x+a_0(t)\in \mathcal{F}[x]$ is called primitive if

1. Its coefficients $a_i(t)$ are polynomials in $\mathbb{F}[t]$, and has positive degree ($n\ge 1$);
2. the gcd of its coefficients in $\mathbb{F}[t]$ is $1$;
3. the leading coefficient $a_n(t)$ is monic.

a53de0

The requirement that $a_n(t)$ be monic in Definition 9 and $a_n>0$ in Definition 2 are just normalization criteria to weed out associates.

Next, we have to prove the analogue of Lemma 3: that $f(t)\in \mathbb{F}[t]$ is prime in $\mathbb{F}[t,x]$ iff it is prime in $\mathbb{F}[t]$.

Proof.

Suppose $f(t)\in \mathbb{F}[t]$. Again, it is clear that if $f(t)$ is prime in $\mathbb{F}[t,x]$, then it is prime in $\mathbb{F}[t]$. Suppose $f(t)$ is prime in $\mathbb{F}[t]$. Suppose $f(t)=g(t,x)h(t,x)$ where $g,h\in \mathbb{F}[t,x]$. Then, ${\text{deg}}_x(f(t))={\text{deg}}_x(g(t,x))+{\text{deg}}_x(h(t,x))$. This forces the degree of $x$ of $g$ and $h$ to be $0$, so $g,h\in \mathbb{F}[t]$. Since $f$ is prime in $\mathbb{F}[t]$, it follows that one of $g$ or $h$ is a unit, so $f(t)$ is prime in $\mathbb{F}[t,x]$.□

Next up: Gauss’s Lemma. The proof is exactly the same as before: If $f$ and $g$ are primitive, $fg$ is primitive (product of monic polynomials is monic), and by the previous lemma, no prime in $\mathbb{F}[t]$ can divide $fg$.

The Lemma 5 analogue is exactly what you’d expect: Every element $f(t,x)$ of $\mathcal{F}(x)$ can be written in the form $c(t)f_0(t,x)$, where $f_0$ is a primitive polynomial in $\mathbb{F}[t,x]$ and $c$ is a rational function in $t$, both uniquely determined. The same proof works.

Theorem 6 and Proposition 7 analogues have the same proofs. Thus, The ring $\mathbb{F}[t,x]$ is a UFD.

Generalization to arbitrary UFDs

We can retrace the same steps as in the previous section to prove that If $R$ is a UFD, the polynomial ring $R[x_1,\dots ,x_n]$ is a UFD:

Theorem 115.10(Theorem).

Let $R$ be a UFD, and let $x$ be a variable. Let $f={\sum }_{i=0}^n{a}_i{x}^i\in R[x]$. Define $c(f)$, the content of $f$, to be the gcd of the coefficients of $f$, up to multiplication by a unit. Call $f\in R[x]$ primitive if $f$ has nonzero degree and $c(f)$ is a unit.

1. $r\in R$ is prime in $R[x]$ iff it is prime in $R$.
2. Let $f,g\in R[x]$. Then, $c(fg)=c(f)c(g)$. In particular, the product of primitive polynomials is a primitive polynomial.
3. Let $\mathcal{R}$ be the field of fractions of $R$. Then, every element $f(x)$ of $\mathcal{R}[x]$ can be written in the form $r{f}_0(x)$, where $f_0\in R[x]$ is primitive and $r\in \mathcal{R}$, both uniquely determined up to a unit factor in $R$.
4. Let $f_0$ be a primitive polynomial, and let $g$ be a polynomial in $R[x]$. If $f_0$ divides $g$ in $\mathcal{R}[x]$, then $f_0$ divides $g$ in $R[x]$.
5. If two polynomials $f$ and $g$ in $R[x]$ have a common nonconstant factor in $\mathcal{R}[x]$, they have a common nonconstant factor in $R[x]$.
6. Let $f$ be an element of $R[x]$. $f$ is irreducible in $R[x]$ iff it is either an irreducible element of $R$, or a primitive polynomial that is irreducible in $\mathcal{R}[x]$.
7. The ring $R[x]$ is a unique factorization domain.

d96427