Faktorizace - Factorization

V matematice , faktorizace (nebo faktorizace naleznete English rozdíly hláskování ), nebo factoring se skládá z psaní číslo nebo jiný matematický objekt jako součin několika faktorů , obvykle menší nebo jednodušších objektů stejného druhu. Například 3 × 5 je faktorizace celého čísla 15 a ( x - 2) ( x + 2) je faktorizace polynomu x ² - 4 .

Faktorizace není obvykle považována za smysluplnou v číselných systémech s dělením , jako jsou reálná nebo komplexní čísla , protože jakékoli lze triviálně zapsat, jako vždy, když není nula. Smysluplnou faktorizaci pro racionální číslo nebo racionální funkci však lze získat tak, že ji napíšeme v nejnižších termínech a oddělíme faktoring jejího čitatele a jmenovatele. ${\ displaystyle x}$${\ displaystyle (xy) \ times (1/y)}$${\ displaystyle y}$

Faktorizace byla poprvé zvažována starověkými řeckými matematiky v případě celých čísel. Dokázali základní teorém aritmetiky , který tvrdí, že každé kladné celé číslo může být započítáno do součinu prvočísel , které nelze dále započítat do celých čísel větších než 1. Navíc je tato faktorizace jedinečná až do pořadí faktorů. Ačkoli je celočíselná faktorizace druhem inverze k násobení, je to algoritmicky mnohem obtížnější , což je skutečnost, která se v kryptosystému RSA využívá k implementaci kryptografie s veřejným klíčem .

Polynomiální faktorizace byla také studována po staletí. V elementární algebře faktoring polynomu redukuje problém nalezení jeho kořenů na nalezení kořenů faktorů. Polynomy s koeficienty v celých číslech nebo v poli mají jedinečnou faktorizační vlastnost , což je verze základní věty o aritmetice s prvočísly nahrazenými neredukovatelnými polynomy . Zejména univariační polynom se složitými koeficienty připouští jedinečnou (až do uspořádání) faktorizaci na lineární polynomy : toto je verze základní věty algebry . V tomto případě lze faktorizaci provést pomocí algoritmů pro hledání kořenů . Případ polynomů s celočíselnými koeficienty je zásadní pro počítačovou algebru . Existují efektivní počítačové algoritmy pro výpočet (úplné) faktorizace v kruhu polynomů s koeficienty racionálních čísel (viz faktorizace polynomů ).

Komutativní kroužek mající jedinečnou rozklad vlastnost se nazývá jedinečné faktorizace doména . Existují číselné systémy , například určité prstence algebraických celých čísel , které nejsou jedinečnými doménami faktorizace. Kruhy algebraických celých čísel však uspokojují slabší vlastnosti Dedekindových domén : ideály faktor jedinečně do prvotních ideálů .

Faktorizace může také odkazovat na obecnější dekompozice matematického objektu na součin menších nebo jednodušších objektů. Například každá funkce může být zahrnuta do složení surjektivní funkce s injektivní funkcí . Matice mají mnoho druhů maticových faktorizací . Například každá matice má jedinečnou faktorizaci LUP jako součin nižší trojúhelníkové matice L se všemi diagonálními vstupy rovnými jedné, horní trojúhelníkové matice U a permutační matice P ; toto je maticová formulace Gaussovy eliminace .

Celá čísla

Podle základní věty o aritmetice má každé celé číslo větší než 1 jedinečnou (až na pořadí faktorů) faktorizaci na prvočísla , což jsou taková celá čísla, která nelze dále faktorizovat na součin celých čísel větších než jedna.

Pro výpočet rozklad celé číslo n , jeden potřebuje algoritmus pro nalezení dělitel q z n a rozhodování o tom, že n je prvočíslo. Když je takový dělitel nalezen, opakovaná aplikace tohoto algoritmu na faktory q a n / q nakonec poskytne úplnou faktorizaci n .

Pro nalezení dělitel q z n , pokud existuje, stačí otestovat všechny hodnoty q tak, že 1 <q a q ² ≤ n . Ve skutečnosti, pokud r je dělitel n takový, že r ² > n , pak q = n / r je dělitel n takový, že q ² ≤ n .

Pokud testujeme hodnoty q ve vzestupném pořadí, první nalezený dělitel je nutně prvočíslo a kofaktor r = n / q nemůže mít žádný dělitel menší než q . K získání úplné faktorizace stačí tedy pokračovat v algoritmu hledáním dělitel r, který není menší než q a není větší než √ r .

