Fattorizzazione

In matematica, la fattorizzazione o scomposizione in fattori di un numero o altro oggetto matematico consiste nella loro rappresentazione come prodotto di più fattori, di solito più piccoli o più semplici e della stessa natura. Per esempio ${\displaystyle 3\times 5}$ è una fattorizzazione dell'intero ${\displaystyle 15}$. Invece ${\displaystyle (x-2)(x+2)}$ è una fattorizzazione del polinomio ${\displaystyle x^{2}-4.}$

La fattorizzazione non è generalmente considerata significativa negli insiemi numerici aventi un'operazione di divisione, come i numeri reali o quelli complessi, poiché qualsiasi ${\displaystyle x}$ può essere scritto banalmente come ${\displaystyle (xy)\times (1/y)}$ per ogni ${\displaystyle y}$ diverso da zero. In ogni caso un'utile fattorizzazione per i numeri razionali e le funzioni razionali può essere ottenuta riducendoli ai minimi termini e successivamente fattorizzando i loro numeratori e denominatori.

La fattorizzazione degli interi era già in uso presso gli antichi matematici greci: Apollonio di Perga, Archimede, Euclide, ecc. Si deve a Euclide il teorema fondamentale dell'aritmetica in cui si afferma che ogni intero positivo può essere scomposto in un prodotto di numeri primi, cioè numeri che non possono essere ulteriormente fattorizzati in altri interi maggiori di 1, e che questo prodotto è unico^[1] se si trascura l'ordine dei fattori. La fattorizzazione è un processo algoritmico di successive divisioni per ottenere i singoli fattori e quindi può apparire metaforicamente come l'inverso della moltiplicazione, ma la difficoltà di questo processo cresce enormemente con i grandi numeri ed è proprio questa difficoltà che viene sfruttata dai moderni sistemi di crittografia RSA.

Anche la fattorizzazione di un polinomio è studiata da secoli. Nell'algebra elementare, fattorizzare un polinomio si riduce al problema di trovare le sue radici per poi trovare i fattori il cui prodotto è uguale al polinomio. Un polinomio con coefficienti interi gode anch'esso della proprietà simile a quella del teorema fondamentale dell'aritmetica, con la differenza che ogni suo fattore viene detto polinomio irriducibile. Un polinomio a una incognita e coefficienti complessi ammette un'unica fattorizzazione in prodotto di polinomi lineari (cioè di grado uno), caso particolare del teorema fondamentale dell'algebra. I polinomi a coefficienti interi sono fondamentali per l'algebra computazionale. Ci sono algoritmi computazionali efficienti per il calcolo completo di un anello polinomiale a coefficienti razionali (si veda la scomposizione dei polinomi).

Un anello commutativo che ha una fattorizzazione unica è detto dominio a fattorizzazione unica. Ci sono sistemi numerici come certi anelli di interi algebrici, che non sono domini a fattorizzazione unica. Tuttavia, essi soddisfano la proprietà più debole di essere un dominio di Dedekind: gli ideali ammettono fattorizzazione unica in ideali primi.

La fattorizzazione si può riferire a un concetto più generale di scomposizione di un oggetto matematico in un prodotto di oggetti più piccoli o più semplici. Per esempio, ogni funzione può essere fattorizzata nella composizione di una funzione suriettiva con una funzione iniettiva. Le matrici hanno molti tipi di fattorizzazione in prodotti di matrici. Per esempio, ogni matrice ha un'unica fattorizzazione LUP consistente nel prodotto di una matrice triangolare inferiore ${\displaystyle L}$, avente tutti gli elementi della diagonale uguali a 1, per una matrice triangolare superiore ${\displaystyle U}$, e per una matrice di permutazione ${\displaystyle P}$.

Numeri interi

Dal teorema fondamentale dell'aritmetica si ha che ogni numero intero maggiore di 1 ha un'unica fattorizzazione in numeri primi, cioè in numeri interi che non possono essere a loro volta fattorizzati in interi maggiori dell'unità.

Per calcolare la fattorizzazione di un intero ${\displaystyle n}$, occorre un algoritmo per trovare un divisore ${\displaystyle q}$ di ${\displaystyle n}$ a meno che ${\displaystyle n}$ sia primo. Nel caso che si sia trovato un divisore, la ripetizione dell'algoritmo ai fattori ${\displaystyle q}$ e ${\displaystyle n}$ / ${\displaystyle q}$ si concluderà alla fine con il completamento della fattorizzazione di ${\displaystyle n}$.^[2]

Per trovare un divisore ${\displaystyle q}$ di ${\displaystyle n}$, se esiste, è sufficiente verificare tutti i valori di ${\displaystyle q}$ tali che ${\displaystyle 1<q}$ e ${\displaystyle q^{2}\leq n}$. Infatti, se ${\displaystyle r}$ è un divisore di ${\displaystyle n}$ e ${\displaystyle r^{2}>n}$, allora ${\displaystyle q=n/r}$ è un divisore di ${\displaystyle n}$ tale che ${\displaystyle q^{2}\leq n}$.

Se si provano i valori di ${\displaystyle q}$ in ordine crescente, il primo divisore trovato è necessariamente un numero primo, e il cofattore ${\displaystyle r=n/q}$ non può avere un divisore minore di ${\displaystyle q}$. Per ottenere la completa fattorizzazione, è perciò sufficiente ripetere l'algoritmo cercando un divisore di ${\displaystyle r}$ non minore di ${\displaystyle q}$ e non maggiore di ${\displaystyle {\sqrt {r}}}$.

Non occorre verificare tutti i valori di ${\displaystyle q}$ per applicare il metodo. In linea di principio è sufficiente provare con divisori primi. Per fare ciò occorre avere una tabella di numeri primi, magari ottenuta con il crivello di Eratostene. Poiché il metodo di fattorizzazione indicato è essenzialmente lo stesso del crivello, è in generale più efficiente cercare un divisore solo per quei numeri per i quali non è immediatamente chiaro se siano primi o no. Normalmente si procede con i divisori 2,3,5 e i numeri ${\displaystyle >5}$, che abbiano come cifra delle unità 1,3,7,9 e che la somma delle cifre di ${\displaystyle q}$ non sia multipla di 3.

