Faktorisierung - Factorization

Das Polynom x 2  +  cx  +  d , wobei a + b = c und ab = d ist , kann in ( x + a ) ( x + b ) zerlegt werden .

In der Mathematik besteht die Faktorisierung (oder Faktorisierung , siehe englische Schreibweisenunterschiede ) oder das Faktorisieren darin, eine Zahl oder ein anderes mathematisches Objekt als Produkt mehrerer Faktoren zu schreiben , normalerweise kleinere oder einfachere Objekte der gleichen Art. Zum Beispiel ist 3 × 5 eine Faktorisierung der ganzen Zahl 15 und ( x – 2)( x + 2) ist eine Faktorisierung des Polynoms x 2 – 4 .

Faktorisierung in der Regel nicht sinnvoll betrachtet innerhalb Zahlensysteme besitzen Teilung , wie die realen oder komplexen Zahlen , da jeder kann trivialerweise geschrieben werden , wenn nicht Null ist . Eine sinnvolle Faktorisierung für eine rationale Zahl oder eine rationale Funktion kann jedoch erhalten werden, indem man sie in den niedrigsten Termen schreibt und ihren Zähler und Nenner getrennt faktorisiert .

Die Faktorisierung wurde zuerst von den antiken griechischen Mathematikern im Fall von ganzen Zahlen in Betracht gezogen . Sie bewiesen den fundamentalen Satz der Arithmetik , der besagt , dass jede positive ganze Zahl in ein Produkt von Primzahlen zerlegt werden kann , die nicht weiter in ganze Zahlen größer als 1 zerlegt werden können. Außerdem ist diese Zerlegung bis zur Ordnung der Faktoren eindeutig . Obwohl die ganzzahlige Faktorisierung eine Art Umkehrung zur Multiplikation ist, ist sie algorithmisch viel schwieriger , eine Tatsache, die im RSA-Kryptosystem ausgenutzt wird , um Kryptographie mit öffentlichem Schlüssel zu implementieren .

Auch die polynomielle Faktorisierung wird seit Jahrhunderten untersucht. In der elementaren Algebra reduziert das Faktorisieren eines Polynoms das Problem des Findens seiner Wurzeln auf das Finden der Wurzeln der Faktoren. Polynome mit Koeffizienten in den ganzen Zahlen oder in einem Körper besitzen die einzigartige Faktorisierungseigenschaft , eine Version des Fundamentalsatzes der Arithmetik mit Primzahlen, die durch irreduzible Polynome ersetzt werden . Insbesondere lässt ein univariates Polynom mit komplexen Koeffizienten eine (bis zur Ordnung) eindeutige Faktorisierung in lineare Polynome zu : Dies ist eine Version des Fundamentalsatzes der Algebra . In diesem Fall kann die Faktorisierung mit Wurzelfindungsalgorithmen erfolgen . Der Fall von Polynomen mit ganzzahligen Koeffizienten ist grundlegend für die Computeralgebra . Es gibt effiziente Computeralgorithmen , um (vollständige) Faktorisierungen innerhalb des Rings von Polynomen mit rationalen Zahlenkoeffizienten zu berechnen (siehe Faktorisierung von Polynomen ).

Ein kommutativer Ring mit der eindeutigen Faktorisierungseigenschaft wird als eindeutiger Faktorisierungsbereich bezeichnet . Es gibt Zahlensysteme , wie bestimmte Ringe algebraischer Ganzzahlen , die keine eindeutigen Faktorisierungsbereiche sind. Ringe aus algebraischen ganzen Zahlen erfüllen jedoch die schwächere Eigenschaft von Dedekind-Gebieten : Ideale werden eindeutig in Primideale berücksichtigt .

Die Faktorisierung kann sich auch auf allgemeinere Zerlegungen eines mathematischen Objekts in das Produkt kleinerer oder einfacherer Objekte beziehen. Zum Beispiel kann jede Funktion in die Zusammensetzung einer surjektiven Funktion mit einer injektiven Funktion einfließen . Matrizen besitzen viele Arten von Matrixfaktorisierungen . Zum Beispiel hat jede Matrix eine eindeutige LUP-Faktorisierung als Produkt einer unteren Dreiecksmatrix L mit allen diagonalen Einträgen gleich eins, einer oberen Dreiecksmatrix U und einer Permutationsmatrix P ; dies ist eine Matrixformulierung der Gaußschen Elimination .

Ganzzahlen

