This post provides the details for the Divisibility lesson.

Let $F$ be a field and $f,g \in F[X]$.

#### Definition 1

- $f$
**divides**$g$, written $f|g$, if $g = hf$ for some $h ∈ F[X]$. We also say that $g$ is a**multiple**of $f$. - If $\deg(f) \ge 1$, we say that $f$ is
**prime**or**irreducible**, if $f =gh$ implies $deg(g)=0$ or $deg(h)=0$.

#### Example 2

All polynomials of degree 1 are irreducible: if $f$ is of degree 1 and $f = gh$ then, since $$1 = \deg(f) = \deg(g) + \deg(h)$$ and $\deg(g) \ge 0$ and $\deg(h) \ge 0$, one of the degrees $\deg(g)$ or $\deg(h)$ must be 0.

#### Exercise 3

Let $f \in F[X]$, and let $d \in F[X]$ be a divisor of $f$. Show that $\deg(d) \le \deg(f)$.

#### Definition 4

Let $f_1, \dots, f_k \in F[X]$.

- $d ∈ F[X]$ is a
**common divisor**of $f_1,\dots,f_k$ if $d|f_i$ for each $i$. - $d ∈ F[X]$ is a
**greatest common divisor**, or**GCD**, of $f_1,\dots,f_k$, if $d$ is a common divisor of $f_1,\dots,f_k$ and any other common divisor $d′$ of $f_1,\dots, f_k$ divides $d$.

#### Proposition 5

*Let $f_1, \dots, f_k \in F[X]$. and assume each $f_i$ is nonzero. Then:*

*There exists a GCD of $f_1,\dots,f_k$.**If $d$ and $d′$ are GCDs of $f_1,\dots,f_k$, then $d′ = ad$ for some nonzero $a ∈ F$.**If $d$ is a GCD of $f_1,\dots,f_k$, then there are $g_1,\dots,g_k \in F[X]$ such that $d =f_1g_1 + \cdots + f_kg_k$.*

The key idea of the proof of this proposition is part 3, i.e., the realization that a GCD is a sum of multiples of the $f_i$. This seems, at first, counterintuitive, since each multiple of $f_i$ has degree at least $\deg(f_i)$ while, by Exercise 3, any common divisor of the $f_i$ has degree at most the smallest degree of the $f_i$. However, taking a sum of such multiples allows for cancellations to occur.

(Show proof)**Claim 1:** if $f,g \in S$, then $f+g \in S$.

To see this, let $f,g \in S$. So there are $g_1, \dots, g_k \in F[X]$ such that $f = f_1g_1 + \cdots + f_k g_k$, and there are $h_1, \dots, h_k \in S$ such that $g = f_1h_1+\cdots+f_kh_k$. Therefore, $$f+g = f_1g_1 + \cdots + f_kg_k + f_1h_1 + \cdots + f_kh_k = f_1(g_1+h_1) + \cdots + f_k(g_k+h_k),$$ which means that $f+g \in S$.

**Claim 2:** if $f \in S$ and $g \in F[X]$, then $fg \in S$.

To see this, let $f \in S$ and $g \in F[X]$. So there are $g_1, \dots, g_k \in F[X]$ such that $f = f_1g_1 + \cdots + f_k g_k$. Therefore, $$fg = (f_1g_1 + \cdots + f_kg_k) g = f_1(g_1g) + \cdots + f_k(g_kg),$$ which means that $fg \in S$.

We now return to the proof of the proposition: note that $f_i \in S$, since $f_i = f_1\cdot 0 + \cdots + f_i \cdot 1 + \cdots + f_k \cdot 0$; in particular, the set $S$ is not empty.

1. Let $d \in S$ be nonzero such that $\deg(d)$ is minimal among all possible degrees of nonzero polynomials in $S$; we claim that $d$ is a GCD of $f_1, \dots, f_k$.

First, we check that $d$ is a common divisor: by polynomial division, there are polynomials $q_i$ and $r_i$, for $i=1, \dots, k$, such that $$f_i = q_id + r_i$$ and either $r_i = 0$ or $\deg(r_i) \lt \deg(d)$. This means that $$r_i = f_i – q_i d;$$ but by Claim 2, since $d \in S$ we have $q_id \in S$, so by Claim 1, since $f_i \in S$ we get $r_i \in S$. Since $\deg(d)$ is minimal among the degrees of all nonzero polynomials in $S$, and since either $r_i = 0$ or $\deg(r_i) \lt \deg(d)$, it follows that $r_i = 0$. So $f_i = q_id$ for each $i$, that is, $d$ is a common divisor of $f_1, \dots, f_k$.