Pro použití metody není třeba testovat všechny hodnoty q . V zásadě stačí testovat pouze primární dělitele. To musí mít tabulku prvočísel, která může být generována například pomocí síta Eratosthenes . Protože metoda faktorizace funguje v podstatě stejně jako síto Eratosthenes, je obecně efektivnější testovat na dělitel pouze ta čísla, u nichž není hned jasné, zda jsou prvočísla nebo ne. Obvykle lze postupovat testováním 2, 3, 5 a čísel> 5, jejichž poslední číslice je 1, 3, 7, 9 a součet číslic není násobkem 3.

Tato metoda funguje dobře pro faktoring malých celých čísel, ale je neúčinná pro větší celá čísla. Například Pierre de Fermat nebyl schopen zjistit, že 6. číslo Fermat

${\ Displaystyle 1+2^{2^{5}} = 1+2^{32} = 4 \, 294 \, 967 \, 297}$

není prvočíslo. Ve skutečnosti by aplikace výše uvedené metody vyžadovala více než10 000  divizí pro číslo, které má 10  desetinných míst .

Existují účinnější algoritmy faktoringu. Zůstávají však relativně neefektivní, protože při současném stavu techniky nelze ani u výkonnějších počítačů rozložit faktor na 500 desetinných číslic, který je součinem dvou náhodně vybraných prvočísel. Tím je zajištěna bezpečnost kryptosystému RSA , který je široce používán pro zabezpečenou internetovou komunikaci.

Příklad

Pro faktoring n = 1386 do prvočísel:

• Začněte dělením 2: číslo je sudé a n = 2 · 693 . Pokračujte číslem 693 a 2 jako první dělitel.
• 693 je lichý (2 není dělitel), ale je násobkem 3: jeden má 693 = 3 · 231 a n = 2 · 3 · 231 . Pokračujte 231 a 3 jako první dělitel kandidát.
• 231 je také násobkem 3: jeden má 231 = 3,7 , a tedy n = 2 · 3 ² · 77 . Pokračujte číslem 77 a 3 jako první dělitel.
• 77 není násobkem 3, protože součet jeho číslic je 14, není násobkem 3. Rovněž to není násobek 5, protože jeho poslední číslice je 7. Další lichý dělitel, který se má testovat, je 7. Jeden má 77 = 7 · 11 , a tedy n = 2 · 3 ² · 7 · 11 . To ukazuje, že 7 je primární (snadno se testuje přímo). Pokračujte čísly 11 a 7 jako kandidát prvního dělitele.
• Jako 7 ² > 11 jedna skončila. 11 je tedy prvočíslo a primární faktorizace je

1386 = 2 · 3 ² · 7 · 11 .

Výrazy

Manipulace s výrazy je základem algebry . Faktorizace je jednou z nejdůležitějších metod pro manipulaci s výrazem z několika důvodů. Pokud lze dát rovnici do faktorizované podoby E ⋅ F = 0 , pak se problém řešení rovnice rozdělí na dva nezávislé (a obecně jednodušší) problémy E = 0 a F = 0 . Když lze výraz zohlednit, faktory jsou často mnohem jednodušší a mohou tak nabídnout určitý náhled na problém. Například,

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

16 násobení, 4 odčítání a 3 sčítání může být zapracováno do mnohem jednoduššího výrazu

${\ Displaystyle (xa) (xb) (xc),}$

pouze se dvěma násobeními a třemi odečty. Faktorovaný tvar navíc okamžitě dává kořeny x = a , b , c jako kořeny polynomu.

Na druhou stranu faktorizace není vždy možná, a když je to možné, faktory nejsou vždy jednodušší. Například lze rozdělit na dva neredukovatelné faktory a . ${\ Displaystyle x^{10} -1}$ ${\ Displaystyle x-1}$${\ Displaystyle x^{9}+x^{8}+\ cdots+x^{2}+x+1}$

Pro nalezení faktorizace byly vyvinuty různé metody; některé jsou popsány níže .

Na řešení algebraických rovnic lze pohlížet jako na problém polynomiální faktorizace. Ve skutečnosti lze základní větu algebry vyjádřit následovně: každý polynom v x stupně n s komplexními koeficienty může být faktorizován do n lineárních faktorů pro i = 1, ..., n , kde a _i s jsou kořeny polynomu. I přesto, že struktura faktorizace je v těchto případech je znám, _i to obecně nemohou být vypočteny z hlediska zbytků ( n ^th kořeny), u Abel-Ruffini teorém . Ve většině případů lze nejlépe provést výpočet přibližných hodnot kořenů pomocí algoritmu pro hledání kořenů . ${\ displaystyle x-a_ {i},}$