Nach dem fundamentalen Satz der Arithmetik hat jede ganze Zahl größer als 1 eine eindeutige (bis zur Ordnung der Faktoren) Zerlegung in Primzahlen , das sind die ganzen Zahlen , die nicht weiter in das Produkt von ganzen Zahlen größer als eins faktorisiert werden können.

Um die Faktorisierung einer ganzen Zahl n zu berechnen , benötigt man einen Algorithmus, um einen Teiler q von n zu finden oder zu entscheiden, dass n eine Primzahl ist. Wenn ein solcher Teiler gefunden wird, ergibt die wiederholte Anwendung dieses Algorithmus auf die Faktoren q und n / q schließlich die vollständige Faktorisierung von n .

Um einen Teiler q von n , falls vorhanden, zu finden, genügt es, alle Werte von q zu testen, so dass 1 < q und q 2n ist . Wenn r ein Teiler von n ist, so dass r 2 > n ist , dann ist q = n / r ein Teiler von n, so dass q 2n ist .

Testet man die Werte von q in aufsteigender Reihenfolge, so ist der erste gefundene Teiler notwendigerweise eine Primzahl, und der Kofaktor r = n / q kann keinen Teiler kleiner als q haben . Um die vollständige Faktorisierung zu erhalten, reicht es also aus, den Algorithmus fortzusetzen, indem ein Teiler von r gesucht wird, der nicht kleiner als q und nicht größer als r ist .

Es ist nicht erforderlich, alle Werte von q zu testen, um das Verfahren anzuwenden. Grundsätzlich genügt es, nur Primteiler zu testen. Diese benötigt eine Primzahlentabelle, die zB mit dem Sieb des Eratosthenes erzeugt werden kann . Da die Faktorisierungsmethode im Wesentlichen die gleiche Arbeit leistet wie das Sieb des Eratosthenes, ist es im Allgemeinen effizienter, nur diejenigen Zahlen auf einen Teiler zu testen, bei denen nicht sofort klar ist, ob sie Primzahlen sind oder nicht. Normalerweise kann man mit dem Testen von 2, 3, 5 und den Zahlen > 5 fortfahren, deren letzte Ziffer 1, 3, 7, 9 ist und die Summe der Ziffern kein Vielfaches von 3 ist.

Diese Methode eignet sich gut zum Faktorisieren kleiner Ganzzahlen, ist jedoch bei größeren Ganzzahlen ineffizient. Pierre de Fermat konnte beispielsweise nicht feststellen, dass die 6. Fermat-Zahl

ist keine Primzahl. Tatsächlich würde die Anwendung der obigen Methode mehr als erfordern10 000  Divisionen für eine Zahl mit 10  Dezimalstellen .

Es gibt effizientere Faktorisierungsalgorithmen. Sie bleiben jedoch relativ ineffizient, da man mit dem heutigen Stand der Technik auch mit den leistungsfähigeren Rechnern eine Zahl von 500 Dezimalstellen, die das Produkt zweier zufällig gewählter Primzahlen ist, nicht faktorisieren kann. Dies gewährleistet die Sicherheit des RSA-Kryptosystems , das für die sichere Internetkommunikation weit verbreitet ist .

Beispiel

Um n = 1386 in Primzahlen zu zerlegen:

  • Beginnen Sie mit der Division durch 2: Die Zahl ist gerade und n = 2 · 693 . Fahren Sie mit 693 und 2 als erster Teilerkandidat fort.
  • 693 ist ungerade (2 ist kein Teiler), aber ein Vielfaches von 3: man hat 693 = 3 · 231 und n = 2 · 3 · 231 . Fahren Sie mit 231 und 3 als erster Teilerkandidat fort.
  • 231 ist auch ein Vielfaches von 3: man hat 231 = 3 · 77 , also n = 2 · 3 2 · 77 . Fahren Sie mit 77 und 3 als erster Teilerkandidat fort.
  • 77 ist kein Vielfaches von 3, da die Summe seiner Ziffern 14 ist, kein Vielfaches von 3. Es ist auch kein Vielfaches von 5, weil seine letzte Ziffer 7 ist. Der nächste zu testende ungerade Teiler ist 7. Eins hat 77 = 7 · 11 und damit n = 2 · 3 2 · 7 · 11 . Dies zeigt, dass 7 eine Primzahl ist (einfach direkt zu testen). Fahren Sie mit 11 und 7 als erster Teilerkandidat fort.
  • Als 7 2 > 11 ist man fertig. Somit ist 11 eine Primzahl und die Primfaktorzerlegung ist
1386 = 2 · 3 2 · 7 · 11 .

Ausdrücke

