Divisibility for polynomials

Let $S$ be the set of all polynomials of the form $f_1 g_1 + \cdots + f_k g_k$, with $g_1, \dots, g_k \in F[X]$. Before proving the proposition, we prove two claims about this set $S$.

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$

Let $d$ be a GCD of $f_1, \dots, f_k$. Then, for every nonzero $a \in F$, the polynomial $ad$ is also a GCD of $f_1, \dots, f_k$. Now let $b \in F$ be the leading coefficient of $d$, that is, $$d = b X^{\deg d} + c_1 X^{\deg d -1} + \cdots + c_{\deg d -1} X + c_{\deg d},$$ where $c_i \in F$ for $i=1, \dots, \deg d$. Then $b \ne 0$, so $b^{-1} d$ is a 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$

Assume first that $f_1, \dots, f_k$ are relatively prime. Then, by Proposition 5.3, there exist polynomials $g_1, \dots, g_k$ such that $1 = f_1g_1 + \cdots + f_kg_k$, as required.

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$

Assume $p|fg$, but that $p$ does not divide $f$; we need to show that $p|g$. Let $d$ be the monic GCD of $p$ and $f$. Then $d|p$, so there is a polynomial $a$ such that $da = p$. Since $p$ is irreducible, we must have $\deg(a) = 0$ or $\deg(d) = 0$; but if $\deg(a) = 0$, then $a \in F$ is nonzero and $d = a^{-1} p$, which implies that $p|f$, a contradiction. Therefore, we must actually have $\deg(d) = 0$, and since $d$ is monic, this means that $d = 1$, that is, that $p$ and $f$ are relatively prime.

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$

Let $f \in F[X]$ be of degree at least 1, and set $e:= \deg(f)$.

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$

By the Factorization Theorem, there exist $k \in \NN$ and irreducible $p_1, \dots, p_k \in F[X]$ such that $f = p_1 \cdots p_k$. We prove the Theorem again by induction on $k$. If $k=1$, we take $a = 1$ and $\alpha_1 = 1$ and are done. So we assume that $k \gt 1$ and that the corollary holds for all $f$ with factorizations with strictly fewer than $k$ irreducible factors.

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$