Second, let $d’ \in F[X]$ be any common divisor of $f_1, \dots, f_k$; we need to show that $d$ divides $d’$. Since $d \in S$, there are polynomials $g_1, \dots, g_k$ such that $d = f_1g_1 + \cdots + f_kg_k$. Since $d’$ divides each $f_i$, there are polynomials $h_1, \dots, h_k$ such that $f_ig_i = d’h_i$, for each $i$. Therefore, $$d = f_1g_1 + \cdots + f_kg_k = d’h_1 + \cdots + d’h_k = d'(h_1 + \cdots + h_k),$$ that is, $d’$ divides $d$.

2. Let $d$ and $d’$ be GCDs of $f_1, \dots, f_k$. Then both $d$ and $d’$ are, in particular, common divisors of $f_1, \dots, f_k$, so that $d|d’$ and $d’|d$. So let $a$ be a polynomial such that $d’ = ad$. It follows from Exercise 3 that $\deg(d) \le \deg(d’)$ and that $\deg(d’) \le \deg(d)$, so that $\deg(d) = \deg(d’)$. But $\deg(d’) = \deg(d) + \deg(a)$, so we must have $\deg(a) = 0$, that is, $a \in F$ is nonzero, as required.

3. The $d$ we chose to prove 1. belongs to $S$, so it is of the required form. Any other GCD $d’$ of $f_1, \dots, f_k$ satisfies, by 2., that $d’ = ad$ for some nonzero $a \in F$. Therefore, $d’ \in S$ as well by Claim 2, which means that $d’$ is of the required form as well.$\qed$

#### Definition 6

A polynomial $f$ is **monic** if the coefficient of $X^{\deg f}$, called the **leading coefficient**, is equal to 1.

#### Corollary 7

*Let $f_1, \dots, f_k \in F[X]$ be nonzero polynomials. Then there is a unique monic GCD of $f_1, \dots, f_k$.*

On the other hand, if $d$ and $d’$ are monic GCDs of $f_1, \dots, f_k$, then $d’ = ad$ for some nonzero $a \in F$, by Proposition 5.2. But then the leading coefficient of $d’$ is equal to $a$ times the leading coefficient of $d$, and since both these leading coefficients are 1, it follows from the group properties of multiplication that $a = 1$ as well, that is, $d’ = d$. $\qed$

#### Definition 8

The polynomials $f_1, \dots, f_k \in F[X]$ are **relatively prime** if their monic GCD is equal to 1.

#### Corollary 9

*The polynomials $f_1, \dots, f_k \in F[X]$ are relatively prime if and only if there exist $g_1, \dots, g_k \in F[X]$ such that $f_1g_1 + \cdots + f_kg_k =1$.*

Conversely, assume that there exist polynomials $g_1, \dots, g_k$ such that $f_1g_1 + \cdots + f_kg_k = 1$. Then 1 belongs to the set $S$ defined in the proof of Proposition 5; since $1 \ne 0$, it follows that 1 is a nonzero polynomial in $S$ of minimal degree (namely, degree 0). So, by the proof of Proposition 5, 1 is a GCD of $f_1, \dots, f_k$, and since 1 is monic, it follows that $f_1, \dots, f_k$ are relatively prime. $\qed$

#### Corollary 10

*Let $f , g, p \in F[X]$, and assume that $p$ is irreducible. If $p|fg$, then $p|f$ or $p|g$.*

So, by Corollary 9, there are polynomials $g_1$ and $g_2$ such that $$pg_1 + fg_2 = 1.$$ Multiplying both sides by $g$ gives $$pgg_1 + fgg_2 = g.$$ Since $p$ divides $pgg_1$ and $p$ divides $fgg_2$ by hypothesis, it follows that the left-hand side is divisible by $p$, hence so is the right-hand side. $\qed$

#### Theorem 11 (Factorization)

Let $f \in F[X]$.

- (Existence)
*If $deg(f ) \ge 1$, then there are irreducible $p_1,\dots,p_k \in F[X]$ such that $f = p_1 \cdots p_k$.* - (Uniqueness)
*If there are irreducible $p_1,\dots,p_k,q_1,\dots,q_l \in F[X]$ such that $f = p_1 \cdots p_k = q_1 \cdots q_l$, then $k = l$ and, after reindexing the $q_i$ if necessary, we have $q_i = a_i p_i$ for some nonzero $a_i \in F$, for each $i = 1,…,k$.*