Questo metodo funziona bene per fattorizzare piccoli interi, ma è inefficiente per grandi interi. Ad esempio, Pierre de Fermat non fu in grado di scoprire che il sesto numero di Fermat

${\displaystyle 1+2^{2^{5}}=1+2^{32}=4.294.967.297}$

non è un primo. Infatti, l'applicazione del metodo riportato richiederebbe più di 10 000 divisioni, per quel numero di 10 cifre.

Ci sono algoritmi più efficienti, ma non ancora abbastanza. Allo stato attuale dell'arte non si riesce ancora a fattorizzare, pur con i calcolatori più potenti, un numero che abbia 500 cifre e sia il prodotto di due primi scelti a caso. Questa incapacità garantisce la sicurezza su cui si basa il sistema di crittografia RSA, che è largamente usato per la protezione delle comunicazioni internet.

Esempio

Per fattorizzare ${\displaystyle n=1386}$ in un prodotto di primi:

• Iniziare con la divisione per 2 (n è pari) e ${\displaystyle n=2\cdot 693}$. Continuare con 693, e 2 come primo candidato divisore.
• 693 è dispari (2 non è un suo divisore), ma è multiplo di 3: si ottiene ${\displaystyle 693=3\cdot 231}$ e ${\displaystyle n=2\cdot 3\cdot 231.}$ Continuare con 231, e 3 come primo candidato divisore.
• Anche 231 è multiplo di 3: si ottiene ${\displaystyle 231=3\cdot 77}$, e quindi ${\displaystyle p=2\cdot 3^{2}\cdot 77.}$ Continuare con 77, e 3 come primo candidato divisore.
• 77 non è multiplo di 3, perché la somma delle cifre è 14 che non è multiplo di 3. Non è neanche multiplo di 5 perché la cifra delle unità è 7. Il prossimo divisore da cercare è perciò 7. Si ottiene ${\displaystyle 77=7\cdot 11,}$ e quindi ${\displaystyle p=2\cdot 3^{2}\cdot 7\cdot 11.}$ Si verifica facilmente che 7 è primo. Continuare con 11, e 7 come primo candidato divisore.
• Siccome ${\displaystyle 7^{2}>11,}$ il processo è terminato. Perciò 11 è primo, e la fattorizzazione completa in primi risulta

${\displaystyle 1386=2\cdot 3^{2}\cdot 7\cdot 11.}$

Espressioni

La manipolazione delle espressioni è alla base dell'algebra. La fattorizzazione è uno dei più importanti metodi di manipolazione delle espressioni per diversi motivi. Se si riesce a rappresentare un'equazione in forma fattorizzata ${\displaystyle E\cdot F=0}$, il problema di risolvere l'equazione si suddivide in due problemi indipendenti (e di solito più facili): ${\displaystyle E=0}$ e ${\displaystyle F=0}$. In una espressione fattorizzata, i fattori sono molto più semplici, e offrono quindi una migliore visione del problema. Per esempio:

${\displaystyle x^{3}-ax^{2}-bx^{2}-cx^{2}+abx+acx+bcx-abc}$

che contiene 16 moltiplicazioni, 4 sottrazioni e 3 addizioni, può essere fattorizzata in un'espressione molto più semplice

${\displaystyle (x-a)(x-b)(x-c),}$

con solo tre moltiplicazioni e tre sottrazioni. Inoltre la forma fattorizzata indica già quali sono le radici ${\displaystyle a,b,c}$ del polinomio.

La fattorizzazione non è sempre possibile, e quando lo è i fattori non sono sempre più semplici. Per esempio, ${\displaystyle x^{10}-1}$ può essere fattorizzato in due fattori irriducibili ${\displaystyle x-1}$ e ${\displaystyle x^{9}+x^{8}+\cdots +x^{2}+x+1.}$

Sono stati sviluppati vari metodi per trovare le fattorizzazioni, alcuni sono descritti più avanti.

La risoluzione di equazioni algebriche può essere vista come un problema di fattorizzazione di polinomi. Infatti il teorema fondamentale dell'algebra può essere espresso come segue: ogni polinomio in ${\displaystyle x}$ di grado ${\displaystyle n}$ con coefficienti complessi può essere fattorizzato in ${\displaystyle n}$ fattori lineari ${\displaystyle x-a_{i},}$ con ${\displaystyle i=1,...,n}$, dove gli ${\displaystyle a_{i}}$ sono le radici del polinomio.^[3] Anche se la struttura della fattorizzazione è nota in questi casi, gli ${\displaystyle x-a_{i}}$, in genere non possono essere calcolati in termini di radicali (cioè mediante radici ${\displaystyle n}$-esime), per il teorema di Abel-Ruffini. In molti casi il meglio che si può fare è calcolare valori approssimati delle radici con appositi algoritmi.

Storia della fattorizzazione delle espressioni

L'uso sistematico di manipolazioni algebriche per semplificare le espressioni (più precisamente le equazioni) può essere datato dal secolo IX, con il testo Breve opera sul calcolo di spostare e raccogliere di al-Khwarizmi che è intitolato con due tipi di manipolazioni.^[4]

Tuttavia, persino per le soluzioni delle equazioni di secondo grado, il metodo di fattorizzazione non era in uso prima del lavoro di Harriot pubblicato nel 1631, dieci anni dopo la sua morte.^[5]