Historie faktorizace výrazů

Systematické používání algebraických manipulací pro zjednodušování výrazů (konkrétněji rovnic )) lze datovat do 9. století s al-Khwarizmiho knihou The Compendious Book on Calculation by Completion and Balancing , která je pojmenována dvěma takovými druhy manipulace.

Avšak ani pro řešení kvadratických rovnic nebyla faktoringová metoda použita před Harriotovou prací publikovanou v roce 1631, deset let po jeho smrti. Ve své knize Artis Analyticae Praxis reklama Aequationes Algebraicas Resolvendas , Harriot nakreslil, stoly pro sčítání, odčítání, násobení a dělení monomials , dvojčleny a trinomials . Potom ve druhé části nastavil rovnici aa - ba + ca = + bc a ukázal, že to odpovídá formě násobení, kterou předtím poskytl, což dává faktorizaci ( a - b ) ( a + c ) .

Obecné metody

Následující metody platí pro jakýkoli výraz, který je součtem nebo který lze převést na součet. Proto jsou nejčastěji aplikovány na polynomy , i když je lze použít také v případě, že podmínky součtu nejsou monomiální , to znamená, že podmínky součtu jsou součinem proměnných a konstant.

Společný faktor

Může se stát, že všechny podmínky částky jsou produkty a že některé faktory jsou společné pro všechny podmínky. V tomto případě distribuční právo umožňuje rozdělit tento společný faktor. Pokud existuje několik takových společných faktorů, stojí za to rozdělit ten největší společný faktor. Pokud existují celočíselné koeficienty, lze také vyloučit největšího společného dělitele těchto koeficientů.

Například,

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

protože 2 je největší společný dělitel 6, 8 a 10 a dělí všechny výrazy. ${\ Displaystyle x^{3} y^{2}}$

Seskupení

Seskupovací podmínky mohou umožňovat použití jiných metod pro získání faktorizace.

Například faktorovat

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

lze poznamenat, že první dva termíny mají společný faktor x a poslední dva termíny mají společný faktor y . Tím pádem

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

Poté jednoduchá kontrola ukazuje společný faktor x + 5 , což vede k faktorizaci

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

Obecně to funguje pro částky 4 výrazů, které byly získány jako součin dvou binomů . I když to není často, může to fungovat i u složitějších příkladů.

Sčítání a odčítání výrazů

Někdy se může stát, že některé seskupení výrazů bude součástí rozpoznatelného vzoru . Potom je užitečné přidat termíny pro dokončení vzoru a odečíst je, pokud neměníte hodnotu výrazu.

Typickým použitím je dokončení metody square pro získání kvadratického vzorce .

Dalším příkladem je faktorizace: Pokud člověk zavádí nereálnou odmocninu –1 , běžně označovanou i , pak má rozdíl čtverců${\ displaystyle x^{4} +1.}$

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

Lze však také chtít faktorizaci s reálnými číselnými koeficienty. Sečtením a odečtením a seskupením tří výrazů dohromady lze rozpoznat čtverec binomické : ${\ displaystyle 2x^{2},}$

${\ Displaystyle x^{4}+1 = (x^{4}+2x^{2} +1) -2x^{2} = (x^{2} +1)^{2}-\ left ( x {\ sqrt {2}} \ right)^{2} = \ left (x^{2}+x {\ sqrt {2}}+1 \ right) \ left (x^{2} -x {\ sqrt {2}}+1 \ vpravo).}$

Odečtením a přidáním také získáte faktorizaci: ${\ displaystyle 2x^{2}}$

${\ Displaystyle x^{4}+1 = (x^{4} -2x^{2} +1)+2x^{2} = (x^{2} -1)^{2}+\ left ( x {\ sqrt {2}} \ right)^{2} = \ left (x^{2}+x {\ sqrt {-2}}-1 \ right) \ left (x^{2} -x { \ sqrt {-2}}-1 \ vpravo).}$

Tyto faktorizace fungují nejen na komplexních číslech, ale také na libovolném poli , kde –1, 2 nebo –2 je čtverec. V konečném poli je součin dvou jiných než čtverců čtverec; to znamená, že polynom, který je neredukovatelný na celá čísla, je redukovatelné modulo každé prvočíslo . Například, ${\ displaystyle x^{4} +1,}$

${\ 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}$od té doby ${\ Displaystyle 1^{2} \ equiv -2 {\ pmod {3}};}$