Die Manipulation von Ausdrücken ist die Grundlage der Algebra . Die Faktorisierung ist aus mehreren Gründen eine der wichtigsten Methoden zur Expressionsmanipulation. Wenn kann man eine setzen Gleichung in einer Form faktorisierter EF = 0 , dann ist das Problem der Lösung der Gleichung teilt sich in zwei unabhängige (und in der Regel einfacher) Probleme E = 0 und F = 0 . Wenn ein Ausdruck faktorisiert werden kann, sind die Faktoren oft viel einfacher und können daher einen Einblick in das Problem bieten. Zum Beispiel,

mit 16 Multiplikationen, 4 Subtraktionen und 3 Additionen, kann in den viel einfacheren Ausdruck eingerechnet werden

mit nur zwei Multiplikationen und drei Subtraktionen. Außerdem liefert die faktorisierte Form sofort die Wurzeln x = a , b , c als Nullstellen des Polynoms.

Andererseits ist eine Faktorisierung nicht immer möglich, und wenn es möglich ist, sind die Faktoren nicht immer einfacher. Zum Beispiel kann in zwei irreduzible Faktoren und faktorisiert werden .

Es wurden verschiedene Methoden entwickelt, um Faktorisierungen zu finden; einige werden unten beschrieben .

Das Lösen algebraischer Gleichungen kann als ein Problem der polynomiellen Faktorisierung angesehen werden. Tatsächlich kann der fundamentale Satz der Algebra wie folgt formuliert werden: Jedes Polynom in x vom Grad n mit komplexen Koeffizienten kann in n lineare Faktoren für i = 1, ..., n zerlegt werden , wobei die a i s die Wurzeln sind des Polynoms. Obwohl die Struktur der Faktorisierung in diesen Fällen bekannt ist, kann a i s im Allgemeinen nicht in Radikalen ( n- ten Wurzeln) berechnet werden , nach dem Abel-Ruffini-Theorem . In den meisten Fällen ist es am besten, Näherungswerte der Wurzeln mit einem Wurzelfindungsalgorithmus zu berechnen .

Geschichte der Faktorisierung von Ausdrücken

Die systematische Anwendung von algebraischen Manipulationen zur Vereinfachung der Ausdrücke (insbesondere Gleichungen )) kann bis zum 9. Jahrhundert datiert werden, mit al-Khwarizmi ‚s Buch Des compendious Buch über die Berechnung durch Fertigstellung und Balancing , die mit zwei solchen Arten von Manipulation trugen den Titel.

Aber selbst zum Lösen quadratischer Gleichungen wurde die Faktorisierungsmethode nicht verwendet, bevor Harriots Arbeit 1631, zehn Jahre nach seinem Tod, veröffentlicht wurde. In seinem Buch Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas zeichnete Harriot Tabellen für Addition, Subtraktion, Multiplikation und Division von Monomen , Binomialen und Trinomen . Dann stellte er in einem zweiten Abschnitt die Gleichung aaba + ca = + bc auf und zeigte, dass diese mit der von ihm zuvor angegebenen Multiplikationsform übereinstimmt, die die Faktorisierung ( ab )( a + c ) ergibt .

Allgemeine Methoden

Die folgenden Methoden gelten für jeden Ausdruck, der eine Summe ist oder in eine Summe umgewandelt werden kann. Daher werden sie am häufigsten auf Polynome angewendet , obwohl sie auch angewendet werden können, wenn die Summenterme keine Monome sind, dh die Summenterme sind ein Produkt von Variablen und Konstanten.

Gemeinsamer Faktor

Es kann vorkommen, dass alle Terme einer Summe Produkte sind und dass einige Faktoren allen Termen gemeinsam sind. In diesem Fall erlaubt das Verteilungsgesetz , diesen gemeinsamen Faktor herauszurechnen. Bei mehreren solchen gemeinsamen Faktoren lohnt es sich, den größten solchen gemeinsamen Faktor aufzuteilen. Wenn es ganzzahlige Koeffizienten gibt, kann man auch den größten gemeinsamen Teiler dieser Koeffizienten herausrechnen.

Zum Beispiel,

da 2 der größte gemeinsame Teiler von 6, 8 und 10 ist und alle Terme teilt.

Gruppierung

Das Gruppieren von Begriffen kann die Verwendung anderer Methoden zum Erhalten einer Faktorisierung ermöglichen.

Zum Beispiel, um zu faktorisieren

man kann anmerken, dass die ersten beiden Terme einen gemeinsamen Faktor x haben und die letzten beiden Terme den gemeinsamen Faktor y haben . Daher

