[figure: TU CLAUSTHAL; INSTITUT FÜR MATHEMATIK; Prof. Dr. W. Klotz; Lineare Algebra II; SS 2000; Übungsblatt 6]

Faktorisierung von Polynomen

Analog zur Primteilerzerlegung von ganzen Zahlen will man oft Polynome in irreduzible Polynome zerlegen. Während bei den Zahlen aber offensichtlich nur endlich viele mögliche Zahlen als Faktoren in Frage kommen, ist dies bei Polynomen nicht offensichtlich. In dieser Übung werden wir Methoden kennenlernen, Polynome zu faktorisieren, bzw. zu erkennen, dass sie unzerlegbar sind.

1. Ein Polynom, das über ℤ irreduzibel ist, kann natürlich über ℂ reduzibel sein, z.B. f(x) = x^{2} + 1. Analog ist x^{2} − 2 über ℚ irreduzibel, aber über ℚ(\sqrt{2}) oder über ℝ reduzibel.

2. Der Fundamentalsatz der Algebra besagt, dass jedes Polynome f ∈ ℂ[x] über ℂ in lineare Faktoren zerfällt, bzw. dass das Polynom n komplexe Nullstellen hat, wobei deg f = n ist. Über ℝ zerfallen Polynome in lineare oder quadratische Faktoren. Da ein Beweis dieser Tatsachen naturgemäß Eigenschaften der reellen Zahlen ausnützt (z.B. Zwischenwertsatz), wird der Beweis meist im Rahmen der Analysisvorlesungen gegeben. Es sind auch zahlreiche elegante Beweise bekannt, die Kenntnisse über Funktionentheorie voraussetzen.

3. Besonders wichtig ist die Faktorisierung über ℚ.

Satz (Gaußsches Lemma): Ist ein Polynom f mit ganzzahligen Koeffizienten über ℤ irreduzibel, so ist es auch über ℚ irreduzibel. Andersherum induziert eine Faktorisierung über ℚ auch eine solche über ℤ. Es reicht daher, nach Faktoren mit ganzzahligen Koeffizienten zu suchen.

4. Satz (Eisensteinsches Irreduzibilitätskriterium):

Sei f ∈ ℤ[x] ein Polynom mit f(x) = a_{n}x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0}. Weiter sei p eine Primzahl. Wenn die folgenden Bedingungen erfüllt sind

i) a_{n} ≢ 0 mod p
ii) a_{i} ≡ 0 mod p für i = 0, ⋯, n − 1
iii) a_{0} ≢ 0 mod p^{2},

dann ist f irreduzibel über ℚ. Dies ist ein hinreichendes, aber kein notwendiges Kriterium.

5. Beispiele: Warum sind folgende Polynome über ℚ irreduzibel?

f(x) = x^{5} + 3x^{2} + 3, f(x) = x^{2} + x + 1, f(x) = x^{5} + 3x^{2} + 1.

6. Wir wollen einen Algorithmus skizzieren, mit dem man Polynome faktorisieren kann. Er zeigt, dass doch nur endlich viele Faktoren in Frage kommen. Der Algorithmus wurde bereits von Kronecker (1823-1891) beschrieben. a) Zunächst eine Bemerkung über Polynominterpolation. Wenn man die Werte

eines Polynoms an n + 1 Stellen (x_{i}, y_{i}) vorgibt, so gibt es genau ein Polynom f vom Grad kleiner oder gleich n, das diese Werte annimmt. Man kann dies Polynom sogar explizit angeben (Lagrange-Polynom, Lagrange (1736-1813)):

f(x) = ∑_{i=0}^{n} y_{i} \frac{(x − x_{1}) ⋯ (x − x_{i−1})(x − x_{i+1}) ⋯ (x − x_{n})}{(x_{i} − x_{1}) ⋯ (x_{i} − x_{i−1})(x_{i} − x_{i+1}) ⋯ (x_{i} − x_{n})}.

b) Wenn das Polynom g ein Teiler vom Polynom f ist, also f = gh gilt, so gilt auch an jeder einzelnen Stelle g(x_{i}) | f(x_{i}). Wenn f überhaupt einen Teiler hat, dann auch einen mit Grad kleiner oder gleich \frac{n}{2}. Wenn man nun an r = [\frac{n}{2}] + 1 vielen Stellen x_{0}, ⋯, x_{r} die Funktionswerte von f auswertet, so erhält man alle (endlich vielen) in Frage kommenden Werte von g(x_{i}) als Teiler von f(x_{i}). Da zu jeder Wahl (g(x_{0}), ⋯, g(x_{r})) genau ein Interpolationspolynom gehört, kann man auf diese Weise alle (endlich vielen) in Frage kommenden Faktoren g von f aufzählen und testen.

c) Beispiel: Sei f(x) = x^{4} + x + 1. f hat keinen linearen Faktor, da f keine ganzzahlige Nullstelle hat. Sei f = gh und deg g = 2. die Stellen x_{0} = −1, x_{1} = 0, x_{1} = 1 erscheinen besonders geeignet, da hier f(x_{i}) aus wenigen Faktoren besteht. f(−1) = 1, f(0) = 1, f(1) = 3. Daher ist g(−1) = ±1, g(0) = ±1, g(1) = ±1, ±3. Es kommen also nur 16 verschiedene Polynome g als Teiler von f in Frage. In einer solchen Situation reicht oft auch ein Ansatz mit unbestimmten Koeffizienten:

f(x) = x^{4} + x + 1 = (x^{2} + ax + b)(x^{2} + cx + d).

7. Eine andere Eigenschaft von Faktoren:

Die Koeffizienten von einem Faktor g können mittels der Koeffizienten von f beschränkt werden: Das Polynom f habe den Grad n, das Polynom g den Grad m. Sei H(f) der betragsmäßig größte Koeffizient von f, und H(g) der von g. Dann gilt H(g) ≤ 2^{m} \sqrt{n + 1}H(f).

8. In der Praxis wird man ein Polynom nicht über ℤ, sondern über geeigneten endlichen Körpern ℤ_{p} faktorisieren. Wenn das Polynom sich über einem ℤ_{p} als irreduzibel erweist, ist es auch über ℤ irreduzibel. Andererseits kann das Wissen über die Faktoren in ℤ_{p} modulo mehrerer Primzahlen zusammengesetzt werden.