${\ Displaystyle x^{4} +1 \ equiv (x^{2} +2) (x^{2} -2) {\ pmod {5}}, \ qquad}$od té doby ${\ Displaystyle 2^{2} \ equiv -1 {\ pmod {5}};}$

${\ Displaystyle x^{4} +1 \ equiv (x^{2}+3x+1) (x^{2} -3x+1) {\ pmod {7}}, \ qquad}$od té doby ${\ Displaystyle 3^{2} \ equiv 2 {\ pmod {7}}.}$

Rozpoznatelné vzory

Mnoho identit poskytuje rovnost mezi součtem a produktem. Výše uvedené metody lze použít k tomu, aby se souhrnná stránka určité identity objevila ve výrazu, který může být proto nahrazen produktem.

Níže jsou uvedeny identity, jejichž levé strany se běžně používají jako vzory (to znamená, že proměnné E a F, které se v těchto identitách objevují, mohou představovat jakýkoli podvýraz výrazu, který je třeba faktorizovat.

• Rozdíl dvou čtverců

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

Například,

${\ 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}-(xy)^{2} \\ & = (a+b +xy) (a+b-x+y). \ end {aligned}}}$

• Součet/rozdíl dvou kostek

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

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

• Rozdíl dvou čtvrtých mocností

${\ Displaystyle {\ begin {aligned} E^{4} -F^{4} & = (E^{2}+F^{2}) (E^{2} -F^{2}) \\ & = (E^{2}+F^{2}) (E+F) (EF) \ end {zarovnáno}}}$

• Součet/rozdíl dvou n -tých mocnin

U následujících identit mohou být faktory často dále faktorizovány:

• Rozdíl, dokonce exponent

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

• Rozdíl, sudý nebo lichý exponent

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

Toto je příklad, který ukazuje, že faktory mohou být mnohem větší než součet, který je faktorizován.

• Součet, lichý exponent

${\ 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})}$

(získané změnou F o - F v předchozím vzorci)

• Součet, dokonce exponent

Pokud je exponent mocninou dvou, pak výraz nelze obecně faktorizovat bez zavedení komplexních čísel (pokud E a F obsahují komplexní čísla, nemusí tomu tak být). Pokud má n lichý dělitel, to znamená, že pokud n = pq s p lichým, lze použít předchozí vzorec (v „součtu, lichý exponent“) aplikovaný na${\ Displaystyle (E^{q})^{p}+(F^{q})^{p}.}$

• Trojčleny a krychlové vzorce

${\ 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}}}$

• Binomická rozšíření

Tyto binomické poučky dodává vzory, které mohou být snadno rozpozná z celých čísel, které se objevují v nich

V nízké míře:

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

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

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

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

Obecněji řečeno, koeficienty rozšířených forem a jsou binomické koeficienty , které se objevují v n -té řadě Pascalova trojúhelníku .${\ displaystyle (a+b)^{n}}$${\ displaystyle (ab)^{n}}$

Kořeny jednoty

N th kořeny jednoty jsou komplexní čísla , z nichž každý se o kořen polynomu Jsou tedy čísla ${\ Displaystyle x^{n} -1.}$

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

pro ${\ Displaystyle k = 0, \ ldots, n-1.}$

Z toho vyplývá, že pro jakékoli dva výrazy E a F má jeden:

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

${\ Displaystyle E^{n}+F^{n} = \ prod _ {k = 0}^{n-1} \ left (E-Fe^{(2k+1) i \ pi /n} \ right ) \ qquad {\ text {if}} n {\ text {je sudý}}}$

${\ Displaystyle E^{n}+F^{n} = (E+F) \ prod _ {k = 1}^{n-1} \ left (E+Fe^{2ik \ pi /n} \ right ) \ qquad {\ text {if}} n {\ text {je lichý}}}$

Pokud E a F jsou skutečné výrazy a člověk chce skutečné faktory, musí nahradit každý pár komplexních konjugovaných faktorů jeho součinem. Protože komplexní konjugát je a ${\ displaystyle e^{i \ alpha}}$${\ Displaystyle e^{-i \ alpha},}$

${\ 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},}$

jeden má následující skutečné faktorizace (jeden přechází z jednoho do druhého změnou k na n - k nebo n + 1 - k a použitím obvyklých trigonometrických vzorců :

${\ displaystyle {\ begin {aligned} E^{2n} -F^{2n} & = (EF) (E+F) \ prod _ {k = 1}^{n-1} \ left (E^{ 2} -2EF \ cos \, {\ tfrac {k \ pi} {n}}+F^{2} \ right) \\ & = (EF) (E+F) \ prod _ {k = 1}^ {n-1} \ left (E^{2}+2EF \ cos \, {\ tfrac {k \ pi} {n}}+F^{2} \ right) \ end {zarovnaný}}}$

${\ Displaystyle {\ begin {aligned} 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) \ end {aligned}}}$

