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 è una fattorizzazione dell'intero . Invece è una fattorizzazione del polinomio
La fattorizzazione non è generalmente considerata significativa negli insiemi numerici aventi un'operazione di divisione, come i numeri reali o quelli complessi, poiché qualsiasi può essere scritto banalmente come per ogni 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 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 , avente tutti gli elementi della diagonale uguali a 1, per una matrice triangolare superiore , e per una matrice di permutazione . 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 , occorre un algoritmo per trovare un divisore di a meno che sia primo. Nel caso che si sia trovato un divisore, la ripetizione dell'algoritmo ai fattori e / si concluderà alla fine con il completamento della fattorizzazione di .
Per trovare un divisore di , se esiste, è sufficiente verificare tutti i valori di tali che e . Infatti, se è un divisore di e , allora è un divisore di tale che .
Se si provano i valori di in ordine crescente, il primo divisore trovato è necessariamente un numero primo, e il cofattore non può avere un divisore minore di . Per ottenere la completa fattorizzazione, è perciò sufficiente ripetere l'algoritmo cercando un divisore di non minore di e non maggiore di .
Non occorre verificare tutti i valori di 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 , che abbiano come cifra delle unità 1,3,7,9 e che la somma delle cifre di 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
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 in un prodotto di primi:
Iniziare con la divisione per 2 (n è pari) e . Continuare con 693, e 2 come primo candidato divisore. 693 è dispari (2 non è un suo divisore), ma è multiplo di 3: si ottiene e Continuare con 231, e 3 come primo candidato divisore. Anche 231 è multiplo di 3: si ottiene , e quindi 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 e quindi Si verifica facilmente che 7 è primo. Continuare con 11, e 7 come primo candidato divisore. Siccome il processo è terminato. Perciò 11 è primo, e la fattorizzazione completa in primi risulta
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 , il problema di risolvere l'equazione si suddivide in due problemi indipendenti (e di solito più facili): e . In una espressione fattorizzata, i fattori sono molto più semplici, e offrono quindi una migliore visione del problema. Per esempio:
che contiene 16 moltiplicazioni, 4 sottrazioni e 3 addizioni, può essere fattorizzata in un'espressione molto più semplice
con solo tre moltiplicazioni e tre sottrazioni. Inoltre la forma fattorizzata indica già quali sono le radici del polinomio.
La fattorizzazione non è sempre possibile, e quando lo è i fattori non sono sempre più semplici. Per esempio, può essere fattorizzato in due fattori irriducibili e
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 di grado con coefficienti complessi può essere fattorizzato in fattori lineari con , dove gli sono le radici del polinomio. Anche se la struttura della fattorizzazione è nota in questi casi, gli , in genere non possono essere calcolati in termini di radicali (cioè mediante radici -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.L’algebra nella matematica islamica – NUOVA STORIA VISUALE – NEW VISUAL HISTORY matematica-islamica/
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.In , l'autore nota "Vista la presente enfasi data alla soluzione delle equazioni quadratiche mediante fattorizzazione, è interessante notare che questo metodo non era in uso prima del lavoro del 1631 di Harriot".
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 e mostra che essa ha la forma di una moltiplicazione precedentemente indicata, dando la sua fattorizzazione .
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,
poiché 2 è l'MCD di 6, 8, 10, e divide tutti i termini.
Raggruppamento Il raggruppamento di termini permette di usare altri metodi di fattorizzazione.
Ad esempio, per fattorizzare
si nota che i primi due termini hanno in comune il fattore , e gli ultimi due hanno in comune il fattore . Quindi
Poi risulta evidente il fattore in comune e quindi
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 . Se si introduce l'unità immaginaria , comunemente denotata con , si ottiene una differenza di quadrati
Nel caso si volesse anche una fattorizzazione con coefficienti reali, si può aggiungere e sottrarre . Raggruppando tre termini si può riconoscere il quadrato di un binomio
Inoltre, sottraendo e aggiungendo si ottiene la fattorizzazione
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 , che è irriducibile nel campo degli interi, diventa riducibile modulo un primo. Per esempio,
poiché poiché poiché
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 e rappresentanti parti dell'espressione originale da fattorizzare).