We prove part 1 by induction on $e$. If $e = 1$, then $f$ is irreducible by Example 2, so we take $k=1$ and $p_1 = f$ and are done. So we assume that $e > 1$ and that part 1 holds for all polynomials $f’$ of degree strictly less than $e$.

Once again, if $f$ is irreducible, we take $k=1$ and $p_1 =f$ and are done; so we also assume that $f$ is not irreducible. This means, by definition, that there are polynomials $g$ and $h$, both of degree at least 1, such that $f = gh$. Since $e = \deg(f) = \deg(g) + \deg(h)$ and both $\deg(g)$ and $\deg(h)$ are at least 1, it follows that $\deg(g) \lt e$ and $\deg(h) \lt e$. So, by the inductive hypothesis, there are irreducible polynomials $p_1, \dots, p_s$ and $p_{s+1}, \dots, p_k$ such that $$g = p_1 \cdots p_s \quad\text{and}\quad h = p_{s+1} \cdots p_k.$$ Therefore $$f = p_1 \cdots p_k,$$ which proves part 1.

For part 2, let $p_1,\dots,p_k,q_1,\dots,q_l \in F[X]$ such that $f = p_1 \cdots p_k = q_1 \cdots q_l$; switching the letters $p$ and $q$, we may assume that $k \le l$. We now prove part 2 by induction on $k$. If $k=1$, then $f = p_1$ is irreducible and part 2 follows (from the definition of irreducible). So we assume that $k \gt 1$ and that part 2 holds for all $p’_1,\dots,p’_{k’},q’_1,\dots,q’_{l’} \in F[X]$ such that $f = p’_1 \cdots p’_{k’} = q’_1 \cdots q’_{l’}$ and $l’ \ge k’ \lt k$.

Let $f’:= p_2 \cdots p_k$. Since $p_1$ divides $f$ and $f = q_1 \cdots q_l$, and since $p_1$ is irreducible, it follows from Corollary 10 that $p_1$ divides $q_j$ for some $j$. Reindexing the $q_j$, we may assume that $p_1$ divides $q_1$. Since $q_1$ is also irreducible, this means that there exists a nonzero $a \in F$ such that $q_1 = p_1 a$. So $$f = p_1 f’ = p_1 \cdot (aq_2 \cdots q_l),$$ and it follows from the division theorem that $$f’ = aq_2 \cdots q_l.$$ Since $f’$ has $k-1$ irreducible factors and $a q_2 \cdots q_l$ has $l-1$ irreducible factors, and since $l \ge k$, it follows from the inductive hypothesis that $l-1 = k-1$ (so that $l=k$) and, after reindexing the $q_i$ if necessary, we have $q_i = a_i p_i$ for some nonzero $a_i \in F$, for each $i = 2,…,k$, as required. $\qed$

#### Definition 12

The polynomials $f_1, \dots, f_k \in F[X]$ are **pairwise relatively prime** if $f_i$ and $f_j$ are relatively prime whenever $i \ne j$.

#### Corollary 13

*Let $f \in F[X]$. Then there exist $a \in F$, irreducible, pairwise relatively prime $p_1,\dots,p_k \in F[X]$ and $\alpha_1,\dots,\alpha_k \in \NN$ such that $$f =ap_1^{\alpha_1} \cdots p_k^{\alpha_k}.$$*

Again, if the $p_i$ are already pairwise relatively prime, we take $a = 1$ and $\alpha_i = 1$ for each $i$ and are done. So we may assume that there exist $i \ne j$ such that $p_i$ and $p_j$ are not relatively prime; reindexing the $p_i$ if necessary, we may assume that $i=1$. Since both $p_1$ and $p_j$ are irreducible, it follows that there exists a nonzero $a \in F$ such that $p_1 = ap_j$. Now set $f’:= p_2 \cdots p_k$; by the inductive hypothesis, there exist nonzero $b \in F$, pairwise relatively prime $q_1, \dots, q_l \in F[X]$ and $\alpha_1, \dots, \alpha_l \in \NN$ such that $$f’ = b q_1^{\alpha_1} \cdots q_l^{\alpha_l}.$$ Since $p_j$ is an irreducible factor of $f’$ by definition, it follows from Corollary 10 that $p_j$ divides $q_r$ for some $r$; reindexing the $q_s$ if necessary, we may assume that $r=1$. So there exists a nonzero $c \in F$ such that $p_j = cq_1$. Putting it all together gives $$f = p_1 f’ = ap_j f’ = acq_1 f’ = abc q_1^{\alpha_1+1} q_2^{\alpha_2} \cdots q_l^{\alpha_l},$$ which is of the required form. $\qed$