Tyto kosiny , které se objevují v těchto factorizations jsou algebraická čísla , a může být vyjádřena z hlediska zbytků (to je možné proto, že jejich Galois skupina je cyklická); tyto radikální výrazy jsou však příliš složité na to, aby byly použity, s výjimkou nízkých hodnot n . Například,

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

${\ Displaystyle a^{5} -b^{5} = (ab) \ 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),}$

Často chce někdo faktorizaci s racionálními koeficienty. Taková faktorizace zahrnuje cyklotomické polynomy . Vyjadřovat racionální factorizations částek a rozdíly nebo pravomoci, potřebujeme zápis pro homogenizaci polynom : pokud její homogenizace je bivariate polynom Tak, jeden má ${\ Displaystyle P (x) = a_ {0} x^{n}+a_ {i} x^{n-1}+\ cdots+a_ {n},}$ ${\ Displaystyle {\ overline {P}} (x, y) = a_ {0} x^{n}+a_ {i} x^{n-1} y+\ cdots+a_ {n} y^{n} .}$

${\ 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),}$

kde produkty jsou převzaty všechny dělitelé n nebo všechny dělitelé 2 n , které nerozdělují n , a je n -tým cyklotomickým polynomem. ${\ displaystyle Q_ {n} (x)}$

Například,

${\ 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) = (ab) (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}),}$

protože dělitelé 6 jsou 1, 2, 3, 6 a dělitelé 12, kteří nerozdělují 6, jsou 4 a 12.

Polynomy

U polynomů je faktorizace silně spojena s problémem řešení algebraických rovnic . Algebraická rovnice má tvar

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

kde P ( x ) je polynom v x s Roztok této rovnice (která se také nazývá kořen polynomu) je hodnota r o x tak, že ${\ displaystyle a_ {0} \ neq 0.}$

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

Pokud je faktorizace P ( x ) = 0 jako součin dvou polynomů, pak kořeny P ( x ) jsou spojením kořenů Q ( x ) a kořenů R ( x ) . Řešení P ( x ) = 0 se tedy redukuje na jednodušší úlohy řešení Q ( x ) = 0 a R ( x ) = 0 . ${\ Displaystyle P (x) = Q (x) R (x)}$

Naopak, faktor věta uvádí, že, je-li r je kořen P ( x ) = 0 , pak P ( x ) mohou být zapracovány jako

${\ Displaystyle P (x) = (xr) Q (x),}$

kde Q ( x ) je kvocient euklidovské dělení z P ( x ) = 0 o lineární (studia jednoho) faktor x - r .

V případě, že koeficienty P ( x ) je reálná nebo komplexní čísla, má základní věta algebry tvrdí, že P ( x ) je skutečný nebo komplexní kořen. Rekurzivně s využitím faktorové věty to má za následek, že

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

kde jsou skutečné nebo komplexní kořeny P , přičemž některé z nich se možná opakují. Tato úplná faktorizace je jedinečná až do pořadí faktorů. ${\ displaystyle r_ {1}, \ ldots, r_ {n}}$

Pokud jsou koeficienty P ( x ) reálné, obecně se chce faktorizace, kde faktory mají skutečné koeficienty. V tomto případě může mít úplná faktorizace některé kvadratické (stupeň dva) faktory. Tuto faktorizaci lze snadno odvodit z výše uvedené úplné faktorizace. Ve skutečnosti, pokud r = a + ib je nereálný kořen P ( x ) , pak jeho komplexní konjugát s = a - ib je také kořenem P ( x ) . Takže produkt

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

je faktor P ( x ) se skutečnými koeficienty. Opakováním pro všechny nereálné faktory získáte faktorizaci s lineárními nebo kvadratickými reálnými faktory.

Pro výpočet těchto skutečných nebo složitých faktorizací je třeba kořeny polynomu, které nemusí být vypočítány přesně a pouze aproximovány pomocí algoritmů pro vyhledávání kořenů .

V praxi má většina zájmových algebraických rovnic celočíselné nebo racionální koeficienty a člověk může chtít faktorizaci s faktory stejného druhu. Základní věta aritmetiky lze zobecnit na tento případ s tím, že polynomy s integer nebo racionálními koeficienty mají jedinečnou vlastnost faktorizace . Přesněji, každý polynom s racionálními koeficienty může být v produktu faktorizován

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

