11. Divisione di polinomi e UFD

(11.1) Teorema. Se $f,g\in \KK [x]$, $g\neq 0$, $\KK $ campo, allora esistono due polinomi $q$ (il quoziente) e $r$ (il resto) tali che $f=qg+r$ e $\mathrm{grado}(r) < \mathrm{grado}(g)$ (dove si intende $\mathrm{grado}(0)=-1$).

Dim. Se $\mathrm{grado}(f) < \mathrm{grado}(g)$, allora basta porre $q=0$ e $r=f$: $f =0g+ r$ (se $f=0$ si ha anche $r=0$). Se $\mathrm{grado}(g) = 0$, allora $g^{-1}\in \KK $ dato che $g\neq 0$, e $f= (g^{-1} f) g + 0$, cioè $q=g^{-1} f$ e $r=0$. Procediamo per induzione sul grado di $f$, $f=a_0+a_1x + \ldots + a_ nx^ n$, con $a_ n\neq 0$, con $n=\mathrm{grado}(f) > 0$ e $g=b_0+b_1x+\ldots + b_ mx^ m$, con $b_ m\neq 0$ e $m=\mathrm{grado}(g) > 0$. Se $n=1$, occorre solo verificare il caso $m=1$, cioè trovare $q,r\in \KK $ tali che \[ a_0 + a_1 x = q(b_0+b_1x) + r \implies \left\{ \begin{aligned} a_0 & = qb_0 + r \\ a_1 & = qb_1 \end{aligned} \right. \] e quindi $q=a_1b_1^{-1}$, $r=a_0 - a_1b_0 b_1^{-1}$. Supponiamo che la proposizione sia vera per i polinomi di grado minore di $n$: occorre trovare $q=\alpha _0+\ldots +\alpha _ kx^ k$ con $k+m= n$ tale che $\mathrm{grado}(f-qg) < \mathrm{grado}(g)=m$ \[ \bar f = f-qg=a_0 + \ldots + a_ nx^ n - (\alpha _0 + \ldots + \alpha _ kx^ k) (b_0 + \ldots b_ mx^ m) = a_0 -\alpha _0b_0 + \ldots + a_ nx^ n - \alpha _ kb_ m x^{k+m}. \] Ora, dato che $b_ m\neq 0$, allora con $\alpha _ k = a_ n b_ m^{-1}$ si ha $\mathrm{grado}(\bar f) = \mathrm{grado}(f-qg) < k+m = n$, e quindi per ipotesi di induzione esistono $\bar q$, $\bar r$ tali che \[ \bar f = \bar q g + \bar r, \] con $\mathrm{grado}(\bar r) < m$, da cui \[ f = qg + \bar f = qg + \bar qg + \bar r = (q+\bar q)g + \bar r. \]
QED

(11.2) Nota. Osserviamo che se $q=\alpha _0+\ldots +\alpha _ kx^ k$ e $r=\beta _0 + \ldots + \beta _{m-1}x^{m-1}$, l’equazione $f=qg+r$ è un sistema lineare di $n+1$ equazioni nelle $k+1+m=n+1$ incognite $\alpha _ i$, $\beta _ j$ che si riduce, eliminando le $\beta _ j$, ad un sistema di $n-m+1 = k+1$ equazioni nelle $k+1$ incognite $\alpha _ i$

\[ a_ s = \sum _{{i+j=s}} \alpha _ i b_ j, \quad \text { per } s=m \ldots n, \]

dove $0\leq i \leq k$ e $0\leq j\leq m$, cioè (supponendo di completare ponendo $b_ j=0$ per $j > m$ e $j < 0$)

\[ \left\{ \begin{aligned} \alpha _0 b_ m & + & \alpha _1b_{m-1} & +& \ldots & & + & \alpha _ k b_{m-k} & =& a_ m \\ \alpha _0 b_{m+1} & + & \alpha _1 b_{m} & +& \ldots & & + & \alpha _ k b_{m+1-k} & =& a_{m+1} \\ & & \cdots & & \\ \alpha _0 b_ n & +& \alpha _1 b_{n-1} & +& \ldots & & + & \alpha _ k b_{n-k} & =& a_ n. \\ \end{aligned}\right. \]

La matrice $B$ dei coefficienti è una matrice triangolare superiore, con termini sulla diagonale uguali a $b_ m\neq 0$, dato che $b_ j = 0$ per $j > m$

\[ \begin{bmatrix} b_ m & b_{m-1} & \ldots & b_{m-k} \\ 0 & b_ m & \ldots & b_{m+1-k} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & b_ m \end{bmatrix} \]

e quindi $B$ è invertibile, dunque esiste la soluzione al sistema. Osserviamo infine che ponendo $N= I - b_ m^{-1} B$ si ha $N^{k+1} = 0$, e quindi

\[ (b_ m^{-1} B)(I+N+\ldots + N^ k) = (I-N)(I+N+\ldots + N^ k) = I - N^{k+1} = I, \]

da cui segue che $I+\ldots + N^ k$ è l’inversa di $b_ m^{-1}B$, per cui

\[ B ^{-1} = b_ m ( I + N + \ldots + N^{k}). \]


(11.3) Nota. La divisione tra polinomi in $\KK [x]$ può essere estesa a $\KK [x_1,\ldots , x_ l]$ considerando quest’ultima immersa nell’algebra polinomiale $\KK (x_1,\ldots , x_{l-1})[x_ l]$, per cui si possono trovare (unici) i polinomi $q$ e $r$ in $\KK (x_1,\ldots , x_{l-1})[x_ l]$ tali che $f=qg+r$ e il grado di $r$ rispetto a $x_ l$ è inferiore al grado di $g$ rispetto a $x_ l$. Solo che i coefficienti di $q$ e $r$ sono in $\KK (x_1,\ldots , x_{l-1})$ e non è detto che siano in $\KK [x_1,\ldots , x_{l-1}]$. Ricordiamo dall’esercizio 4.9 che un polinomio in $l$ variabili di grado $k$ ha $\binom {k+l}{k}$ coefficienti. Sia $n=\mathrm{grado}(f)$ e $m=\mathrm{grado}(g)$, e $k=n-m$. Il sistema lineare nei $\binom {k+l}{k}$ coefficienti $\alpha _{\vi }$ di $q$ e nei $\binom {m-1+l}{m-1}$ coefficienti $\beta _{\vj }$ di $r$ indotto dall’equazione $f=qg+r$ ($\vi $ e $\vj $ sono multi-indici di lunghezza $l$), in cui $\mathrm{grado}(r) < \mathrm{grado}(g)$, consiste di $n+1$ equazioni nelle

\[ \binom {k+l}{k} + \binom {m-1+l}{m-1} \]

variabili. Se $l=1$, queste sono $k+1 + m = n+1$, altrimenti il numero di variabili eccede il numero di equazioni ($n+1$), e le soluzioni non sono certamente uniche (cfr. esercizio 4.19). L’estensione a più variabili dell’algoritmo di divisione di polinomi in una variabile è un problema delicato. Occorre sostituire il grado globale con un buon ordinamento dei monomi nelle variabili $x_1,\ldots , x_ l$.

Un dominio di integrità (integral domain) è un anello privo di divisori dello zero (cioè di elementi non nulli $a,b$ tali che $ab=0$). Un dominio di integrità è un dominio a fattorizzazione unica (unique factorization domain) se esiste una decomposizione in fattori irriducibili $r= \epsilon p_1^{\mu _1} \ldots p_ l^{\mu _ l}$ (con $\epsilon $ unità dell’anello – cioè invertibile nell’anello), e questa è essenzialmente unica (cioè le molteplicità $\mu _ i$ e le componenti $p_ i$ sono uniche a meno di permutazioni e moltiplicazione per invertibili).

Osserviamo che se $R$ è un UFD, allora ben è definito (a meno di invertibili) il massimo comun divisore di $l$ elementi non nulli di $R$, $MCD(a_1,\ldots , a_ l)$ (esercizio).

(11.4) Teorema.[Gauss] Se $R$ è un UFD, allora $R[x]$ è un UFD.

Dim. Se $f\in R[x]$, sia $\operatorname {cont}(f)\in R$ il MCD dei coefficienti di $f$. Vale il seguente lemma.

(11.5) Se $f,g\in R[x]$, allora $\operatorname {cont}(fg) = \operatorname {cont}(f) \operatorname {cont}(g)$.

Dim. È chiaro che $\operatorname {cont}(kf) = k \operatorname {cont}(f)$, se $k\in R$ non è zero. Allora, è sufficiente considerare il caso $\operatorname {cont}(f) = \operatorname {cont}(g)=1$. Occorre mostrare che $\operatorname {cont}(fg) =1$. Se così non fosse, esisterebbe $p\in R$ non invertibile e irriducibile che divide tutti i coefficienti di $fg$, ma $p$ non divide tutti i coefficienti di $f$ né tutti i coefficienti di $g$. Sia \[ \begin{aligned} f & = \sum _{i=0}^ n a_ i x^ i \\ g & = \sum _{j=0}^ m b_ j x^ j, \\ \implies fg & = \sum _{k=0}^{n+m} \left( \sum _{i+j=k} a_ i b_ j\right) x^{i+j}. \end{aligned} \] Siano $\bar i $ il più piccolo indice per cui $p$ non divide $a_ i$, e $\bar j$ il più grande indice per cui $p$ non divide $b_ j$. Sia $\bar k= \bar i + \bar j$. Il coefficiente di $x^{\bar k}$ in $fg$ è uguale a \[ a_0 b_{\bar k} + a_1 b_{\bar k-1} + ... + a_{\bar i} b_{\bar j} + \ldots + a_{\bar k -1} b_1 + a_{\bar k} b_0, \] ed è divisibile per $p$. I coefficienti dei termini della somma a sinistra di $a_{\bar i} b_{\bar j}$ sono divisibili per $p$ (perché $\bar j$ è il più grande), e i coefficienti della somma a destra di $a_{\bar i} b_{\bar j}$ sono divisibili per $p$ (perché $\bar i$ è il più piccolo). Ma allora anche $a_{\bar i} b_{\bar j}$ è divisibile per $p$, e questo è assurdo perché $a_{\bar i}$ e $b_{\bar j}$ non sono divisibili per $p$, e $p$ è irriducibile in $R$ UFD, quindi deve dividerne almeno uno. Quindi $\operatorname {cont}(fg) = 1$.
QED

Esistenza: sia $f\in R[x]$ un polinomio. Allora se $u=\operatorname {cont}(f)$, si ha $f = u f_0$, con $\operatorname {cont}(f_0)=1$. Se $f_0$ non è irriducibile, si scrive come prodotto $f_0 = g h$, con $\operatorname {cont}(g) \operatorname {cont}(h) = 1$, e quindi (a meno di invertibili) si può supporre $\operatorname {cont}(g) = \operatorname {cont}(h) = 1$. Iterando, si mostra che i fattori irriducibili (che esistono perché il grado di $g$ e di $h$ non può essere meno di zero) di $f_0$ hanno $\operatorname {cont}=1$. Si può quindi scrivere

\[ f = u f_1^{\mu _1} \ldots f_ l^{\mu _ l} \]

con $u\in R$, $\mu _ i \in \NN $ con $\mu _ i \geq 1$, e $\operatorname {cont}(f_ i) = 1$. Se $d_ i$ è il grado di $f_ i$ e $d$ il grado di $f$, risulta $d=\sum _{i=1}^ l d_ i \mu _ i$.

Unicità: per l’unicità, occorre mostrare che se

\[ f = u f_1^{\mu _1} \ldots f_ l^{\mu _ l} = v p_1^{\beta _1} \ldots p_ l^{\beta _ k} \]

allora $l=k$, e a meno di permutazioni ed invertibili si ha $f_ i = p_ i$, $\beta _ i = \mu _ i$, $u=v$.

Per prima cosa, osserviamo che se i $p_ i$ sono irriducibili, allora $\operatorname {cont}(p_ i) = 1$, e allora $\operatorname {cont}(f) = u = v$ (a meno di invertibili di $R$). Sia $\KK $ il campo delle frazioni di $R$: l’anello dei polinomi $\KK [x]$ è un UFD (è euclideo, e quindi a ideali principali) e contiene $R[x]$.

Se $p\in R[x]$, con $\operatorname {cont}(p)=1$, è riducibile in $\KK [x]$, allora $p = \dfrac {q_1}{r_1} \dfrac {q_2}{r_2}$ con $q_ i \in R[x]$ e $r_ i\in R$ in modo tale che $\operatorname {cont}(q_ i)$ e $r_ i$ non hanno divisori comuni. Ma allora $r_1r_2 \operatorname {cont}(p) = r_1 r_2 = \operatorname {cont}(q_1) \operatorname {cont}(q_2)$, e deve essere $\operatorname {cont}_(q_1) = r_2$ e $\operatorname {cont}(q_2) = r_1$ ($R$ è UFD) a meno di invertibili. Allora $r_1$ divide tutti i coefficienti di $q_2$, e $r_2$ divide tutti i coefficienti di $q_1$, e a meno di invertibili

\[ p = \dfrac { q_1 }{r_2} \dfrac {q_2}{r_1}, \]

con $\dfrac {q_1}{r_2} \in R[x] \ni \dfrac {q_2}{r_1}$. In altre parole, se $p$ è riducibile in $\KK [x]$, allora è riducibile anche in $R[x]$. Ma allora, si ha in $\KK [x]$ l’uguaglianza

\[ f_1^{\mu _1} \ldots f_ l^{\mu _ l} = p_1^{\beta _1} \ldots p_ l^{\beta _ k} \in \KK [x] \]

con $f_ i$ e $p_ i$ irriducibili in $\KK [x]$, da cui segue che $k=l$ e a meno di permutazioni e invertibili (di $\KK $) $\mu _ i = \beta _ i$, $p_ i = f_ i$. La dimostrazione si conclude considerando che se $p_ i = k f_ i$ con $k\in \KK $, allora esistono $a,b\in R$ senza fattori comuni tali che $ap_ i = b f_ i$, ma dato che $\operatorname {cont}(p_ i) = \operatorname {cont}(f_ i) = 1$, deve essere $a=b$ (a meno di invertibili di $R$), cioè $k$ è invertibile anche in $R$.

QED

(11.6) Corollario. Se $\KK $ è un campo, allora l’anello dei polinomi $\KK [x_0,\ldots , x_ n]$ è un UFD.