Dann zeigt eine einfache Inspektion den gemeinsamen Faktor x + 5 , was zur Faktorisierung führt

Im Allgemeinen funktioniert dies für Summen von 4 Termen, die als Produkt von zwei Binomialen erhalten wurden . Obwohl nicht häufig, kann dies auch für kompliziertere Beispiele funktionieren.

Addieren und Subtrahieren von Termen

Manchmal lässt eine Begriffsgruppierung einen Teil eines erkennbaren Musters erscheinen . Es ist dann nützlich, Terme hinzuzufügen, um das Muster zu vervollständigen, und sie zu subtrahieren, um den Wert des Ausdrucks nicht zu ändern.

Eine typische Anwendung hierfür ist die Quadratvervollständigung , um eine quadratische Formel zu erhalten .

Ein weiteres Beispiel ist die Faktorisierung von Wenn man die nicht-reelle Quadratwurzel von –1 einführt , die gewöhnlich mit i bezeichnet wird , dann hat man eine Differenz von Quadraten

Man kann aber auch eine Faktorisierung mit reellen Koeffizienten wünschen . Durch Addieren und Subtrahieren und Gruppieren von drei Termen kann man das Quadrat eines Binomials erkennen :

Subtrahieren und Addieren ergibt auch die Faktorisierung:

Diese Faktorisierungen funktionieren nicht nur über die komplexen Zahlen, sondern auch über alle Körper , in denen entweder –1, 2 oder –2 ein Quadrat ist. In einem endlichen Körper ist das Produkt zweier Nicht-Quadrate ein Quadrat; dies bedeutet , dass das Polynom , das ist nicht reduzierbar über die ganzen Zahlen, reduzierbar Modulo jede Primzahl . Zum Beispiel,

schon seit
schon seit
schon seit

Erkennbare Muster

Viele Identitäten bieten eine Gleichheit zwischen einer Summe und einem Produkt. Die obigen Verfahren können verwendet werden, um die Summenseite einer gewissen Identität in einem Ausdruck erscheinen zu lassen, die daher durch ein Produkt ersetzt werden kann.