kde q je racionální číslo a jsou nekonstantní polynomy s celočíselnými koeficienty, které jsou neredukovatelné a primitivní ; to znamená, že žádný z nich nesmí být zapsán jako součin dvou polynomů (s celočíselnými koeficienty), které nejsou ani 1 ani –1 (celá čísla jsou považována za polynomy stupně nula). Tato faktorizace je navíc jedinečná až do pořadí faktorů a znaků faktorů. ${\ Displaystyle P_ {1} (x), \ ldots, P_ {k} (x)}$${\ displaystyle P_ {i} (x)}$

Pro výpočet této faktorizace existují účinné algoritmy , které jsou implementovány ve většině systémů počítačové algebry . Viz faktorizace polynomů . Tyto algoritmy jsou bohužel příliš komplikované na použití pro výpočty typu papír a tužka. Kromě výše uvedené heuristiky je pro ruční výpočty vhodné pouze několik metod, které obecně fungují pouze pro polynomy nízkého stupně s několika nenulovými koeficienty. Hlavní takové metody jsou popsány v následujících podsekcích.

Faktorizace primitivní části a obsahu

Každý polynom s racionálními koeficienty může být faktorizován jedinečným způsobem jako součin racionálního čísla a polynomu s celočíselnými koeficienty, který je primitivní (to znamená, že největší společný dělitel koeficientů je 1) a má kladný vedoucí koeficient (koeficient termínu nejvyššího stupně). Například:

${\ 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)}$

Při této faktorizaci se racionální číslo nazývá obsah a primitivní polynom je primitivní část . Výpočet této faktorizace lze provést následujícím způsobem: za prvé redukujte všechny koeficienty na společného jmenovatele, abyste získali kvocient o celé číslo q polynomu s celočíselnými koeficienty. Potom se rozdělí větší společný dělitel p koeficientů tohoto polynomu pro získání primitivní části, přičemž obsah je Nakonec, pokud je to potřeba, změní se znaménka p a všechny koeficienty primitivní části. ${\ Displaystyle p/q.}$

Tato faktorizace může vést k výsledku, který je větší než původní polynom (typicky když existuje mnoho společných jmenovatelů), ale i když je tomu tak, s primitivní částí se obecně snáze manipuluje pro další faktorizaci.

Pomocí faktorové věty

Faktor teorém říká, že pokud r se o kořen z polynomu

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

což znamená P ( r ) = 0 , pak existuje faktorizace

${\ Displaystyle P (x) = (xr) Q (x),}$

kde

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

s . Pak polynomiální dlouhé dělení nebo syntetické dělení dává: ${\ displaystyle a_ {0} = b_ {0}}$

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

To může být užitečné, když člověk ví nebo může uhodnout kořen polynomu.

Například pro člověka může být snadno vidět, že součet jeho koeficientů je 0, takže r = 1 je kořen. As r + 0 = 1 , a jeden má ${\ Displaystyle P (x) = x^{3} -3x+2,}$${\ Displaystyle r^{2}+0r-3 = -2,}$

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

Racionální kořeny

U polynomů s koeficienty racionálních čísel lze hledat kořeny, které jsou racionálními čísly. Primitivní faktorizace částečného obsahu (viz výše ) redukuje problém hledání racionálních kořenů na případ polynomů s celočíselnými koeficienty, které nemají netriviálního společného dělitele .

If je racionální kořen takového polynomu ${\ displaystyle x = {\ tfrac {p} {q}}}$

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

faktorová věta ukazuje, že člověk má faktorizaci

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

kde oba faktory mají celočíselné koeficienty (skutečnost, že Q má celočíselné koeficienty, vyplývá z výše uvedeného vzorce pro podíl P ( x ) podle ). ${\ displaystyle xp/q}$

Porovnání koeficientů stupně n a konstantních koeficientů ve výše uvedené rovnosti ukazuje, že je -li racionální kořen v redukované formě , pak q je dělitelem a p je dělitelem Proto existuje konečný počet možností pro p a q , které lze systematicky zkoumat. ${\ displaystyle {\ tfrac {p} {q}}}$${\ displaystyle a_ {0},}$${\ displaystyle a_ {n}.}$

Například pokud je polynom

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

