miniatura|Polinomul x² + cx + d, unde a + b = c și ab = d, poate fi factorizat în (x + a)(x + b). În matematică, factorizarea constă în scrierea unui număr sau a altui obiect matematic ca produs de mai mulți factori, de obicei obiecte mai mici sau mai simple de același fel. De exemplu, este o factorizare a întregului , iar este o factorizare a polinomului .
Nu se consideră de obicei că factorizarea ar avea vreo importanță în sistemele de numere care posedă diviziuni, cum ar fi numerele reale sau complexe, deoarece orice poate fi scris trivial ca oricând nu este zero. Totuși, o factorizare semnificativă pentru un număr rațional sau o funcție rațională poate fi obținută prin aducerea la o formă ireductibilă și factorizarea separată a numărătorului și numitorului.
Primii care s-au gândit la conceptul de factorizare au fost în cazul numerelor întregi. Ei au demonstrat teorema fundamentală a aritmeticii, care afirmă că fiecare număr întreg pozitiv poate fi factorizat într-un produs de numere prime, care nu pot fi factorizate mai departe în numere întregi mai mari de 1. Mai mult, această factorizare este unică până la ordinea factorilor. Deși factorizarea întregilor este un fel de operație inversă înmulțirii, ea este mult mai dificilă din punct de vedere algoritmic, fapt care este exploatat în criptosistemul RSA pentru a implementa criptografia cu cheie publică.
este și ea studiată de secole. În algebra elementară, factorizarea unui polinom reduce problema găsirii rădăcinilor sale la găsirea rădăcinilor factorilor. Polinoamele cu coeficienți în mulțimea numerelor întregi sau într-un corp posedă proprietatea de factorizare unică, o versiune a teoremei fundamentale a aritmeticii în care numerele prime sunt înlocuite cu . În special, un polinom univariat cu coeficienți complecși admite o factorizare unică (până la ordonare) în polinoame liniare: aceasta este o versiune a teoremei fundamentale a algebrei. În acest caz, factorizarea se poate face cu . Cazul polinoamelor cu coeficienți întregi este fundamental pentru . Există algoritmi de calcul eficienți pentru calcularea factorizărilor (complete) în cadrul inelului polinoamelor cu coeficienți de număr rațional.
Un inel comutativ care posedă proprietatea de factorizare unică se numește domeniu unic de factorizare. Există sisteme numerice, cum ar fi anumite inele de numere întregi algebrice, care nu sunt domenii de factorizare unică. Totuși, inelele de numere întregi algebrice satisfac proprietatea mai slabă a : idealele se împart în mod unic în ideale prime.
Termenul factorizare se poate referi și la descompuneri mai generale ale unui obiect matematic în produsul unor obiecte mai mici sau mai simple. De exemplu, orice funcție poate fi inclusă în compoziția unei funcții surjective cu o funcție injectivă. Matricele posedă multe tipuri de . De exemplu, fiecare matrice are o unică ca produs al unei matrice inferior triunghiulară cu toate elementele de pe diagonală egale cu unu, cu o matrice superior triunghiulară și o matrice permutare ; aceasta este o formulare matriceală a eliminării gaussiene.
Numere întregi Conform teoremei fundamentale a aritmeticii, fiecare număr întreg mai mare de 1 are o descompunere unică (până la ordinea factorilor) în numere prime, care sunt acele numere întregi ce nu pot fi descompuse în produs de alte numere întregi mai mari de unu.
Pentru a calcula factorizarea unui număr întreg , este nevoie de un algoritm care găsește un divizor al lui sau decide că este prim. Când se găsește un astfel de divizor, aplicarea repetată a acestui algoritm asupra factorilor și dă în cele din urmă factorizarea completă a lui .
Pentru a găsi un divizor al lui , dacă există, este suficient să se testeze toate valorile lui astfel încât și . De fapt, dacă este un divizor al lui astfel încât , atunci este un divizor al lui astfel încât .
Dacă se testează valorile lui în ordine crescătoare, primul divizor care se găsește este cu siguranță un număr prim, iar cofactorul nu poate avea niciun divizor mai mic decât . Pentru a obține factorizarea completă, este suficient să se continue algoritmul prin căutarea unui divizor al lui care nu este mai mic decât și nu mai mare decât .
Nu este nevoie să se testeze toate valorile lui pentru aplicarea metodei. În principiu, este suficientă testarea doar a divizorilor primi. Acesta trebuie să aibă un tabel de numere prime care poate fi generat, de exemplu, cu ciurul lui Eratostene. Deoarece metoda de factorizare efectuează în esență aceeași activitate ca ciurul lui Eratostene, este în general mai eficientă testarea pentru un divizor doar pentru acele numere pentru care nu este imediat clar dacă sunt prime sau nu. De obicei, se poate continua testând 2, 3, 5 și numerele > 5, a căror ultimă cifră este 1, 3, 7, 9 și suma cifrelor nu este un multiplu al lui 3.
Această metodă funcționează bine pentru factorizarea numerelor întregi mici, dar este ineficientă pentru numerele întregi mai mari. De exemplu, Pierre de Fermat nu a putut descoperi că al 6-lea
nu este un număr prim. De fapt, aplicarea metodei de mai sus ar necesita peste de împărțiri, pentru un număr care are 10 cifre zecimale.
Există algoritmi de factorizare mai eficienți. Totuși, ele rămân relativ ineficiente, deoarece, în stadiul actual al tehnicii, nu se poate factoriza, chiar și cu calculatoarele mai puternice, un număr de 500 de cifre zecimale care este produsul a două numere prime alese aleatoriu. Aceasta asigură securitatea criptosistemului RSA, care este utilizat pe scară largă pentru comunicarea securizată prin Internet.
Exemplu Pentru factorizarea în numere prime:
Se începe cu împărțirea la 2: numărul este par și . Se continuă cu 693 și 2 drept candidate ca prim divizor. 693 este impar (2 nu este divizor), dar este multiplu al lui 3: avem și deci . Se continuă cu 231 și 3 drept candidate ca primul divizor. 231 este și el un multiplu al lui 3: avem , și astfel . Se continuă cu 77 și 3 drept candidate ca prim divizor. 77 nu este un multiplu al lui 3, deoarece suma cifrelor sale este 14, deci nu este multiplu de 3. Nu este nici multiplu de 5, deoarece ultima sa cifră este 7. Următorul divizor impar care trebuie testat este 7. Avem , și astfel . Aceasta arată că 7 este prim (ușor de testat direct). Se continuă cu 11 și 7 drept candidate ca prim divizor. Întrucât , calculul s-a terminat. Astfel 11 este prim, iar descompunerea în factori primi este
.
Expresii Manipularea expresiilor stă la fundamentele algebrei. Factorizarea este una dintre cele mai importante metode de manipulare a expresiilor din mai multe motive. Dacă se poate pune o ecuație într-o formă factorizată , atunci problema rezolvării ecuației se împarte în două probleme independente (și în general mai ușoare) și . Atunci când o expresie poate fi factorizată, factorii sunt adesea mult mai simpli și, astfel, pot oferi o perspectivă asupra problemei. De exemplu, expresia
având 16 înmulțiri, 4 scăderi și 3 adunări, poate fi factorizată în expresia mult mai simplă
cu doar două înmulțiri și trei scăderi. Mai mult, forma factorizată dă imediat rădăcinile x = a, b, c ca rădăcini ale polinomului.
Pe de altă parte, factorizarea nu este întotdeauna posibilă, iar atunci când este posibilă, se poate ca factorii să nu fie întotdeauna mai simpli. De exemplu, poate fi factorizat în doi și .
Au fost dezvoltate diverse metode pentru găsirea factorizărilor; unele sunt descrise mai jos.
Rezolvarea ecuațiilor algebrice poate fi privită ca o problemă de . De fapt, teorema fundamentală a algebrei poate fi enunțată după cum urmează: fiecare polinom în de grad cu coeficienți complecși poate fi factorizat în factori liniari pentru , unde sunt rădăcinile polinomului. Chiar dacă structura factorizării este cunoscută în aceste cazuri, valorile nu pot fi în general calculate în termeni de radicali (rădăcini a de ordin n), conform teoremei Abel-Ruffini. În cele mai multe cazuri, cel mai bun lucru care se poate face este să se calculeze valori aproximative pentru rădăcini cu ajutorul unui .
Istoria factorizării expresiilor Utilizarea sistematică a manipulărilor algebrice pentru simplificarea expresiilor (mai precis a ecuațiilor) datează din secolul al IX-lea, de la cartea lui al-Khwarizmi , al cărei titlu conține denumirea a două astfel de tipuri de manipulare.
Totuși, chiar și pentru rezolvarea ecuațiilor pătratice, nu s-a folosit metoda de factorizare decât după lucrarea lui Harriot publicată în 1631, la zece ani după moartea sa.In , the author notes "In view of the present emphasis given to the solution of quadratic equations by factoring, it is interesting to note that this method was not used until Harriot's work of 1631". În cartea sa , Harriot a întocmit tabele pentru adunarea, scăderea, înmulțirea și împărțirea monoamelor, binoamelor și trinoamelor. Apoi, într-o a doua secțiune, a enunțat ecuația și a arătat că aceasta se potrivește cu forma de înmulțire pe care a o specificase anterior, dând factorizarea .
Metode generale Următoarele metode se aplică oricărei sume sau expresii care poate fi transformată într-o sumă. Prin urmare, ele sunt cel mai adesea aplicate la polinoame, deși pot fi aplicate și atunci când termenii sumei nu sunt monoamele, adică termenii sumei sunt un produs de variabile și constante.
Factorul comun Se poate întâmpla ca toți termenii unei sume să fie produse și ca anumiți factori să fie comuni tuturor termenilor. În acest caz, distributivitatea permite extragerea acestui factor comun. Dacă există mai mulți astfel de factori comuni, este se preferă împărțirea la cel mai mare astfel de factor comun. De asemenea, dacă există coeficienți întregi, se poate găsi cel mai mare divizor comun al acestor coeficienți.
De exemplu,
deoarece 2 este cel mai mare divizor comun al lui 6, 8 și 10, și toți termenii se împart la .
Gruparea Gruparea termenilor poate permite utilizarea altor metode pentru obținerea unei factorizări.
De exemplu, pentru a factoriza
se poate observa că primii doi termeni au un factor comun , iar ultimii doi termeni au factorul comun . Prin urmare
Atunci, o inspecție simplă relevă factorul comun , ceea ce duce la factorizarea
În general, aceasta funcționează pentru sume de 4 termeni care au fost obținute ca produs a două binoame. Deși nu frecvent, aceasta poate funcționa și pentru exemple mai complicate.
Adunarea și scăderea termenilor Uneori, o grupare de termeni dezvăluie o parte a unui șablon identificabil. Atunci, este utilă adunarea și scăderea termenilor pentru completarea șablonului.
O utilizare tipică este metoda de pentru obținerea formulei pătratice.
Un alt exemplu este factorizarea lui Dacă se introduce rădăcina pătrată nereală a lui –1, notată de regulă cu , atunci avem o diferență de pătrate
S-ar putea dori însă și o factorizare cu coeficienți numere reale. Prin adunarea și scăderea lui și grupând trei termeni împreună, se poate recunoaște pătratul unui binom:
Dacă se scade și apoi se adună , rezultă factorizarea:
Aceste factorizări funcționează nu numai asupra numerelor complexe, ci și asupra oricărui corp, unde –1, 2 sau –2 este un pătrat. Într-un corp finit, produsul a două elemente care nu sunt pătrate este un pătrat; aceasta implică faptul că polinomul care este peste numerele întregi, este reductibil orice număr prim. De exemplu,
deoarece deoarece deoarece
Șabloane identificabile Multe identități oferă o egalitate între o sumă și un produs. Metodele de mai sus pot fi utilizate pentru a face să apară într-una din părți suma dintr-o identitate, care poate fi, prin urmare, înlocuită cu un produs.
Mai jos sunt identitățile ale căror părți stângi sunt utilizate în mod obișnuit ca șabloane (aceasta înseamnă că variabilele și care apar în aceste identități pot reprezenta orice subexpresie a expresiei care trebuie factorizată). miniatura| Demonstrație vizuală a diferențelor dintre două pătrate și două cuburi
Diferența a două pătrate
De exemplu,
Suma/diferența a două cuburi