Nel suo libro Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas, Harriot disegna tabelle per l'addizione, sottrazione, moltiplicazione e divisione di monomi, binomi e trinomi. Successivamente, in una seconda sezione, egli imposta l'equazione ${\displaystyle aa-ba+ca=+bc}$ e mostra che essa ha la forma di una moltiplicazione precedentemente indicata, dando la sua fattorizzazione ${\displaystyle (a-b)(a+c)}$.^[6]

Metodi generali

I seguenti metodi si applicano a qualsiasi espressione fatta di somme o che può essere trasformata in somme. Quindi essi sono applicati spesso ai polinomi, anche quando i termini delle somme non sono monomi, ma prodotti di variabili e costanti.

Fattori comuni

Può verificarsi il caso che tutti i termini della somma siano costituiti da prodotti e che alcuni fattori siano comuni a tutti i termini. In questo caso la proprietà distributiva permette il loro raccoglimento a fattor comune totale. Se ci sono diversi fattori comuni, conviene raccogliere a fattor comune il loro massimo comun divisore (MCD).

Per esempio,^[7]

${\displaystyle 6x^{3}y^{2}+8x^{4}y^{3}-10x^{5}y^{3}=2x^{3}y^{2}(3+4xy-5x^{2}y)}$

poiché 2 è l'MCD di 6, 8, 10, e ${\displaystyle x^{3}y^{2}}$ divide tutti i termini.

Raggruppamento

Il raggruppamento di termini permette di usare altri metodi di fattorizzazione.

Ad esempio, per fattorizzare

${\displaystyle 4x^{2}+20x+3xy+15y,}$

si nota che i primi due termini hanno in comune il fattore ${\displaystyle x}$, e gli ultimi due hanno in comune il fattore ${\displaystyle y}$. Quindi

${\displaystyle 4x^{2}+20x+3xy+15y=(4x^{2}+20x)+(3xy+15y)=4x(x+5)+3y(x+5).}$

Poi risulta evidente il fattore in comune ${\displaystyle x+5,}$ e quindi

${\displaystyle 4x^{2}+20x+3xy+15y=(4x+3y)(x+5).}$

In generale, questo metodo funziona per somme di quattro termini che sono il risultato del prodotto di due binomi. In qualche caso, non frequente, anche in esempi più complicati.

Addizione e sottrazione di termini

Qualche volta il raggruppamento di alcuni termini appare come parte di un prodotto notevole. In questo caso è utile aggiungere i termini mancanti e nello stesso tempo sottrarli per non alterare il valore dell'espressione. Un tipico uso è il metodo del completamento del quadrato per ottenere una forma quadratica.

Un altro esempio è la fattorizzazione di ${\displaystyle x^{4}+1}$. Se si introduce l'unità immaginaria ${\displaystyle {\sqrt {-1}}}$, comunemente denotata con ${\displaystyle i}$, si ottiene una differenza di quadrati

${\displaystyle x^{4}+1=(x^{2}+i)(x^{2}-i).}$

Nel caso si volesse anche una fattorizzazione con coefficienti reali, si può aggiungere e sottrarre ${\displaystyle 2x^{2}}$. Raggruppando tre termini si può riconoscere il quadrato di un binomio

${\displaystyle x^{4}+1=(x^{4}+2x^{2}+1)-2x^{2}=(x^{2}+1)^{2}-(x{\sqrt {2}})^{2}=(x^{2}+x{\sqrt {2}}+1)(x^{2}-x{\sqrt {2}}+1).}$

Inoltre, sottraendo e aggiungendo ${\displaystyle 2x^{2}}$ si ottiene la fattorizzazione

${\displaystyle x^{4}+1=(x^{4}-2x^{2}+1)+2x^{2}=(x^{2}-1)^{2}+(x{\sqrt {2}})^{2}=(x^{2}+x{\sqrt {-2}}-1)(x^{2}-x{\sqrt {-2}}-1).}$

Queste fattorizzazioni funzionano non solo con i numeri complessi, ma anche per ogni campo di numeri, ove uno dei valori -1, 2, -2 sia un quadrato. In un campo finito, il prodotto di due numeri, che non siano dei quadrati, è un quadrato; ciò implica che il polinomio ${\displaystyle x^{4}+1}$, che è irriducibile nel campo degli interi, diventa riducibile modulo un primo. Per esempio,

${\displaystyle x^{4}+1\equiv (x+1)^{4}{\pmod {2}};}$

${\displaystyle x^{4}+1\equiv (x^{2}+x-1)(x^{2}-x-1){\pmod {3}},\qquad }$ poiché ${\displaystyle 1^{2}\equiv -2{\pmod {3}};}$

${\displaystyle x^{4}+1\equiv (x^{2}+2)(x^{2}-2){\pmod {5}},\qquad }$poiché ${\displaystyle 2^{2}\equiv -1{\pmod {5}};}$

${\displaystyle x^{4}+1\equiv (x^{2}+3x+1)(x^{2}-3x+1){\pmod {7}},\qquad }$ poiché ${\displaystyle 3^{2}\equiv 2{\pmod {7}}.}$

Prodotti notevoli

Molte identità rappresentano un'uguaglianza tra una somma e un prodotto. I precedenti metodi possono mettere in evidenza la parte somma di un'identità che quindi può essere sostituita con il suo prodotto.