má racionální kořen s q > 0 , pak p musí dělit 6; to je a q musí dělit 2, to znamená, že navíc, pokud x <0 , všechny členy polynomu jsou záporné, a proto kořen nemůže být záporný. To znamená, že člověk musí mít ${\ displaystyle {\ tfrac {p} {q}}}$${\ Displaystyle p \ in \ {\ pm 1, \ pm 2, \ pm 3, \ pm 6 \},}$${\ displaystyle q \ in \ {1,2 \}.}$

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

Přímý výpočet ukazuje, že pouze root je, takže nemůže existovat žádný jiný racionální root. Použití faktorové věty nakonec vede k faktorizaci ${\ displaystyle {\ tfrac {3} {2}}}$${\ Displaystyle 2x^{3} -7x^{2}+10x-6 = (2x-3) (x^{2} -2x+2).}$

Kvadratická metoda AC

Výše uvedený způsob lze upravit pro kvadratické polynomy , což vede k ac faktorizační metodě .

Zvažte kvadratický polynom

${\ Displaystyle P (x) = sekera^{2}+bx+c}$

s celočíselnými koeficienty. Pokud se má racionální kořen, musí být jeho jmenovatel rozdělit rovnoměrně, a to může být psáno jako možná redukovatelné frakci By viètovy vzorce , druhý kořen je ${\ displaystyle {\ tfrac {r} {a}}.}$

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

s Tedy druhý kořen je také racionální a Vietův druhý vzorec dává ${\ Displaystyle s =-(b+r).}$

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

to je

${\ Displaystyle rs = ac \ quad {\ text {and}} \ quad r+s = -b.}$

Kontrola všech párů celých čísel, jejichž součinem je ac, poskytne racionální kořeny, pokud existují.

Uvažujme například kvadratický polynom

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

Kontrola faktorů ac = 36 vede k 4 + 9 = 13 = b , čímž získáme dva kořeny

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

a faktorizace

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

Použití vzorců pro polynomické kořeny

Libovolný univariantní kvadratický polynom lze založit pomocí kvadratického vzorce : ${\ Displaystyle sekera^{2}+bx+c}$

${\ 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),}$

kde a jsou dva kořeny polynomu. ${\ displaystyle \ alpha}$${\ displaystyle \ beta}$

Pokud jsou a, b, c všechny reálné , pak jsou faktory reálné právě tehdy, pokud diskriminant není záporný. V opačném případě nelze kvadratický polynom faktorizovat na nekonstantní reálné faktory. ${\ displaystyle b^{2} -4ac}$

Kvadratická rovnice je platná, pokud koeficienty do žádné oblasti z charakteristického odlišný od dvou, a zejména na koeficienty v konečného pole s lichým počtem prvků.

Existují také vzorce pro kořeny krychlových a kvartických polynomů, které jsou obecně pro praktické použití příliš komplikované. Tyto Abel-Ruffini věta ukazuje, že neexistují žádné obecné kořenové vzorce, pokud jde o zbytky pro polynomy stupně pět nebo vyšší.

Využití vztahů mezi kořeny

Může se stát, že člověk zná nějaký vztah mezi kořeny polynomu a jeho koeficienty. Použití těchto znalostí může pomoci faktoring polynomu a nalezení jeho kořenů. Galoisova teorie je založena na systematickém studiu vztahů mezi kořeny a koeficienty, které zahrnují Vietovy vzorce .

Zde uvažujeme jednodušší případ, kdy vztah uspokojují dva kořeny a polynom${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ displaystyle P (x)}$

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

kde Q je polynom.

To znamená, že je společným kořenem a Jeho je tedy kořenem největšího společného dělitele těchto dvou polynomů. Z toho vyplývá, že tento největší společný dělitel je nekonstantním faktorem euklidovského algoritmu pro polynomy, který umožňuje vypočítat tento největší společný faktor. ${\ displaystyle x_ {1}}$${\ displaystyle P (Q (x))}$${\ Displaystyle P (x).}$${\ Displaystyle P (x).}$

Pokud například někdo ví nebo hádá, že: má dva kořeny, které se sčítají na nulu, lze použít euklidovský algoritmus na a První krok dělení spočívá v přidání k získání zbytku ${\ Displaystyle P (x) = x^{3} -5x^{2} -16x+80}$${\ displaystyle P (x)}$${\ displaystyle P (-x).}$${\ displaystyle P (x)}$${\ displaystyle P (-x),}$

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

Poté, dělení podle dává nulu jako nový zbytek a x - 5 jako podíl, což vede k úplné faktorizace ${\ displaystyle P (x)}$${\ displaystyle x^{2} -16}$

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

Unikátní faktorizační domény