Unten sind Identitäten aufgeführt, deren linke Seiten häufig als Muster verwendet werden (das bedeutet, dass die Variablen E und F , die in diesen Identitäten vorkommen, jeden Unterausdruck des Ausdrucks darstellen können, der faktorisiert werden muss.

Visueller Beweis der Unterschiede zwischen zwei Quadraten und zwei Würfeln
Zum Beispiel,
  • Summe/Differenz von zwei Würfeln
  • Differenz von zwei vierten Potenzen
  • Summe/Differenz von zwei n- ten Potenzen
In den folgenden Identitäten können die Faktoren oft weiter faktorisiert werden:
  • Differenz, gerader Exponent
  • Differenz, gerader oder ungerader Exponent
Dies ist ein Beispiel, das zeigt, dass die Faktoren viel größer sein können als die Summe, die faktorisiert wird.
  • Summe, ungerader Exponent
(erhalten durch Ändern von F um F in der vorhergehenden Formel)
  • Summe, gerader Exponent
Wenn der Exponent eine Zweierpotenz ist, kann der Ausdruck im Allgemeinen nicht faktorisiert werden, ohne komplexe Zahlen einzuführen (wenn E und F komplexe Zahlen enthalten, ist dies möglicherweise nicht der Fall). Wenn n einen ungeraden Teiler hat, dh wenn n = pq mit p ungerade ist, kann man die obige Formel (in "Summe, ungerader Exponent") anwenden auf
  • Trinome und kubische Formeln
  • Binomialerweiterungen
Visualisierung der Binomialentwicklung bis zur 4. Potenz
Der Binomialsatz liefert Muster, die leicht an den darin vorkommenden ganzen Zahlen zu erkennen sind
In geringem Maße:
Allgemeiner ausgedrückt sind die Koeffizienten der erweiterten Formen von und die Binomialkoeffizienten , die in der n- ten Reihe des Pascalschen Dreiecks erscheinen .

Wurzeln der Einheit

Die n- ten Einheitswurzeln sind die komplexen Zahlen, von denen jede eine Wurzel des Polynoms ist Sie sind also die Zahlen

zum

Daraus folgt, dass für zwei beliebige Ausdrücke E und F gilt:

Wenn E und F reelle Ausdrücke sind und man reelle Faktoren will, muss man jedes Paar komplex konjugierter Faktoren durch sein Produkt ersetzen . Da die komplex Konjugierte von ist und

man hat die folgenden reellen Faktorisierungen (man geht von einem zum anderen über, indem man k in nk oder n + 1 – k ändert und die üblichen trigonometrischen Formeln anwendet :

Die Kosinus , die in diesen Faktorisierungen erscheinen, sind algebraische Zahlen und können in Radikalen ausgedrückt werden (dies ist möglich, weil ihre Galois-Gruppe zyklisch ist); diese radikalen Ausdrücke sind jedoch zu kompliziert, um verwendet zu werden, außer bei niedrigen Werten von n . Zum Beispiel,

Oft möchte man eine Faktorisierung mit rationalen Koeffizienten. Eine solche Faktorisierung beinhaltet zyklotomische Polynome . Um rationale Faktorisierungen von Summen und Differenzen oder Potenzen auszudrücken, benötigen wir eine Notation für die Homogenisierung eines Polynoms : Wenn seine Homogenisierung das bivariate Polynom ist Dann gilt

wobei die Produkte über alle Teiler von n oder alle Teiler von 2 n , die n nicht teilen , genommen werden und das n- te zyklotomische Polynom ist.

Zum Beispiel,

da die Teiler von 6 1, 2, 3, 6 sind und die Teiler von 12, die 6 nicht teilen, 4 und 12 sind.

Polynome

Bei Polynomen hängt die Faktorisierung stark mit dem Problem der Lösung algebraischer Gleichungen zusammen . Eine algebraische Gleichung hat die Form

wobei P ( x ) ein Polynom in x mit einer Lösung dieser Gleichung (auch Wurzel des Polynoms genannt) ist ein Wert r von x mit

Wenn eine Faktorisierung von P ( x ) = 0 als Produkt zweier Polynome ist, dann sind die Wurzeln von P ( x ) die Vereinigung der Wurzeln von Q ( x ) und der Wurzeln von R ( x ) . Somit reduziert sich die Lösung von P ( x ) = 0 auf die einfacheren Probleme der Lösung von Q ( x ) = 0 und R ( x ) = 0 .

Umgekehrt behauptet der Faktorsatz , dass, wenn r eine Wurzel von P ( x ) = 0 ist , P ( x ) faktorisiert werden kann als

wobei Q ( x ) der Quotient der euklidischen Division von P ( x ) = 0 durch den linearen (Grad eins) Faktor xr ist .

Wenn die Koeffizienten von P ( x ) sind reale oder komplexe Zahlen, der Fundamentalsatz der Algebra behauptet , dass P ( x ) eine reelle oder komplexe Wurzel hat. Unter Verwendung des Faktorsatzes rekursiv ergibt sich, dass

wo sind die reellen oder komplexen Wurzeln von P , von denen einige möglicherweise wiederholt werden. Diese vollständige Faktorisierung ist bis auf die Reihenfolge der Faktoren eindeutig .

Wenn die Koeffizienten von P ( x ) reell sind, möchte man im Allgemeinen eine Faktorisierung, bei der Faktoren reelle Koeffizienten haben. In diesem Fall kann die vollständige Faktorisierung einige quadratische (Grad zwei) Faktoren aufweisen. Diese Faktorisierung kann leicht aus der obigen vollständigen Faktorisierung abgeleitet werden. In der Tat, wenn r = a + ib eine nicht-reelle Wurzel von P ( x ) ist , dann ist ihre komplex Konjugierte s = aib auch eine Wurzel von P ( x ) . Also das Produkt

ist ein Faktor von P ( x ) mit reellen Koeffizienten. Wiederholt man dies für alle nicht-reellen Faktoren, erhält man eine Faktorisierung mit linearen oder quadratischen reellen Faktoren.

Um diese reellen oder komplexen Faktorisierungen zu berechnen, benötigt man die Wurzeln des Polynoms, die möglicherweise nicht genau berechnet und nur mit Wurzelsuchalgorithmen angenähert werden .

In der Praxis haben die meisten interessierenden algebraischen Gleichungen ganzzahlige oder rationale Koeffizienten, und man kann eine Faktorisierung mit Faktoren der gleichen Art wünschen. Der fundamentale Satz der Arithmetik kann auf diesen Fall verallgemeinert werden und besagt, dass Polynome mit ganzzahligen oder rationalen Koeffizienten die eindeutige Faktorisierungseigenschaft haben . Genauer gesagt kann jedes Polynom mit rationalen Koeffizienten in ein Produkt faktorisiert werden

wobei q eine rationale Zahl ist und nicht konstante Polynome mit ganzzahligen Koeffizienten sind, die irreduzibel und primitiv sind ; Dies bedeutet, dass keines der Polynome als Produkt zweier Polynome (mit ganzzahligen Koeffizienten) geschrieben werden kann, die weder 1 noch –1 sind (Ganzzahlen werden als Polynome vom Grad Null betrachtet). Außerdem ist diese Faktorisierung bis auf die Reihenfolge der Faktoren und die Vorzeichen der Faktoren eindeutig.

Es gibt effiziente Algorithmen zur Berechnung dieser Faktorisierung, die in den meisten Computeralgebrasystemen implementiert sind. Siehe Faktorisierung von Polynomen . Leider sind diese Algorithmen zu kompliziert, um sie für Papier-und-Bleistift-Berechnungen zu verwenden. Abgesehen von den oben genannten Heuristiken sind nur wenige Methoden für Handberechnungen geeignet, die im Allgemeinen nur für Polynome niedrigen Grades mit wenigen von Null verschiedenen Koeffizienten funktionieren. Die wichtigsten solcher Methoden werden in den nächsten Unterabschnitten beschrieben.

Primitive-Teil- und Inhaltsfaktorisierung

Jedes Polynom mit rationalen Koeffizienten kann auf einzigartige Weise als Produkt einer rationalen Zahl und eines Polynoms mit ganzzahligen Koeffizienten faktorisiert werden, das primitiv ist (d. h. der größte gemeinsame Teiler der Koeffizienten ist 1) und hat a positiver führender Koeffizient (Koeffizient des Termes des höchsten Grades). Zum Beispiel:

Bei dieser Faktorisierung wird die rationale Zahl Inhalt genannt , und das primitive Polynom ist der primitive Teil . Die Berechnung dieser Faktorisierung kann wie folgt erfolgen: Zuerst alle Koeffizienten auf einen gemeinsamen Nenner reduzieren, um den Quotienten durch eine ganze Zahl q eines Polynoms mit ganzzahligen Koeffizienten zu erhalten. Dann teilt man den größeren gemeinsamen Teiler p der Koeffizienten dieses Polynoms auf, um den primitiven Teil zu erhalten, wobei der Inhalt schließlich, falls erforderlich, die Vorzeichen von p und alle Koeffizienten des primitiven Teils ändert .

Diese Faktorisierung kann zu einem Ergebnis führen, das größer als das ursprüngliche Polynom ist (normalerweise bei vielen teilerfremden Nennern), aber selbst wenn dies der Fall ist, ist der primitive Teil im Allgemeinen einfacher für die weitere Faktorisierung zu manipulieren.

Verwendung des Faktorsatzes

Der Faktorsatz besagt, dass wenn r eine Wurzel eines Polynoms ist

Bedeutung P ( r ) = 0 , dann gibt es eine Faktorisierung

wo

mit . Dann geben polynomiale lange Division oder synthetische Division :

Dies kann nützlich sein, wenn man eine Wurzel des Polynoms kennt oder erraten kann.

Zum Beispiel kann man leicht erkennen, dass die Summe seiner Koeffizienten 0 ist, also ist r = 1 eine Wurzel. Da r + 0 = 1 , und man hat

Rationale Wurzeln

Bei Polynomen mit Koeffizienten rationaler Zahlen kann man nach Wurzeln suchen, die rationale Zahlen sind. Primitive Teilinhaltsfaktorisierung (siehe oben ) reduziert das Problem der Suche nach rationalen Wurzeln auf den Fall von Polynomen mit ganzzahligen Koeffizienten, die keinen nicht-trivialen gemeinsamen Teiler haben .

Ist eine rationale Wurzel eines solchen Polynoms

der Faktorsatz zeigt, dass man eine Faktorisierung hat

wobei beiden Faktoren haben ganzzahligen Koeffizienten (die Tatsache , daß Q aus der obigen Formel für die Quotienten aus ganzzahligen Koeffizienten Ergebnissen hat P ( x ) durch ).

Ein Vergleich der Koeffizienten vom Grad n und der konstanten Koeffizienten in obiger Gleichheit zeigt, dass, wenn eine rationale Wurzel in reduzierter Form ist , dann q ein Teiler von und p ein Teiler von ist. Daher gibt es eine endliche Anzahl von Möglichkeiten für p und q , die systematisch untersucht werden können.

Wenn zum Beispiel das Polynom

hat eine rationale Wurzel mit q > 0 , dann muss p 6 teilen; das heißt, und q muss 2 teilen, d. h . Wenn x < 0 ist , sind alle Terme des Polynoms negativ, und daher kann eine Wurzel nicht negativ sein. Das heißt, man muss haben

Eine direkte Berechnung zeigt, dass nur eine Wurzel ist, also kann es keine andere rationale Wurzel geben. Die Anwendung des Faktorsatzes führt schließlich zur Faktorisierung

Quadratische Wechselstrommethode

Das obige Verfahren kann für quadratische Polynome angepasst werden , was zu dem AC-Verfahren der Faktorisierung führt.

Betrachten Sie das quadratische Polynom

mit ganzzahligen Koeffizienten. Wenn es eine rationale Wurzel hat, muss dessen Nenner dividieren ein gleichmäßig , und es kann als möglicherweise geschrieben werden reduzierbaren Fraktion von Vietas Formeln , die andere Wurzel

mit Somit ist auch die zweite Wurzel rational, und die zweite Formel von Vieta ergibt

das ist

Die Überprüfung aller Paare von ganzen Zahlen, deren Produkt ac ist, liefert die rationalen Wurzeln, falls vorhanden.

Betrachten wir zum Beispiel das quadratische Polynom

Die Betrachtung der Faktoren von ac = 36 führt zu 4 + 9 = 13 = b , was die beiden Wurzeln

und die Faktorisierung

Verwenden von Formeln für Polynomwurzeln

Jedes univariate quadratische Polynom kann mit der quadratischen Formel faktorisiert werden :

wobei und die beiden Nullstellen des Polynoms sind.

Wenn a, b, c alle reell sind , sind die Faktoren genau dann reell , wenn die Diskriminante nicht negativ ist. Andernfalls kann das quadratische Polynom nicht in nicht konstante reelle Faktoren zerlegt werden.

Die quadratische Formel gilt , wenn die Koeffizienten in jedem gehören Feld der Charakteristik von zwei unterschiedlichen, und insbesondere, für die Koeffizienten in einem endlichen Feld mit einer ungeraden Anzahl von Elementen.

Es gibt auch Formeln für Wurzeln kubischer und quartischer Polynome, die im Allgemeinen zu kompliziert für die praktische Anwendung sind. Der Satz von Abel-Ruffini zeigt, dass es für Polynome vom Grad fünf oder höher keine allgemeinen Wurzelformeln in Form von Radikalen gibt.

Verwenden von Beziehungen zwischen Wurzeln

Es kann vorkommen, dass man eine Beziehung zwischen den Nullstellen eines Polynoms und seinen Koeffizienten kennt. Die Verwendung dieses Wissens kann helfen, das Polynom zu faktorisieren und seine Wurzeln zu finden. Die Galois-Theorie basiert auf einer systematischen Untersuchung der Beziehungen zwischen Wurzeln und Koeffizienten, die Vietas Formeln einschließen .

Hier betrachten wir den einfacheren Fall, in dem zwei Wurzeln und eines Polynoms die Beziehung

wobei Q ein Polynom ist.

Dies impliziert, dass ist eine gemeinsame Wurzel von und It ist daher eine Wurzel des größten gemeinsamen Teilers dieser beiden Polynome. Daraus folgt, dass dieser größte gemeinsame Teiler ein nicht konstanter Faktor des euklidischen Algorithmus für Polynome ist, der die Berechnung dieses größten gemeinsamen Faktors ermöglicht.

Wenn man zum Beispiel weiß oder vermutet, dass: zwei Nullstellen hat, die sich zu Null summieren, kann man den euklidischen Algorithmus anwenden auf und Der erste Divisionsschritt besteht darin , den Rest von zu addieren

Dann ergibt die Division durch Null als neuen Rest und x – 5 als Quotienten, was zur vollständigen Faktorisierung führt

Eindeutige Faktorisierungsdomänen

Die ganzen Zahlen und die Polynome über ein Feld teilt die Eigenschaft der faktoriell, dass jedes Nicht - Null - Element ist , können in ein Produkt aus einem invertierbaren Elemente (A faktorisiert werden Einheit , ± 1 in dem Fall , von ganzen Zahlen) , und ein Produkt aus nicht reduzierbaren Elementen ( Primzahlen , im Fall von ganzen Zahlen), und diese Faktorisierung ist einzigartig bis auf die Neuordnung der Faktoren und das Verschieben der Einheiten zwischen den Faktoren. Integrale Domänen, die diese Eigenschaft teilen, werden als eindeutige Faktorisierungsdomänen (UFD) bezeichnet.

Größte gemeinsame Teiler existieren in UFDs, und umgekehrt ist jeder integrale Bereich, in dem größte gemeinsame Teiler existieren, ein UFD. Jede prinzipielle ideale Domäne ist ein UFD.

Ein euklidischer Bereich ist ein ganzzahliger Bereich, auf dem eine euklidische Division ähnlich der von ganzen Zahlen definiert ist. Jedes euklidische Gebiet ist ein prinzipielles Idealgebiet und somit ein UFD.

In einer euklidischen Domäne ermöglicht die euklidische Division die Definition eines euklidischen Algorithmus zum Berechnen der größten gemeinsamen Teiler. Dies impliziert jedoch nicht die Existenz eines Faktorisierungsalgorithmus. Es gibt ein explizites Beispiel für einen Körper F , bei dem es keinen Faktorisierungsalgorithmus im euklidischen Bereich F [ x ] der univariaten Polynome über F geben kann .

Ideale

In der algebraischen Zahlentheorie führte das Studium der diophantischen Gleichungen die Mathematiker im 19. Jahrhundert dazu, Verallgemeinerungen der ganzen Zahlen einzuführen, die als algebraische ganze Zahlen bezeichnet werden . Der erste Ring von algebraischen ganzen Zahlen , die in Betracht gezogen wurden, waren Gaußsche ganze Zahlen und Eisenstein-Zahlen , die mit gewöhnlichen ganzen Zahlen die Eigenschaft teilen, ideale Hauptgebiete zu sein , und somit die einzigartige Faktorisierungseigenschaft haben .

Leider stellte sich bald heraus, dass die meisten Ringe algebraischer Ganzzahlen keine Hauptringe sind und keine eindeutige Faktorisierung aufweisen. Das einfachste Beispiel ist, in dem

und alle diese Faktoren sind irreduzibel .

Dieses Fehlen einer eindeutigen Faktorisierung ist eine Hauptschwierigkeit bei der Lösung diophantischer Gleichungen. Zum Beispiel basierten viele falsche Beweise von Fermats letztem Theorem (wahrscheinlich einschließlich Fermats "wirklich wunderbarer Beweis dafür, den dieser Spielraum zu eng ist" ) auf der impliziten Annahme einer eindeutigen Faktorisierung.

Diese Schwierigkeit wurde von Dedekind gelöst , der bewies, dass die Ringe algebraischer Ganzzahlen eine einzigartige Faktorisierung von Idealen haben : In diesen Ringen ist jedes Ideal ein Produkt von Primidealen , und diese Faktorisierung ist in der Reihenfolge der Faktoren einzigartig. Die ganzzahligen Gebiete , die diese einzigartige Faktorisierungseigenschaft haben, werden jetzt Dedekind-Gebiete genannt . Sie haben viele schöne Eigenschaften, die sie grundlegend für die algebraische Zahlentheorie machen.

Matrizen

Matrixringe sind nicht kommutativ und haben keine eindeutige Faktorisierung: Im Allgemeinen gibt es viele Möglichkeiten, eine Matrix als Produkt von Matrizen zu schreiben . Somit besteht das Faktorisierungsproblem darin, Faktoren bestimmter Typen zu finden. Zum Beispiel ergibt die LU-Zerlegung eine Matrix als das Produkt einer unteren Dreiecksmatrix durch eine obere Dreiecksmatrix . Da dies nicht immer möglich ist, betrachtet man im Allgemeinen die "LUP-Zerlegung" mit einer Permutationsmatrix als dritten Faktor.

Siehe Matrixzerlegung für die gebräuchlichsten Typen von Matrixfaktorisierungen.

Eine logische Matrix repräsentiert eine binäre Relation , und die Matrixmultiplikation entspricht der Zusammensetzung von Relationen . Die Zerlegung einer Relation durch Faktorisierung dient dazu, die Natur der Relation zu profilieren, beispielsweise eine difunktionale Relation.

Siehe auch

Anmerkungen

Verweise

  • Burnside, William Schnee ; Panton, Arthur William (1960) [1912], The Theory of Equations mit einer Einführung in die Theorie der binären algebraischen Formen (Band 1) , Dover
  • Dickson, Leonard Eugene (1922), Erster Kurs in der Theorie der Gleichungen , New York: John Wiley & Sons
  • Fite, William Benjamin (1921), College Algebra (überarbeitet) , Boston: DC Heath & Co.
  • Klein, Felix (1925), Elementare Mathematik aus einem fortgeschrittenen Standpunkt; Arithmetik, Algebra, Analysis , Dover
  • Selby, Samuel M., CRC Standard Mathematical Tables (18. Aufl.), The Chemical Rubber Co.

Externe Links