Fattorizzazione dei polinomi

# Fattorizzazione dei polinomi ###### tags: `md` #### Irriducibilità e fattorizzazione ###### Definizione Un polinomio si dice **monico** se il coefficiente del termine di grado massimo è pari ad $1$. Un elemento $a$ che divide lo zero (cioè diverso da $0$ e tale che esiste $b$ diverso da $0$, con $ab = 0$) è detto **divisore dello zero**. Un anello commutativo è un anello in cui la moltiplicazione è commutativa. In altre parole, se $a$ e $b$ sono elementi dell'anello allora $a\times b=b\times a$ Un anello commutativo con unità e privo di divisori dello zero è detto **dominio di integrità**. $\mathbb{Z},$ $\mathbb{Q}$, $\mathbb{R}$ e $\mathbb{C}$ sono domini di integrità. I domini d'integrità sono anelli con proprietà simili a quelle di $\mathbb{Z}$ Useremo la notazione $A[x]$ quando considereremo il caso allargato di polinomi a coeﬃcienti in un anello $A$ commutativo, con unità e privo di divisori di zero ($A$ è quindi un dominio si integrità). I casi che ci interesseranno saranno essenzialmente quelli dei polinomi a coeﬃcienti in $\mathbb{Z}$, $\mathbb{Z}_p$, $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$, dunque tutti del tipo descritto e, a parte $\mathbb{Z}$, tutti campi. Dato un polinomio $p(x) $di $A[x]$ con $A$ anello, se esistono due polinomi $f(x)$ e$ g(x)$ in $A[x]$ entrambi non invertibili e tali che $$ p(x) = f(x)\cdot g(x) $$ il prodotto $f(x)\cdot g(x)$ si dice una **fattorizzazione** di $p(x)$ in $A[x]$. Sia $f(x)$ un polinomio di $A[x]$ non invertibile. Il polinomio $f(x)$ si dice **riducibile** (o **fattorizzabile**) in $A[x]$ se in $A[x]$ esiste almeno una fattorizzazione di $f(x)$. Altrimenti il polinomio $f(x)$ si dice **irriducibile**. ###### Osservazione Un modo equivalente di dire che un polinomio $f(x)$ di $A[x]$ è irriducibile (ed è quello che solitamente viene richiamato negli esercizi e nelle dimostrazioni) è aﬀermare che qualsiasi scrittura di $f(x)$ come prodotto di polinomi di $A[x]$: $$ f(x) = g(x)h(x) $$ implica che uno dei due polinomi sia invertibile in $A[x]$. Ovvero nel caso di polinomi a coeﬃcienti in un campo $\mathbb{K}$, essendo gli invertibili tutti e soli i polinomi di grado $0$ (le costanti), $f(x)$ è irriducibile in $\mathbb{K}[x]$ se e solo se $f(x)$ ha grado maggiore o uguale a $1$ e non può essere scritto come prodotto di due polinomi (non necessariamente distinti) di grado maggiore di $0$. ###### Proposizione Negli anelli di polinomi $\mathbb{K}[x]$, con $\mathbb{K}$ campo, tutti i polinomi di grado $1$ sono irriducibili. ###### Dimostrazione Supponiamo che il polinomio $f(x)\in \mathbb{K}[x]$ di grado $1$ sia il prodottodi due polinomi $g(x)$ e $h(x)$ di $\mathbb{K}[x]$: $$ f(x) =g(x)h(x) $$ Per le proprietà del grado del prodotto di polinomi abbiamo che: $$ 1 =deg(f(x)) =deg(g(x)) +deg(h(x)) $$ Ovvero uno dei due polinomi deve avere grado $0$. E sappiamo che in $\mathbb{K}[x]$ tutti i polinomidi grado $0$ sono invertibili. ###### Osservazione Mostriamo, ad esempio, che in $\mathbb{Z}[x]$ esistono polinomi di primo grado riducibili. Consideriamo f$(x) = 2x−4$, possiamo scriverlo come $2·(x−2)$ ed i polinomi 2 e $x−2$ non sono invertibili in $\mathbb{Z}[x]$ ###### Definizione Un polinomio $f(x) = \sum^n_{i=0} a_ix^i$ in $\mathbb{Z}[x]$ si dice **primitivo** se il massimo comun divisore tra i suoi coeﬃcienti $a_0,a_1,\ldots,a_n$ è uguale a $1$. La deﬁnizione di polinomio primitivo ci permette di individuare i polinomi irriducibili di primo grado in $\mathbb{Z}[x]$ (e dunque di mostrare che, per esempio, il polinomio $x − 2$ è irriducibile in $\mathbb{Z}[x]$). ###### Proposizione In $\mathbb{Z}[x]$ i polinomi di primo grado sono irriducibili se e solo se sono primitivi. ###### Dimostrazione Se $f(x) =ax+b\in \mathbb{Z}[x]$ di primo grado è il prodotto di due polinomi, allora, per la proprietà del grado $2$, deve essere il prodotto di un polinomio di primo grado $h(x) =sx+t$, per un polinomio di grado $0$, ovvero una costante $c\in\mathbb{Z}$. Questo, per la definizione di uguaglianza tra polinomi significa che $c\cdot s=a$ e $c\cdot t=b$, dunque che $c$ è un divisore comune dei coefficienti di $f(x)$. Dunque esiste $c$ non invertibile (ovvero diverso da $1$ o $−1$), e quindi una fattorizzazione di $f(x)$ (ovvero $c\cdot h(x)$) se e solo se $f(x)$ non è primitivo. ###### Corollario Un polinomio $f(x) \in \mathbb{K}[x]$ di grado $2$ e $3$ è riducibile se e solo se ha una radice in $\mathbb{K}$. ###### Dimostrazione Abbiamo osservato che, in generale, un polinomio di grado $n >1$ che ha una radice in $\mathbb{K}$ è riducibile in $\mathbb{K}[x]$. Viceversa se un polinomio di grado $2$ o $3$ è riducibile allora, sfruttando le proprietà del grado del prodotto di polinomi, necessariamente nel primo caso ($n= 2$) deve essere il prodotto di due fattori di grado $1$, mentre nel secondo caso $(n= 3)$ può essere il prodotto di un polinomio di grado $1$ per un polinomio di grado $2$ o il prodotto di tre polinomi di grado $1$. Ovvero abbiamo stabilito che i polinomi di grado $2$ o $3$ riducibili hanno necessariamente un fattore di grado $1$ e il teorema di Ruffini ci dice che avere un fattore di grado $1$ in $\mathbb{K}[x]$ equivale ad avere una radice in $\mathbb{K}$. ###### Teorema Primalità di un polinomio irriducibile Se $p(x)$ è un polinomio irriducibile in $\mathbb{K}[x]$ dove $\mathbb{K}$ è un campo, e $p(x) | f(x)\cdot g(x)$ (dove $f(x),g(x) \in \mathbb{K}[x]$), allora o vale $p(x) | f(x)$ o vale $p(x) | g(x)$. Vale anche l'analogo del teorema di fattorizzazione unica. ###### Dimostrazione Vale anche l'analogo del teorema di fattorizzazione unica (la dimostrazione è un esercizio caldamente consigliato; è una applicazione del teorema di primalità: si procede in maniera del tutto simile alla dimostrazione della fattorizzazione unica in $\mathbb{Z}$). ###### Teorema Teorema di fattorizzazione unica per polinomi Ogni polinomio di grado $\ge 1$ in $\mathbb{K}[x]$ (dove $\mathbb{K}$ è un campo) è irriducibile o si fattorizza come prodotto di polinomi irriducibili. Inoltre, se $$ f(x) = p_1(x)\cdot p_2(x)\cdot \ldots \cdot p_s(x) = q_1(x)\cdot q_2(x)\cdot \ldots \cdot q_t(x) $$ sono due fattorizzazioni del polinomio $f(x)$ come prodotto di irriducibili, allora vale che $s = t$ e che i polinomi $p_i(x)$ e i polinomi $q_j(x)$ sono a due a due associati. Nel teorema di fattorizzazione unica per polinomi i $p_i(x)$ non sono necessariamente distinti. ###### Parallelismi con gli interi Proprio come nel caso della fattorizzazione tra gli interi, possiamo scrivere la fattorizzazione di un polinomio accorpando i fattori uguali e usando le potenze. Si scriverà dunque $$ h(x) =a\cdot q^{r1}_1(x)\cdot q^{r2}_2(x)\cdots q^{rt}_t(x) $$ dove $a$ è il coefficiente direttivo di $h(x)$, i $q_j(x)$ sono i polinomi irriducibili distinti monici della fattorizzazione di $h(x)$, gli $r_i$ sono i numeri naturali positivi che evidenziano quante volte ricorre il polinomio $q_i(x)$ nella fattorizzazione di $h(x)$. Avendo questa fattorizzazione è molto facile individuare, proprio come avveniva in $\mathbb{Z}$, il $M.C.D.$ di due polinomi (se non si conosce già una fattorizzazione, in generale è invece più conveniente. Se infatti consideriamo un polinomio $g(x)$ e la sua fattorizzazione in irriducibili: $$ g(x) =b\cdot p^{s1}_1(x)p^{s2}_2(x)\cdot \ldots \cdot p^{rj}_j(x) $$ allora il $M.C.D.(h(x),g(x))$ si otterrà facendo il prodotto degli irriducibili che compaionosia fra i $p_m(x)$ che fra i $q_n(x)$, ciascuno preso col minimo esponente fra i due esponentiche troviamo nelle due fattorizzazioni. ###### Osservazione L'unicità della fattorizzazione in $\mathbb{K}[x]$ è a meno dell'ordine dei fattori e di moltiplicazione per invertibili, cioè le costanti. Il teorema di fattorizzazione unica vale per ogni $\mathbb{K}[x]$ con $\mathbb{K}$ campo. #### Fattorizzazione in $\mathbb{C}[x]$ ###### Teorema Teorema fondamentale dell'algebra Ogni polinomio $f(x)$ a coeﬃcienti in $\mathbb{C}$ di grado maggiore di zero ammette almeno una radice in $\mathbb{C}$ Teorema di Ruffini Un polinomio $p(x)$ è divisibile per $(x-a)$ se e solo se $p(a)=0$, ovvero se e solo se $a$ è una radice del polinomio. Usando il teorema fondamentale dell'algebra e il teorema di Ruﬃni abbiamo una caratterizzazione completa degli irriducibili in C. ###### Corollario Ogni polinomio $f \in \mathbb{C}[x]$ di grado $n > 0$ è il prodotto di $n$ fattori di primo grado in $\mathbb{C}[x]$ Segue che **In $\mathbb{C}[x]$ un polinomio è irriducibile se e solo se è di primo grado** ###### Dimostrazione Procediamo per induzione sul grado $n$ di $f$. Se $f$ è di primo grado la tesi segue immediatamente. Sia ora $f(x) =\sum^n_{i=0}a_ix_i$ con $a_i\in C$ e $a_n\neq 0,n >1$. Possiamo scrivere $f(x) =a_ng(x)$ con $g(x)$ monico. Sia $\alpha$ radice di $g(x)$, la cui esistenza è assicurata dal Teorema precedente, allora: $$ f(x) =a_n(x−\alpha)g_1(x) \qquad \text{con} \qquad deg(g_1) =n−1 $$ quindi $g_1$ e di conseguenza $f$ si scrivono come prodotto di fattori di grado $1$. ###### Definizione Chiamiamo funzione **coniugio** la funzione da $\mathbb{C}$ in $\mathbb{C}$ che al numero complesso $a + ib$ associa $\overline{a + ib} = a−ib$ ###### Proprietà Usando la definizione dimostrare le seguenti proprietà della funzione coniugio: 1. I suoi punti fissi, ovvero gli $z\in \mathbb{C}$ tali che $\bar z=z$, sono tutti e soli i numeri reali. 2. Il coniugio della somma è la somma dei coniugi, ovvero per ogni $z,w\in\mathbb{C} \; \overline{z+w}=\bar z+ \bar w$. 3. Il coniugio del prodotto è il prodotto dei coniugi, ovvero per ogni $z,w\in\mathbb{C} \; \overline{z\cdot w}=\bar z \cdot \bar w$. 4. Il prodotto di un numero complesso per il suo coniugato è un numero reale, ovvero per ogni $zin\mathbb{C}$ si ha che $z\cdot \bar z\in\mathbb{R}$. ###### Proposizione Sia $f(x) \in \mathbb{R}[x] \subset \mathbb{C}[x]$ e sia $\alpha \in \mathbb{C}$ una radice di $f$. Allora anche $\alpha$ è una radice di $f$ ###### Dimostrazione Sia $f(x) =\sum^n_{i=0}a_ix^i$ con $a_i\in\mathbb{R}$. Per ipotesi: $$ 0 =f(\alpha) =\sum^n_{i=0}a_i\alpha^i $$ quindi, dalle proprietà precedenti, segue che: $$ \bar 0=\overline{\sum^n_{i=0}a_i\alpha^i}= \sum^n_{i=0}\overline{a_i\alpha^i}= \sum^n_{i=0}a_i\overline{\alpha^i}= \sum^n_{i=0}a_i\overline{\alpha}^i $$ Cioè $f(\overline{\alpha}) = \bar 0 = 0$. #### Fattorizzazione in $\mathbb{R}[x]$ ###### Proposizione Ogni polinomio di grado maggiore di $2$ in $\mathbb{R}[x]$ è riducibile. In $\mathbb{R}[x]$ un polinomio è irriducibile se e solo è di primo grado oppure di secondo grado (del tipo $ax^2 + bx + c$ con $a \neq 0$) con $\Delta = b^2 − 4ac$ minore di zero ###### Dimostrazione Infatti in $\mathbb{C}[x]$ il polinomio $f(x)$ ha $n=deg(f(x))$ radici (non necessariamente distinte) $z_1,\ldots,z_n$. Se una di queste $n$ radici è reale, allora $f(x)$ ha un fattore di grado $1$ e dunque è riducibile, altrimenti se sono tutte radici complesse non reali, $f(x)$ è divisibile per il polinomio reale di secondo grado $(x−z_1)\cdot (x−\overline{z_1})$: $$ f(x) = (x−z_1)·(x−\overline{z_1})\cdot h(x) $$ E per la proprietà del grado del prodotto di polinomi, $h(x)$ ha grado maggiore di $1$ e dunque non è invertibile. #### Fattorizzazione in $\mathbb{Q}[x]$ ###### Lemma Lemma di Gauss Sia $f(x) \in\mathbb{Z}[x]$ Se $f(x) = a(x)b(x)$ in $\mathbb{Q}[x]$ allora possiamo trovare due polinomi $a_1(x) \in \mathbb{Z}[x]$, associato a $a(x)$, e $b_1 \in \mathbb{Z}[x]$, associato a $b(x)$, tali che $$ f(x) = a_1(x)b_1(x) $$ ###### Definizione Il coefficiente direttivo, o coefficiente direttore è il coefficiente del termine con esponente maggiore ###### Teorema Criterio di Eisenstein Sia $$ f(x) = \sum^n_{i=0}a_ix^i $$ un polinomio primitivo di grado maggiore di $1$ a coeﬃcienti interi. Se esiste un numero primo $p$ tale che: 1. $p$ NON divide il coeﬃciente direttivo $a_n$ 2. $p$ divide tutti gli $a_i$ con $i < n$ 3. $p^2$ NON divide il termine noto $a_0$ allora $f(x)$ è irriducibile in $\mathbb{Z}[x]$, e dunque, per il lemma di Gauss, in $\mathbb{Q}[x]$. ###### Dimostrazione Supponiamo che $f(x)$ sia uguale al prodotto dei due polinomi $g(x) =\sum^r_{i=0}b_ix^i$ e $h(x) =\sum^s_{i=0}c_ix^i$ di $\mathbb{Z}[x]$, entrambi di grado maggiore o uguale a $1$. Da $f(x) =g(x)h(x)$ e dalla definizione di uguaglianza tra polinomi, segue che tutti i coefficienti del polinomio a destra sono uguali a tutti i coefficienti del polinomio a sinistra. Facendo i conti, otteniamo un sistema dove gli $n+ 1$ coefficienti $a_i$ di $f(x)$ sono espressi tramite i coefficienti di $g(x)$ e $h(x)$ come segue: $$ a_i=\sum^i_{j=0}b_j\cdot c_{i−j} $$ Partiamo dal basso del'equazione: $a_0=b_0c_0$. Per ipotesi $p$ divide $a_0$, ma $p_2$ non divide $a_0$: questo significa che $p$ divide uno tra $b_0$ e $c_0$, ma non entrambi. Il ruolo dei $b_i$ e dei $c_i$ è simmetrico quindi possiamo, senza perdere di generalità, supporre che $p$ divida $b_0$ e non $c_0$. A questo punto la seconda equazione del sistema è $a_1=b_1c_0+b_0c_1$, che diventà: $$ b_1c_0=a_1−b_0c_1 $$ Ora sappiamo che $p$ divide $a_1$ (ipotesi), $p$ divide $b_0$ (appena stabilito) e dunque $p$ divide $b_1c_0$. Sappiamo anche che $p$ non divide $c_0$ e di conseguenza divide $b_1$. Iterando questo procedimento si ottiene che $p$ divide ogni $b_i$ e di conseguenza divide $a_n=b_rc_s$: ma questo è contro l'ipotesi. L'assurdo nasce dal fatto di aver supposto che $f(x)$, che verifica le tre condizioni del criterio di Eisenstein, possa essere scritto come prodotto di due polinomi di grado maggiore o uguale a $1$. ###### Corollario In $\mathbb{Q}[x]$ esistono polinomi irriducibili di grado $n > 0$ qualsiasi. ###### Dimostrazione Basta considerare il polinomio $x^n−2$ ed applicare Eisenstein con primo $p= 2$. Infatti $2$ divide il termine noto ($2$), ma il quadrato di $p$ ($4$) non divide il termine noto. E infine $2$ non divide il coefficiente direttivo ($1$). Lo stesso ragionamentopermette di dimostrare che $x^n−p$, per un qualsiasi primo $p$, è irriducibile. ###### Proposizione Se $f(x) \in \mathbb{Z}[x]$ e $r/s$ (ridotto ai minimi termini, ovvero con $MCD(r,s) = 1$) è una radice in $\mathbb{Q}$, allora $r$ divide il termine noto e $s$ divide il coeﬃciente direttivo di $f(x)$ Consideriamo il polinomio $f(x) = x^4 + 3x^3 + x^2 − 6x − 6$. Dalla proposizione segue che se $r/s$ è una radice razionale, allora $r$ divide $−6$ e $s$ divide $1$. Ovvero sappiamo che le uniche radici razionali possibili di $f(x)$ sono da ricercare nell'insieme ﬁnito: $$ A = \{\pm 1,\pm 2,\pm 3,\pm 6\} $$ Sostituendo in $f(x)$ non si trova $0$ in nessuno di questi casi, dunque $f(x)$ non ha radici razionali. ATTENZIONE: Questo non signiﬁca che $f(x)$ sia irriducibile! Sappiamo solo che $f(x)$ non ha fattori di grado $1$, ma potrebbe essere il prodotto di due fattori irriducibili di grado $2$. ###### Dimostrazione Sia $f(x) =\sum^m_{j=0}b_jx^j$ a coefficienti interi, l'ipotesi che $r/s$ sia radice equivale a: $$ \sum^n_{i=0}b_i\left({r\over s}\right)^i= 0 $$ Moltiplicando tutto persnsi ottiene: $$ b_nr^n+\underbrace{b_{n−1}r^{n−1}s+\ldots+b_0s^n}_\text{è un multiplo di s} = 0 $$ Per cui $s|b_nr^n$, ma essendo $(s,r) = 1$ questo implica $s|b_n$. Analogamente se raccogliamo $r$, otteniamo che $r$ deve dividere $b_0s^n$, ma essendo $(r,s) = 1$ questo implica che $r|b0$. #### Fattorizzazione in $\mathbb{Z}_p[x]$ Sia infatti $f(x) \in \mathbb{Z}_p[x]$ di grado $n$; allora se è riducibile ha un fattore irriducibile che ha grado minore o uguale a $n/2$ se $n$ è pari, e a $(n−1)/2$ se $n$ è dispari. Essendo $\mathbb{Z}_p$ ﬁnito i polinomi di grado minore o uguale di un ﬁssato $k$ sono ﬁniti (sono $p^{k+1}$) e quindi un modo per trovare una fattorizzazione di $f(x)$ è provare a dividere per tutti i polinomi di grado minore o uguale di $n/2$ (o $(n−1)/2$ nel caso $n$ dispari). Se nessuno di questi divide $f(x)$ allora $f(x)$ è irriducibile, altrimenti continuiamo con lo stesso procedimento ﬁno a che non si scrive $f(x)$ come prodotto di irriducibili. ###### Proposizione Criterio della riduzione modulo $p$ Sia $f(x) = \sum^n_{i=0}a_ix^i$ primitivo a coeﬃcienti interi e sia $p$ un primo che NON divide il coeﬃciente direttivo $a_n$ di $f(x)$. Se il polinomio $f(x)$ di $\mathbb{Z}_p[x]$ ottenuto riducendo i coeﬃcienti modulo $p$ (e considerando dunque le corrispondenti classi di resto) è irriducibile in $\mathbb{Z}_p[x]$ allora $f(x)$ è irriducibile in $\mathbb{Q}[x]$. Notiamo che tale proposizione non permette di concludere niente nel caso il polinomio $f(x)$ ridotto modulo $p$ sia riducibile in $\mathbb{Z}_p[x]$ #### Espansione PDF Polinomi ###### Definizione Dati due polinomi $s(x),p(x) \in \mathbb{K}[x]$, diciamo che il polinomio $s(x)$ **divide** il polinomio $p(x)$ se esiste un polinomio $q(x) \in \mathbb{K}[x]$ tale che $p(x) = q(x)s(x)$. In modo equivalente, possiamo dire che $s(x)$ divide $p(x)$ se il resto della divisione di $p(x)$ per $s(x)$ è uguale a zero. Per indicare che $s(x)$ divide $p(x)$ useremo la notazione $s(x)|p(x)$. Se $s(x)$ divide $p(x)$ si dice che $s(x)$ è un **fattore** del polinomio $p(x)$ o anche che $p(x)$ è un **multiplo** di $s(x)$. Dati due polinomi $p_1(x),p_2(x) \in \mathbb{K}[x]$, non entrambi nulli, un massimo comun divisore di $p_1(x),p_2(x)$ è un polinomio $d(x)$ che divide sia $p_1(x)$ che $p_2(x)$, e tale che ogni altro polinomio che divide sia $p_1(x)$ che $p_2(x)$ ha grado minore o uguale a quello di $d(x)$. ###### Teorema Lemma di Bezout Dati due polinomi $f(x),g(x) \in \mathbb{K}[x]$ non entrambi nulli, esiste un polinomio $d(x)$ che è un massimo comun divisore tra $f(x)$ e $g(x)$. Esistono inoltre due polinomi $t(x)$ e $h(x)$ in $\mathbb{K}[x]$ tali che $$ d(x) = f(x)\cdot h(x) + g(x)\cdot t(x) $$ Algoritmo di Euclide Per calcolare un massimo comun divisore $d(x)$ tra due polinomi $f(x)$ e $g(x)$ di $\mathbb{K}[x]$ si può usare l'algoritmo di Euclide. ###### Osservazione Come nel caso di $\mathbb{Z}$, se $d(x)$ è un massimo comun divisore tra $f(x)$ e $g(x)$, i polinomi $h(x)$ e $t(x)$ del Lemma di Bezout (ovvero tali che $d(x) = f(x)\cdot h(x) + g(x)\cdot t(x)$) si possono calcolare risalendo l'algoritmo di Euclide. ###### Definizione Due polinomi $f(x),g(x)$ in $\mathbb{K}[x]$ si dicono **associati** se diﬀeriscono moltiplicativamente per una costante non nulla, ossia se esiste $k \in \mathbb{K},\; k \neq 0$ tale che $f(x) = k\cdot g(x)$ ###### Proposizione Se $d(x)$ è un massimo comun divisore tra due polinomi non entrambi nulli $f(x),g(x)$ in $\mathbb{K}[x]$ allora tutti i polinomi associati a $d(x)$ sono massimi comun divisori. Dati due polinomi non entrambi nulli $f(x)$ e $g(x)$ in $\mathbb{K}[x]$, se $d_1(x)$ e $d_2(x)$ sono due massimi comun divisori tra $f(x)$ e $g(x)$, allora $d_1(x)$ e $d_2(x)$ sono polinomi associati. #### Polinomi irriducibili in $\mathbb{Z}_2[x]$ Prima di procedere a scrivere la lista dei polinomi irriducibili in $\mathbb{Z}_2[x]$, osserviamo che questa lista potrà essere usata negli esercizi di fattorizzazione in $\mathbb{Z}_2[x]$ ma anche per mostrare la irriducibilià di qualche polinomio in $\mathbb{Q}[x]$. Infatti se cerchiamo un fattore di grado $d\le 4$ di un polinomio $f(x)$ in $\mathbb{Z}_2[x]$ potremo usare questa lista per limitare il numero di divisioni da eseguire. ###### Polinomi irriducibili di grado $1$ in $\mathbb{Z}_2[x]$ Essendo $\mathbb{Z}_2$ un campo, tutti i polinomi di primo grado di $\mathbb{Z}_2[x]$ sono irriducibili. I polinomi di primo grado in $\mathbb{Z}_2[x]$ sono due: $$ x+ 1 \\ x $$ ###### Polinomi irriducibili di grado $2$ in $\mathbb{Z}_2[x]$ I polinomi di grado $2$ in $\mathbb{Z}_2[x]$ sono 4: $$ x^2+x+1\\ x^2+x\\ x^2+ 1 \\ x^2 $$ Sappiamo che un polinomio di grado $2$ è riducibile se e solo se ha una radice. Ora $x^2$ ha radice $0$ doppia e infatti è fattorizzato come $x$ per $x$, $x^2+x$ ha radici $0$ e $1$ e infatti è fattorizzato come $x$ per $x+ 1$, $x^2+ 1$ ha radice $1$ doppia e infatti (in $\mathbb{Z}_2[x]$) è fattorizzato come $x+ 1$ per $x+ 1$. Il polinomio $x^2+x+ 1$ invece, valutato in $0$ e in $1$ vale $1$, di conseguenza non ha radici e dunque è l'unico irriducibile di grado $2$ in $\mathbb{Z}_2[x]$. ###### Polinomi irriducibili di grado $3$ in $\mathbb{Z}_2[x]$ I polinomi di grado $3$ in $\mathbb{Z}_2[x]$ sono 8: $$ x^3+x^2+x+ 1 \\ x^3+x^2+x\\ x^3+x^2+ 1 \\ x^3+x+ 1 \\ x^3+x^2\\ x^3+x \\ x^3+ 1 \\ x^3 $$ Anche i polinomi di grado $3$ sono riducibili se e solo se hanno una radice. Cercando le radici (è molto facile in $\mathbb{Z}_2$ che ha solo due elementi: basta calcolare il valore del polinomio in $0$ e $1$) e applicando, nel caso chei polinomi abbiano effettivamente radici, Ruffini, abbiamo il seguente quadro degli $8$ polinomi di grado $3$ di $\mathbb{Z}_2[x]$: $$ x^3+x^2+x=x\cdot (x^2+x+ 1) \\ x^3+ 1 = (x+ 1)\cdot (x^2+x+ 1) \\ x^3+x^2+x+ 1 = (x+ 1)^3 \\ x^3+x^2=x\cdot x\cdot (x+ 1)\\ x^3+x=x\cdot (x+ 1)^2 \\ x^3=x\cdot x\cdot x\\ x^3+x^2+ 1 \\ x^3+x+ 1 \\ $$ Dunque esistono solo due polinomi irriducibili in $\mathbb{Z}_2[x]$: $x^3+^2+ 1$ e $x3+x+ 1$. ###### Osservazione Osserviamo che in $\mathbb{Z}_2[x]$ una condizione sufficiente (ma non necessaria) affinché un polinomio $f(x)$ di grado maggioredi $1$ sia riducibile è che $f(x)$ abbia un numero pari $2k$ di termini, in quanto valutando $f(x)$ in $1$ si ottiene $2k$ che è $0$ in $\mathbb{Z}_2$. Dunque $1$ è radice di tutti i polinomi con un numero pari di termini in $\mathbb{Z}_2[x]$ e per il teorema di Ruffini questo equivale al fatto che $x−1$ (che in $\mathbb{Z}_2[x]$ è $x+ 1$) divide tutti i polinomi con un numero pari di termini. Ad esempio $x^3+x^2+x+ 1$ ha $4$ termini e infatti valutato in $1$ dà come risultato $4$, ovvero $0$ in $\mathbb{Z}_2[x]$. ###### Polinomi irriducibili di grado $4$ in $\mathbb{Z}_2[x]$ I polinomi di grado $4$ in $\mathbb{Z}_2[x]$ sono $16$ di cui $8$ con un numero pari di termini e dunque sicuramente riducibili: $$ x^4+x^3+x^2+x\\ x^4+x^3+x^2+ 1\\ x^4+x^3+x+ 1\\ x^4+x^2+x+ 1 \\ x^4+x^3\\ x^4+x^2\\ x^4+x\\ x^4+ 1 $$ Rimangono $8$ polinomi con un numero dispari di termini, di cui dobbiamo discutere l'irrudicibilità. Come abbiamo osservato, il criterio del numero pari di termini è una condizione sufficiente, ma non necessaria, per essere irriducibili in $\mathbb{Z}_2[x]$. In particolare anche tutti i polinomi che si annullano in $0$ sono riducibili; tra gli $8$ che sono rimasti ce ne sono 4: $$ x^4+x^3+x^2 \\ x^4+x^3+x \\ x^4+x^2+x\\ x^4 $$ A questo punto rimangono solo i $4$ polinomi di quarto grado che non hanno radici in $\mathbb{Z}_2[x]$: $$ x^4+x^3+x^2+x+ 1\\ x^4+x^3+ 1\\ x^4+x^2+ 1\\ x^4+x+ 1 $$ Non è detto però che tutti siano irriducibili: potrebbero essere il prodotto di polinomi di grado $2$ irriducibili. Sappiamo che in $\mathbb{Z}_2[x]$ l'unico polinomio irriducibile di grado $2$ è $x^2+x+ 1$, dunque l'unico polinomio di grado $4$ di $\mathbb{Z}_2[x]$ che non ha radici ma è riducibile è: $$ (x^2+x+ 1)^2=x^4+x^2+ 1 $$ Perciò ci sono $3$ polinomi di grado $4$ irriducibili in $\mathbb{Z}_2[x]$ e sono: $$ x^4+x^3+x^2+x+ 1\\ x^4+x^3+1\\ x^4+x+1 $$ #### Espansione slide ###### Definizione Sia $R$ una relazione di equivalenza sull'insieme $X$ e sia $a\in X$. La classe di equivalenza di $a$, indicata talvolta con $[a]$, è l'insieme di tutti gli elementi $b$ di $X$ che sono equivalenti ad $a$ Data una relazione di equivalenza su un insieme $X$, posso creare un nuovo insieme i cui elementi sono le classi di equivalenza rispetto alla relazione $R$. Tale insieme viene detto insieme quoziente di $X$ modulo $R$ e viene talvolta indicato con $X/R$. Sia $R$ la relazione di equivalenza su $\mathbb{Z}$ definita da $xRy \iff x \equiv y\;mod\:n$ L'insieme quoziente viene indicato con $\mathbb{Z}/(n)$. I suoi elementi sono le classi di equivalenza modulo $n$ Dato $x\in \mathbb{Z}$, indichiamo con $[x]_n$ la classe di equivalenza di $x$ modulo $n$ Definiamo una somma e un prodotto di classi ponendo $[x]_n+ [y]_n= [x+y]_n \\ [x]_n\cdot [y]_n= [x\cdot y]_n$ Con queste operazioni $\mathbb{Z}/(n)$ è un anello, con $0 = [0]_n$ e $1=[1]_n$ ###### Teorema Le classi di equivalenza dividono $X$ in insiemi a due a due disgiunti.