Celá čísla a polynomy nad polem sdílejí vlastnost jedinečné faktorizace, to znamená, že každý nenulový prvek může být zapracován do součinu invertibilního prvku ( jednotka , ± 1 v případě celých čísel) a součinu neredukovatelných prvků ( prvočísla , v případě celých čísel), a tato faktorizace je jedinečná až do přeskupení faktorů a přesunu jednotek mezi faktory. Integrální domény, které sdílejí tuto vlastnost, se nazývají jedinečné faktorizační domény (UFD).

V UFD existují největší společní dělitelé a naopak každá integrální doména, ve které existují největší společní dělitelé, je UFD. Každá hlavní ideální doména je UFD.

Euclidean doména je nedílnou domény, na kterém je definována euklidovské dělení podobný tomu z celých čísel. Každá euklidovská doména je hlavní ideální doménou, a tedy UFD.

V euklidovské doméně umožňuje euklidovské dělení definování euklidovského algoritmu pro výpočet největších společných dělitelů. To však neznamená existenci faktorizačního algoritmu. Existuje explicitní příklad pole F , takže v euklidovské doméně F [ x ] univariačních polynomů nad F nemůže existovat žádný faktorizační algoritmus .

Ideály

V teorii algebraických čísel vedlo studium diofantických rovnic v průběhu 19. století matematiky k zavedení generalizací celých čísel zvaných algebraická celá čísla . První prsten algebraických celých čísel , které byly zvažovány, byla Gaussova celá a Eisensteinova celá čísla , která sdílejí s obvyklými celými čísly tu vlastnost, že jsou hlavními ideálními doménami , a mají tedy jedinečnou vlastnost faktorizace .

Bohužel se brzy ukázalo, že většina prstenců algebraických celých čísel není hlavní a nemá jedinečnou faktorizaci. Nejjednodušší příklad je ve kterém ${\ displaystyle \ mathbb {Z} [{\ sqrt {-5}}],}$

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

a všechny tyto faktory jsou neredukovatelné .

Tento nedostatek jedinečné faktorizace je hlavní obtíž při řešení diofantických rovnic. Například mnoho špatných důkazů Fermatovy poslední věty (pravděpodobně včetně Fermatova „skutečně úžasného důkazu toho, který je tento okraj příliš úzký na to, aby obsahoval“ ) bylo založeno na implicitním předpokladu jedinečné faktorizace.

Tuto obtíž vyřešil Dedekind , který dokázal, že prstence algebraických celých čísel mají jedinečnou faktorizaci ideálů : v těchto prstencích je každý ideál produktem prvotních ideálů a tato faktorizace je jedinečná podle pořadí faktorů. Tyto obory integrity , které mají tuto jedinečnou vlastnost faktorizace se nyní nazývají dedekindův obor . Mají mnoho pěkných vlastností, které je činí základními v teorii algebraických čísel.

Matice

Maticové prstence jsou nekomutativní a nemají jedinečnou faktorizaci: obecně existuje mnoho způsobů, jak psát matici jako produkt matic. Problém faktorizace tedy spočívá v hledání faktorů specifikovaných typů. Například, LU rozklad poskytuje matici jako produkt, jehož dolní trojúhelníkovou matici pomocí horní trojúhelníkovou matici . Protože to není vždy možné, obecně se za třetí faktor považuje „rozklad LUP“ s permutační maticí .

Nejběžnější typy maticových faktorizací najdete v části Rozklad matice.

Logické matice reprezentuje binární relaci , a maticové násobení odpovídá složení vztahů . Dekompozice vztahu prostřednictvím faktorizace slouží k profilování povahy vztahu, jako je například difunkční vztah.

Viz také

• Eulerova faktorizační metoda pro celá čísla
• Fermatova faktorizační metoda pro celá čísla
• Monoidní faktorizace
• Multiplikativní oddíl
• Tabulka Gaussových celočíselných faktorizací

Poznámky

Reference

• Burnside, William Snow ; Panton, Arthur William (1960) [1912], Teorie rovnic s úvodem do teorie binárních algebraických forem (svazek první) , Dover
• Dickson, Leonard Eugene (1922), první kurz teorie rovnic , New York: John Wiley & Sons
• Fite, William Benjamin (1921), College Algebra (revidovaný) , Boston: DC Heath & Co.
• Klein, Felix (1925), Elementární matematika z pokročilého hlediska; Aritmetika, algebra, analýza , Dover
• Selby, Samuel M., CRC Standard Mathematical Tables (18. vydání.), The Chemical Rubber Co.

externí odkazy

• Wolfram Alpha může také faktorizovat .