Faktorizáció

egy objektum felbontása nála kisebb elemek szorzatára

A faktorizáció azt a folyamatot jelöli, amely során egy objektumot (például egész számok faktorizációja, polinomok faktorizációja, mátrixok faktorizációja) nála valamilyen szempontból „kisebb” elemek szorzatára bontunk. Például a 15 természetes szám faktorizációja a természetes számok feletti prímelemek szorzatára: 3*5, míg az x2-4 polinom faktorizációja az egész számok fölötti polinomgyűrűben: (x-2)(x+2).

Az x2 + cx + d polinom, ahol a + b = c és ab = d felbontható (x + a)'(x + b)-re.

A faktorizálás célja az, hogy valamit nála kisebb „elemi építőelemek” szorzatára felbontsunk. Például egész számok esetében prímszámokra, polinomok esetén irreducibilis polinomokra.

A polinom faktorizáció ellentéte a kibontás vagy beszorzás, amikor az azt alkotó polinomok összeszorzását elvégezzük.

A nagy számok prímfelbontása nehéz probléma, így ezt a tulajdonságot alkalmazzák bizonyos titkosításokban például az RSA-ban.

Egész számokSzerkesztés

A számelmélet alaptételének megfelelően, minden 1-nél nagyobb egész szám egyértelműen felírható prímek szorzataként. A prímfelbontási algoritmus az 1-nél nagyobb egész számnak megadja a prímosztóit.[1] Nagy számokra nem ismert hatékony prímfelbontó algoritmus.

PolinomokSzerkesztés

Másodfokú polinomokSzerkesztés

Bármely másodfokú komplex együtthatós polinom felírható, elsőfokú komplex együtthatós polinomok és egy konstans szorzatára, a következőképpen:


 

ahol   és   a polinom két gyöke. A másodfokú polinom gyökeit a másodfokú egyenlet megoldóképletével találhatjuk meg.

Az egész számok fölött faktorizálható másodfokú polinomokSzerkesztés

Bizonyos másodfokú polinomok felbonthatóak az egész számok teste fölötti elsőfokú polinomok és egy konstans szorzatára.

Teljes négyzetekSzerkesztés

 
A grafikus megjelenítése az (a + b)2 = a2 + 2ab + b2 azonosságnak.

Teljes négyzetnek azokat a polinomokat nevezzük amelyek felírhatóak egy elsőfokú polinom négyzeteként. Ha egy polinom teljes négyzet akkor a következőképpen faktorziálható:

 

vagy

 

Négyzetek összege, különbségeSzerkesztés

Egy másik nagyon hasznos azonosság a négyzetek különbsége:

 

Ha a négyzetek nem kivonva, hanem összeadva vannak, akkor   helyett helyettesítsünk  -t a fenti formulába, és így kaphatjuk a következő azonosságot:

 

  faktorizációja például  .

Egyéb polinomok faktorizációjaSzerkesztés

Két köb összege/különbségeSzerkesztés

 
Két köb faktorizációjának grafikus megjelenítése, térfogatok segítségével.

Egy ismert formula köbök összegére és különbségére a következő:

 

a különbségére pedig:

 

Két negyedik hatvány különbségeSzerkesztés

Szintén ismert formula két negyedik hatvány különbségének kifejezésére:

 
  • Ez a formula levezethető a két négyzet különbségére vonatkozó formulából az a4-t és a b4-t mint a2 és b2 négyzeteként kezelve.

Két ötödik hatvány összege/különbségeSzerkesztés

Szintén ismertek a következő formulák:

 

a különbségre pedig:

 

(További faktorizáció is lehetséges de ekkor az együtthatók megszűnnek egészeknek lenni.)

Két n-edik hatvány összege/különbségeSzerkesztés

A fenti különbségre vonatkozó formulákat ki lehet terjeszteni általános hatványra is a geometriai sorozat első n elemének összegére való formulával. Mivel

 

így (x − 1)-el szorozva az egyenlet mindkét oldalát, megkapjuk az általános formula egy formáját. Az általánosan elterjedt formához helyettesítsünk x helyett a/b-t és mindkét oldalt szorozzuk meg bn-el. Így kapjuk, hogy:

 

Az ehhez tartozó összegre vonatkozó formula attól, függ, hogy n páros vagy páratlan. Ha n páratlan akkor b-t −b-re cserélve a fenti formulában, azt kapjuk, hogy:

 

Ha n páros akkor két eset lehetséges:

  • Ha n 2 hatvány, akkor
  felbonthatatlan a valós számok körében.
  • Különben legyen
 , ahol m páratlan.
Ekkor a kifejezés a következő alakot ölti:  
Így az általános formula:
 

Sophie Germain-féle azonosságSzerkesztés

A Sophie Germain-féle azonosság[2] alapján

 

A levezetése a következő:

 

Egyéb faktorizációs formulákSzerkesztés

 

MátrixokSzerkesztés

FordításSzerkesztés

Ez a szócikk részben vagy egészben a Factorization című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

ForrásokSzerkesztés

  1. An Introduction to the Theory of Numbers, 5th, Oxford Science Publications (1980). ISBN 978-0198531715 
  2. Sophie Germain Identity (angol nyelven). Art of Problem Solving Wiki. [2018. augusztus 16-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. augusztus 16.)

További információkSzerkesztés