Di seguito sono riportate identità in forma generalizzata (tramite le variabili ${\displaystyle E}$ e ${\displaystyle F}$ rappresentanti parti dell'espressione originale da fattorizzare).^[8]

• Differenza tra due quadrati

${\displaystyle E^{2}-F^{2}=(E+F)(E-F)}$

Per esempio,

${\displaystyle {\begin{aligned}a^{2}+&2ab+b^{2}-x^{2}+2xy-y^{2}\\&=(a^{2}+2ab+b^{2})-(x^{2}-2xy+y^{2})\\&=(a+b)^{2}-(x-y)^{2}\\&=(a+b+x-y)(a+b-x+y).\end{aligned}}}$

• Somma/differenza di due cubi

${\displaystyle E^{3}+F^{3}=(E+F)(E^{2}-EF+F^{2})}$

${\displaystyle E^{3}-F^{3}=(E-F)(E^{2}+EF+F^{2})}$

• Differenza di due potenze di quarto grado

${\displaystyle {\begin{aligned}E^{4}-F^{4}&=(E^{2}+F^{2})(E^{2}-F^{2})\\&=(E^{2}+F^{2})(E+F)(E-F)\end{aligned}}}$

• Somma/differenza di due valori all'${\displaystyle n}$-esima potenza

Nelle seguenti identità i fattori sono spesso a loro volta fattorizzabili.

• Differenza con esponente pari

${\displaystyle E^{2n}-F^{2n}=(E^{n}+F^{n})(E^{n}-F^{n})}$

• Differenza, con qualsiasi esponente

${\displaystyle E^{n}-F^{n}=(E-F)(E^{n-1}+E^{n-2}F+E^{n-3}F^{2}+\cdots +EF^{n-2}+F^{n-1})}$

Questo è un esempio di fattori più numerosi della somma da fattorizzare.

• Somma con esponente dispari

${\displaystyle E^{n}+F^{n}=(E+F)(E^{n-1}-E^{n-2}F+E^{n-3}F^{2}-\cdots -EF^{n-2}+F^{n-1})}$

(ottenuta scambiando ${\displaystyle F}$ con ${\displaystyle -F}$ nella precedente formula)

• Somma con esponente pari

Se l'esponente è una potenza di 2, l'espressione non può, in generale, essere fattorizzata senza usare numeri complessi (se ${\displaystyle E}$ e ${\displaystyle F}$ contengono numeri complessi potrebbe non essere vero). Se ${\displaystyle n}$ ha un divisore dispari, cioè se ${\displaystyle n=pq}$ con ${\displaystyle p}$ dispari, si può

usare la formula precedente ("Somma con esponente dispari") e applicarla a ${\displaystyle (E^{q})^{p}+(F^{q})^{p}.}$

• Trinomi e formule cubiche

${\displaystyle {\begin{aligned}&x^{2}+y^{2}+z^{2}+2(xy+yz+xz)=(x+y+z)^{2}\\&x^{3}+y^{3}+z^{3}-3xyz=(x+y+z)(x^{2}+y^{2}+z^{2}-xy-xz-yz)\\&x^{3}+y^{3}+z^{3}+3x^{2}(y+z)+3y^{2}(x+z)+3z^{2}(x+y)+6xyz=(x+y+z)^{3}\\&x^{4}+x^{2}y^{2}+y^{4}=(x^{2}+xy+y^{2})(x^{2}-xy+y^{2}).\end{aligned}}}$

• Sviluppi binomiali

Nel teorema binomiale ci sono delle forme facilmente riconoscibili in base ai numeri interi presenti di grado piccolo:

${\displaystyle a^{2}+2ab+b^{2}=(a+b)^{2}}$

${\displaystyle a^{2}-2ab+b^{2}=(a-b)^{2}}$

${\displaystyle a^{3}+3a^{2}b+3ab^{2}+b^{3}=(a+b)^{3}}$

${\displaystyle a^{3}-3a^{2}b+3ab^{2}-b^{3}=(a-b)^{3}}$

In generale, i coefficienti degli sviluppi di ${\displaystyle (a+b)^{n}}$ e ${\displaystyle (a-b)^{n}}$ sono i coefficienti binomiali, che appaiono nella ${\displaystyle n}$-esima riga del triangolo di Pascal.

Radici dell'unità

Le radici ${\displaystyle n}$-esime dell'unità sono quei numeri complessi ciascuno dei quali è la radice del polinomio ${\displaystyle x^{n}-1.}$. Essi sono perciò i numeri

${\displaystyle e^{2ik\pi /n}=\cos {\tfrac {2\pi k}{n}}+i\sin {\tfrac {2\pi k}{n}},}$

per ${\displaystyle k=0,\ldots ,n-1.}$

Dal cui segue che per ogni coppia di espressioni ${\displaystyle E}$ e ${\displaystyle F}$, si ha:

${\displaystyle E^{n}-F^{n}=(E-F)\prod _{k=1}^{n-1}\left(E-Fe^{2ik\pi /n}\right);}$

${\displaystyle E^{n}+F^{n}={\begin{cases}\displaystyle \prod _{k=0}^{n-1}\left(E-Fe^{(2k+1)\pi /n}\right),&{\text{se }}n{\text{ è pari}},\\\displaystyle (E+F)\prod _{k=1}^{n-1}\left(E+Fe^{2ik\pi /n}\right),&{\text{se }}n{\text{ è dispari}}.\end{cases}}}$

Se ambedue sono espressioni reali, e si desiderano fattori reali, occorre rimpiazzare ogni coppia di fattori complessi coniugati con i suoi prodotti. Poiché il complesso coniugato di ${\displaystyle e^{i\alpha }}$ è ${\displaystyle e^{-i\alpha },}$ e

${\displaystyle \left(a-be^{i\alpha }\right)\left(a-be^{-i\alpha }\right)=a^{2}-ab\left(e^{i\alpha }+e^{-i\alpha }\right)+b^{2}e^{i\alpha }e^{-i\alpha }=a^{2}-2ab\cos \alpha +b^{2},}$

si hanno le seguenti fattorizzazioni reali (si passa dall'una all'altra sostituendo ${\displaystyle k}$ con ${\displaystyle n-k}$ o con ${\displaystyle n+1-k}$, e applicando le solite formule trigonometriche:

${\displaystyle E^{2n}-F^{2n}=(E-F)(E+F)\prod _{k=1}^{n-1}\left(E^{2}-2EF\cos \,{\tfrac {k\pi }{n}}+F^{2}\right)=(E-F)(E+F)\prod _{k=1}^{n-1}\left(E^{2}+2EF\cos \,{\tfrac {k\pi }{n}}+F^{2}\right);}$

${\displaystyle E^{2n}+F^{2n}=\prod _{k=1}^{n}\left(E^{2}+2EF\cos \,{\tfrac {(2k-1)\pi }{2n}}+F^{2}\right)=\prod _{k=1}^{n}\left(E^{2}-2EF\cos \,{\tfrac {(2k-1)\pi }{2n}}+F^{2}\right).}$

I coseni che appaiono in queste fattorizzazioni sono numeri algebrici, che possono essere espressi in termini di radicali (possibile in quanto il loro gruppo di Galois è ciclico); tuttavia, queste espressioni radicali sono troppo complicate da usare, con l'eccezione per piccoli valori di ${\displaystyle n}$. Per esempio:

${\displaystyle a^{4}+b^{4}=(a^{2}-{\sqrt {2}}ab+b^{2})(a^{2}+{\sqrt {2}}ab+b^{2});}$

${\displaystyle a^{5}-b^{5}=(a-b)\left(a^{2}+{\frac {1-{\sqrt {5}}}{2}}ab+b^{2}\right)\left(a^{2}+{\frac {1+{\sqrt {5}}}{2}}ab+b^{2}\right);}$

${\displaystyle a^{5}+b^{5}=(a+b)\left(a^{2}-{\frac {1-{\sqrt {5}}}{2}}ab+b^{2}\right)\left(a^{2}-{\frac {1+{\sqrt {5}}}{2}}ab+b^{2}\right).}$

Spesso si desidera una fattorizzazione con coefficienti razionali. Esse implicano polinomi ciclotomici. Per ottenere fattorizzazioni razionali di somme e differenze o di potenze, è necessaria una notazione per l'omogeneizzazione di un polinomio: se ${\displaystyle P(x)=a_{0}x^{n}+a_{i}x^{n-1}+\cdots +a_{n}}$, la sua omogeneizzazione è il polinomio a due variabili ${\displaystyle {\overline {P}}(x,y)=a_{0}x^{n}+a_{i}x^{n-1}y+\cdots +a_{n}y^{n}}$. Allora si ottiene

${\displaystyle E^{n}-F^{n}=\prod _{k\mid n}{\overline {Q}}_{n}(E,F),}$

${\displaystyle E^{n}+F^{n}=\prod _{k\mid 2n,k\not \mid n}{\overline {Q}}_{n}(E,F),}$

dove i prodotti si riferiscono a tutti i divisori di ${\displaystyle n}$, o di ${\displaystyle 2n}$ che non sono divisori di ${\displaystyle n}$, e ${\displaystyle Q_{n}(x)}$ è l'${\displaystyle n}$-esimo polinomio ciclotomico.

Per esempio:

${\displaystyle a^{6}-b^{6}={\overline {Q}}_{1}(a,b){\overline {Q}}_{2}(a,b){\overline {Q}}_{3}(a,b){\overline {Q}}_{6}(a,b)=(a-b)(a+b)(a^{2}-ab+b^{2})(a^{2}+ab+b^{2}),}$

${\displaystyle a^{6}+b^{6}={\overline {Q}}_{4}(a,b){\overline {Q}}_{12}(a,b)=(a^{2}+b^{2})(a^{4}-a^{2}b^{2}+b^{4}),}$

poiché i divisori di 6 sono 1,2,3,6, e i divisori di 12 che non dividono 6 sono 4 e 12.

Polinomi

Per i polinomi la fattorizzazione è strettamente legata al problema della soluzione di una equazione algebrica. Un'equazione algebrica ha la forma

${\displaystyle P(x)\ \,{\stackrel {\text{def}}{=}}\ \,a_{0}x^{n}+a_{1}x^{n-1}+\cdots +a_{n}=0,}$

dove ${\displaystyle P(x)}$ è un polinomio in ${\displaystyle x}$ con ${\displaystyle a_{0}\neq 0}$. Una soluzione di questa equazione (chiamata anche radice del polinomio) è un valore ${\displaystyle r}$ di ${\displaystyle x}$ tale che

${\displaystyle P(r)=0.}$

Se ${\displaystyle P(x)=Q(x)R(x)}$ è una fattorizzazione di ${\displaystyle P(x)=0}$ come prodotto di due polinomi, allora le radici di ${\displaystyle P(x)}$ sono l'unione delle radici di ${\displaystyle Q(x)}$ e quelle di ${\displaystyle R(x)}$. Per cui la soluzione di ${\displaystyle P(x)=0}$ è ridotta ai più semplici problemi di risolvere ${\displaystyle Q(x)=0}$ e ${\displaystyle R(x)=0}$.

All'opposto, il teorema del fattore asserisce che se ${\displaystyle r}$ è una radice di ${\displaystyle P(x)=0}$, allora ${\displaystyle P(x)}$ può essere fattorizzato come

${\displaystyle P(x)=(x-r)Q(x),}$

dove ${\displaystyle Q(x)}$ è il quoziente di una divisione euclidea (vedi regola di Ruffini) di ${\displaystyle P(x)=0}$ per il fattore lineare ${\displaystyle x-r}$.

Se i coefficienti di ${\displaystyle P(x)}$ sono reali o complessi, il teorema fondamentale dell'algebra afferma che ${\displaystyle P(x)}$ ha una radice reale o complessa. Utilizzando ricorsivamente il teorema del fattore, risulta che

${\displaystyle P(x)=a_{0}(x-r_{1})\cdots (x-r_{n}),}$

dove ${\displaystyle r_{1},\ldots ,r_{n}}$ sono le radici reali o complesse di ${\displaystyle P}$, con alcune di esse anche ripetute. Tale fattorizzazione completa è unica.

Se i coefficienti di ${\displaystyle P(x)}$ sono reali, in generale si preferisce che anche la fattorizzazione abbia coefficienti reali. In questo caso, nella fattorizzazione completa possono esserci fattori quadratici. Questa fattorizzazione può facilmente essere dedotta dalla fattorizzazione completa precedente. Infatti, se ${\displaystyle r=a+ib}$ è una radice non reale di ${\displaystyle P(x)}$, allora il suo complesso coniugato ${\displaystyle s=a-ib}$ è anch'esso una radice di ${\displaystyle P(x)}$. Per cui, il prodotto

${\displaystyle (x-r)(x-s)=x^{2}-(r+s)x+rs=x^{2}+2ax+a^{2}+b^{2}}$

è un fattore di ${\displaystyle P(x)}$ con coefficienti reali. Ripetendo l'operazione per tutti i fattori non reali si ottiene una fattorizzazione con fattori reali lineari o quadratici.

Per calcolare questi fattori, reali o complessi, occorre trovare le radici del polinomio, che possono non essere esatte, ma solo approssimate tramite algoritmi di calcolo delle radici.

In pratica, molte equazioni algebriche di interesse hanno coefficienti interi o razionali e si desidera lo stesso per la fattorizzazione. Il teorema fondamentale dell'aritmetica può essere generalizzato a questo caso, in quanto i polinomi con coefficienti interi o razionali hanno anch'essi la proprietà di avere un'unica fattorizzazione. Più precisamente, ogni polinomio con coefficienti razionali può essere fattorizzato nel prodotto

${\displaystyle P(x)=q\,P_{1}(x)\cdots P_{k}(x),}$

dove ${\displaystyle q}$ è un numero razionale e ${\displaystyle P_{1}(x),\ldots ,P_{k}(x)}$ sono polinomi variabili a coefficienti interi che sono polinomi irriducibili e primitivi; ciò significa che nessuno dei ${\displaystyle P_{i}(x)}$ può essere scritto come prodotto di due polinomi (con coefficienti interi) che non siano 1 o -1 (gli interi sono considerati come polinomi di grado zero). Inoltre, questa fattorizzazione è unica a meno dell'ordine e del segno dei fattori.

Ci sono efficienti algoritmi per calcolare le fattorizzazioni, utilizzati dalla maggior parte dei calcolatori algebrici. Si veda scomposizione dei polinomi. Sfortunatamente questi algoritmi sono troppo complicati da utilizzare sulla carta. A parte il calcolo euristico sopra accennato, solo pochi metodi si prestano a un calcolo manuale, e sono per polinomi di grado minore, con pochi coefficienti maggiori di zero. I principali di questi metodi sono descritti qui di seguito.

Fattorizzazione in parte primitiva e contenuto

Ogni polinomio a coefficienti razionali può essere fattorizzato in un unico modo come prodotto di un numero razionale e un polinomio a coefficienti interi primitivo (cioè l'MCD dei coefficienti è 1) e ha un coefficiente positivo iniziale (coefficiente del termine con il grado più elevato). Ad esempio:

${\displaystyle -10x^{2}+5x+5=(-5)\cdot (2x^{2}-x-1),}$

${\displaystyle {\frac {1}{3}}x^{5}+{\frac {7}{2}}x^{2}+2x+1={\frac {1}{6}}(2x^{5}+21x^{2}+12x+6).}$

In questa fattorizzazione, il numero razionale è detto contenuto e il polinomio primitivo è detto parte primitiva. Il calcolo di questa fattorizzazione può essere fatto come segue:

1. Ridurre i coeficienti a un comune denominatore, per ottenere il quoziente intero ${\displaystyle q}$ di un polinomio a coefficienti interi.
2. Raccogliere a fattore comune l'MCD ${\displaystyle p}$ dei coefficienti di questo polinomio per ottenere la parte primitiva, essendo il contenuto ${\displaystyle p/q}$.
3. Se necessario, cambiare di segno ${\displaystyle p}$ e tutti i coefficienti della parte primitiva.

Questa fattorizzazione può portare a un'espressione più estesa di quella originale (tipicamente quando ci sono molti denominatori interi coprimi), ma ciò nonostante la parte primitiva è generalmente più facile da manipolare per ulteriori fattorizzazioni.

Utilizzo del teorema del fattore

Il teorema del fattore afferma che se ${\displaystyle r}$ è una radice di un polinomio

${\displaystyle P(x)=a_{0}x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n},}$

con ${\displaystyle P(r)=0}$, allora esiste una fattorizzazione

${\displaystyle P(x)=(x-r)Q(x),}$

dove

${\displaystyle Q(x)=b_{0}x^{n-1}+\cdots +b_{n-2}x+b_{n-1},}$

con ${\displaystyle a_{0}=b_{0}}$. Il risultato della divisione lunga di un polinomio o quella sintetica è allora:

${\displaystyle b_{i}=a_{0}r^{i}+\cdots +a_{i-1}r+a_{i}\ {\text{ for }}\ i=1,\ldots ,n{-}1.}$

Tutto questo può essere utile quando si conosce o si intuisce qual è la radice del polinomio.

Ad esempio, per ${\displaystyle P(x)=x^{3}-3x+2,}$ si può facilmente vedere che la somma dei coefficienti è 0, per cui ${\displaystyle r=1}$ è la radice. Siccome ${\displaystyle r+0=1}$ e ${\displaystyle r^{2}+0r-3=-2}$, si ha

${\displaystyle x^{3}-3x+2=(x-1)(x^{2}+x-2).}$

Radici razionali

Nel caso dei polinomi con coefficienti razionali, è possibile cercare le sue radici razionali. La fattorizzazione in parte primitiva e contenuto riduce il problema della ricerca di radici razionali al caso di polinomi a coefficienti interi aventi un massimo comundivisore uguale a 1.

Se ${\displaystyle x={\tfrac {p}{q}}}$ è una radice razionale del polinomio

${\displaystyle P(x)=a_{0}x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n},}$

il teorema del fattore mostra che si ha la fattorizzazione

${\displaystyle P(x)=(qx-p)Q(x),}$

dove entrambi i fattori hanno coefficienti interi. Il fatto che ${\displaystyle Q}$ abbia coefficienti interi deriva dalla formula sopraccitata del quoziente di ${\displaystyle P(x)}$ diviso per ${\displaystyle x-p/q}$.

Confrontando i coefficienti di grado ${\displaystyle n}$ con i coefficienti costanti dell'uguaglianza sopra, si nota che se ${\displaystyle {\tfrac {p}{q}}}$ è una radice razionale, in forma ridotta, allora ${\displaystyle q}$ è un divisore di ${\displaystyle a_{0}}$ e ${\displaystyle p}$ è un divisore di ${\displaystyle a_{n}}$ (teorema delle radici razionali). Di conseguenza, ci sono solo un numero finito di possibilità per ${\displaystyle p}$ e ${\displaystyle q}$, che possono essere esaminate sistematicamente.^[9]

Ad esempio, se il polinomio

${\displaystyle P(x)=2x^{3}-7x^{2}+10x-6}$

ha radici razionali ${\displaystyle {\tfrac {p}{q}}}$ con ${\displaystyle q>0}$, allora ${\displaystyle p}$ deve dividere 6, cioè ${\displaystyle p\in \{\pm 1,\pm 2,\pm 3,\pm 6\},}$ e ${\displaystyle q}$ deve dividere 2, quindi ${\displaystyle q\in \{1,2\}}$. Inoltre, se ${\displaystyle x<0}$, i termini del polinomio sono negativi, perciò una radice non può essere negativa. Si deve quindi avere

${\displaystyle {\tfrac {p}{q}}\in \{1,2,3,6,{\tfrac {1}{2}},{\tfrac {3}{2}}\}.}$

Un calcolo diretto mostra che solo ${\displaystyle {\tfrac {3}{2}}}$ è una radice, quindi non possono esserci altre radici razionali. Applicando il teorema del fattore si arriva alla fattorizzazione finale

${\displaystyle 2x^{3}-7x^{2}+10x-6=(2x-3)(x^{2}-2x+2).}$

Metodo quadratico AC

Questo metodo può essere adatto ai polinomi quadratici detto metodo AC di fattorizzazione.^[10]

Si consideri il polinomio quadratico

${\displaystyle P(x)=ax^{2}+bx+c}$

con coefficienti interi. Se ha una radice razionale, il suo denominatore deve essere un divisore di ${\displaystyle a}$ e può essere scritto come una frazione riducibile ${\displaystyle {\tfrac {r}{a}}}$. Tramite le formule di Viète, l'altra radice è

${\displaystyle -{\frac {b}{a}}-{\frac {r}{a}}=-{\frac {b+r}{a}}={\frac {s}{a}}}$

con ${\displaystyle s=-(b+r)}$. Quindi anche la seconda radice è razionale, e la seconda formula di Viète porta a

${\displaystyle {\frac {s}{a}}{\frac {r}{a}}={\frac {c}{a}},}$

cioè

${\displaystyle rs=ac,\quad {\text{e}}\quad r+s=-b.}$

Controllando tutte le coppie di interi il cui prodotto è ${\displaystyle ac}$ si ottengono, se esistono, le radici razionali.

Ad esempio, consideriamo il polinomio quadratico

${\displaystyle 6x^{2}+13x+6.}$

Analizzando i possibili fattori di ${\displaystyle ac=36}$ si trova che ${\displaystyle 4+9=13=b}$, che danno le radici

${\displaystyle -{\frac {4}{6}}=-{\frac {2}{3}}\quad {\text{e}}\quad -{\frac {9}{6}}=-{\frac {3}{2}}}$

e la fattorizzazione

${\displaystyle 6x^{2}+13x+6=6(x+{\tfrac {2}{3}})(x+{\tfrac {3}{2}})=(3x+2)(2x+3).}$

Utilizzo di formule per le radici dei polinomi

Qualsiasi polinomio quadratico a un'incognita ${\displaystyle ax^{2}+bx+c}$ può essere fattorizzato con la formula quadratica:

${\displaystyle ax^{2}+bx+c=a(x-\alpha )(x-\beta )=a\left(x-{\frac {-b+{\sqrt {b^{2}-4ac}}}{2a}}\right)\left(x-{\frac {-b-{\sqrt {b^{2}-4ac}}}{2a}}\right),}$

dove ${\displaystyle \alpha }$ e ${\displaystyle \beta }$ sono le due radici del polinomio.

Se ${\displaystyle a,b,c}$ sono variabili reali, i fattori sono anch'essi reali se e solo se il discriminante ${\displaystyle b^{2}-4ac}$ è positivo. Altrimenti, il polinomio non può essere fattorizzato in fattori reali variabili.

La formula è valida quando i coefficienti appartengono a una caratteristica del campo numerico diversa da due, e in particolare, per coefficienti di un campo finito con un numero dispari di elementi.^{[N 1]}

Ci sono pure formule per le radici dei polinomi cubici e quartici che sono, in generale, troppo complicate per un uso pratico. Il teorema di Abel-Ruffini afferma che non possono esserci formule generali per le radici di polinomi di grado cinque o superiore.

Utilizzo delle relazioni tra radici

Può capitare che si conosca qualche relazione tra le radici di un polinomio e i suoi coefficienti. L'uso di questa conoscenza può aiutare il lavoro di fattorizzazione del polinomio e la ricerca delle sue radici. La teoria di Galois è basata su uno studio sistematico di queste relazioni che includono le formule di Viète.

Qui ci limitiamo a considerare il caso più semplice di due radici ${\displaystyle x_{1}}$ e ${\displaystyle x_{2}}$ di un polinomio ${\displaystyle P(x)}$che soddisfa la relazione

${\displaystyle x_{2}=Q(x_{1}),}$

dove ${\displaystyle Q}$ è un polinomio.

Questo implica che ${\displaystyle x_{1}}$ è una radice comune a ${\displaystyle P(Q(x))}$ e ${\displaystyle P(x)}$, è quindi una radice del polinomio MCD di questi due polinomi. Da ciò segue che questo MCD è un fattore variabile di ${\displaystyle P(x).}$La divisione dei polinomi consente il calcolo dell'MCD.

Ad esempio,^[11] se si conosce o si intuisce che: ${\displaystyle P(x)=x^{3}-5x^{2}-16x+80}$ ha due radici la cui somma è zero, si può applicare l'algoritmo euclideo a ${\displaystyle P(x)}$ e ${\displaystyle P(-x)}$. Il primo passo della divisione consiste nell'aggiungere ${\displaystyle P(x)}$ a ${\displaystyle P(-x)}$ ottenendo il resto di

${\displaystyle -10(x^{2}-16).}$

Poi, dividendo ${\displaystyle P(x)}$ per ${\displaystyle x^{2}-16}$ ottenendo zero come nuovo resto, e ${\displaystyle x-5}$ come quoziente, arrivando così alla completa fattorizzazione

${\displaystyle x^{3}-5x^{2}-16x+80=(x-5)(x-4)(x+4).}$

Domini a fattorizzazione unica

Gli interi e i polinomi di un campo condividono la proprietà della fattorizzazione unica, cioè, ogni elemento diverso da zero può essere fattorizzato in un prodotto di un elemento invertibile (una unità, ${\displaystyle \pm 1}$ nel caso degli interi) e un prodotto di elementi irriducibili (numeri primi nel caso degli interi), e questa fattorizzazione è unica a meno dell'ordine degli elementi e dello spostamento delle unità tra i fattori. I domini di integrità che condividono questa proprietà sono detti domini a fattorizzazione unica (UFD).

L'MCD esiste negli UFD, e di converso, ogni dominio di integrità, nei quali esiste l'MCD, è un UFD. Ogni dominio ad ideali principali è un UFD.

Un dominio euclideo è un dominio di integrità nel quale è definita una divisione euclidea simile a quella degli interi. Ogni dominio euclideo è un dominio di ideali principale, e perciò un UFD.

In un dominio euclideo, la divisione euclidea consente la definizione di un algoritmo euclideo per il calcolo dell'MCD. Tuttavia, ciò non implica l'esistenza di un algoritmo di fattorizzazione. C'è un esempio esplicito di un campo ${\displaystyle F}$ in cui non può esistere qualsiasi algoritmo di fattorizzazione nel dominio euclideo ${\displaystyle F[x]}$ dei polinomi a una incognita di ${\displaystyle F}$.

Ideali

Nella teoria dei numeri algebrici, lo studio delle equazioni diofantee indusse i matematici, durante il XIX secolo, a introdurre una generalizzazione dei numeri interi detti interi algebrici. Il primo anello di interi algebrici preso in considerazione fu l'intero gaussiano e l'intero di Eisenstein, che condividono con gli interi usuali la proprietà di essere dominio ad ideali principali, aventi perciò la proprietà della fattorizzazione unica.

Sfortunatamente, la maggior parte degli algebrici interi si rivelarono subito come non principali e senza una fattorizzazione unica. Il più semplice di essi è ${\displaystyle \mathbb {Z} [{\sqrt {-5}}],}$ nel quale

${\displaystyle 9=3\cdot 3=(2+{\sqrt {-5}})(2-{\sqrt {-5}}),}$

e tutti questi generi di fattori sono irriducibili.

Questa mancanza di un'unica fattorizzazione è una delle maggiori difficoltà per la soluzione delle equazioni diofantee. Per esempio, molte dimostrazioni errate dell'ultimo teorema di Fermat (probabilmente quelle dello stesso Pierre de Fermat) erano basate sull'implicita ipotesi della fattorizzazione unica.

Questa difficoltà fu risolta da Dedekind, che dimostrò che gli anelli degli interi algebrici hanno un'unica fattorizzazione in ideali: in questi anelli ogni ideale è il prodotto di primi ideali, e questa fattorizzazione è unica. I domini di integrità che possiedono questa proprietà di fattorizzazione unica sono ora detti domini di Dedekind. Essi hanno molte proprietà interessanti che li rendono fondamentali nella teoria dei numeri algebrici.

Matrici

Gli anelli di matrici sono non commutativi e non hanno un'unica fattorizzazione: ci sono, in generale, molti modi di scrivere una matrice come prodotto di matrici. Per cui il problema della fattorizzazione consiste nel trovare fattori di un tipo specifico. Per esempio, la decomposizione LU porta a una matrice risultante dal prodotto di una matrice triangolare inferiore (L) per una matrice triangolare superiore (U). Siccome ciò non è sempre possibile, in generale, si prova la decomposizione LUP avente una matrice di permutazione come terzo fattore.

Si veda la decomposizione di una matrice per i tipi più comuni di fattorizzazione di matrici.

Una matrice logica rappresenta una relazione binaria, e la moltiplicazione di matrici corrisponde a una composizione di relazioni. Scomporre una relazione tramite fattorizzazione serve a dare un profilo alla natura della relazione, come per esempio una relazione difunzionale.

Note

Annotazioni

Fonti

Voci correlate

• Metodo di fattorizzazione di Eulero
• Metodo di fattorizzazione di Fermat

Altri progetti

• Wikizionario contiene il lemma di dizionario «fattorizzazione»

Collegamenti esterni

• fattorizzazione, in Dizionario delle scienze fisiche, Istituto dell'Enciclopedia Italiana, 1996.
• fattorizzazione, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Fattorizzazione, su MathWorld, Wolfram Research.
• (EN) Fattorizzazione, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.

Controllo di autorità	Thesaurus BNCF 30495 · LCCN (EN) sh85046844 · BNF (FR) cb122865337 (data) · J9U (EN, HE) 987007565462605171