<<

. 29
( 60 .)



>>

χf (x) = (’1)n (x ’ »)m» ,
»∈spec(f )

wobei m» die algebraische Vielfachheit von » ist. Daraus folgt n = »∈spec(f ) m» .
Wenn wir voraussetzen, dass die algebraischen Vielfachheiten gleich den geome-
trischen sind, folgt also (6.8).
Zum Schluss noch ein einfaches Beispiel eines irreduziblen Polynoms von Grad
3:

Beispiel 6.9 In Z2 [x] ist p (x) = 1 + x + x3 irreduzibel

Beweis. p (1) = p (0) = 1 = 0, d.h. das Polynom hat keine Nullstellen. H¨tte a
das Polynom einen echten Teiler: p (x) = q (x) h (x) , so musste entweder q (x)
¨
oder h (x) Grad 1 haben. Jedes Polynom von Grad 1 hat jedoch (genau) eine
Nullstelle. Diese Nullstelle musste auch eine Nullstelle von p (x) sein. Somit folgt,
¨
dass p (x) keine Zerlegung hat.

6.4.3 Ideale, grosster gemeinsamer Teiler, Euklidscher Algorithmus
¨
Vorbemerkung: Die De¬nitionen und Lemmas in diesem und dem folgenden Un-
terkapitel sind nur fur den Polynomring angegeben. Sie k¨nnen aber allgemeiner
o
¨
fur nullteilerfreie Ringe mit Eins formuliert werden. Das einfachste Beispiel fur
¨ ¨
einen solchen Ring ist Z. Es ist fur die Anschauung sehr hilfreich, die Aussagen
¨
immer an diesem Beispiel zu uberprufen.
¨ ¨

De¬nition 6.14 Eine nicht leere Teilmenge J ‚ K [x] heisst Ideal, falls die
folgenden Bedingungen erfullt sind:
¨

J1 J = {0}

J2 (J, +) ist eine Untergruppe von K [x]

126
J3 Sind p (x) ∈ J und q (x) ∈ K [x] , so ist p (x) q (x) ∈ J.

Ist A ‚ K [x] eine nicht leere Teilmenge mit 0 ∈ A, so ist das von A erzeugte
/
Ideal JA de¬niert durch
n
hj (x) aj (x) : n ∈ N, aj (x) ∈ A, hj (x) ∈ K [x] .
JA :=
j=1

Im Spezialfall A = {a (x)} , a (x) = 0, heisst JA das von a (x) erzeugte Haupt-
ideal. Man schreibt dann (a (x)) fur JA .
¨

Man beachte, dass in J3 q (x) beliebig ist. J3 besagt also nicht nur, dass
J abgeschlossen gegenuber Produkten in J ist, sondern das jedes polynomiale
¨
Vielfache eines Elementes in J wieder in J ist.

Lemma 6.6 Ist A ‚ K [x] , A = …, 0 ∈ A, so ist JA das kleinste Ideal, das A
/
enth¨lt, d.h. es gelten die folgenden beiden Eigenschaften:
a
a) JA ist ein Ideal mit A ‚ JA .
b) Ist I ein Ideal mit A ‚ I so gilt JA ‚ I.
¨
Beweis. Der ganz einfache Beweis sei dem Leser als Ubungsaufgabe uberlas-
¨
sen.

Bemerkung 6.5 a) Enth¨lt ein Ideal J ein konstantes Polynom = 0, so ist
a
J = K [x] . In der Tat: Ist das konstante Polynom a ∈ J, a = 0, so folgt fur jedes
¨
Polynom p (x) :
p (x) = a (p (x) /a) ∈ J
wegen J3.
b) J = (a (x)) mit a (x) = 0 gilt genau dann, wenn a (x) | p (x) fur jedes
¨
Polynom p (x) ∈ J gilt.
c) (a (x)) = (a (x)) gilt genau dann wenn ± ∈ K\ {0} existiert mit a (x) =
±a (x) . Dies folgt sofort aus Bemerkung 6.4 c). Zu jedem Hauptideal J existiert
also ein eindeutiges normiertes Polynom a (x) mit J = (a (x)) .

Satz 6.15 In K [x] ist jedes Ideal ein Hauptideal. (Man sagt, K [x] sei ein
Hauptidealring.)

Beweis. Wegen J = {0} existiert p (x) ∈ J, p (x) = 0. Sei a (x) ein beliebiges
Polynom von minimalem Grad ≥ 0 in J. Wir zeigen, dass J = (a (x)) ist.
Sei p (x) ∈ J, p (x) = 0. Wir fuhren eine Division mit Rest durch:
¨

p (x) = h (x) a (x) + r (x) ,

mit grad (r (x)) < grad (a (x)) . Nun ist aber wegen J3 h (x) a (x) ∈ J und dann
wegen J2 r (x) = p (x) ’ h (x) a (x) ∈ J. Da a (x) minimalen Grad aller Polynome

127
= 0 in J hatte, folgt r (x) = 0. Somit ist p (x) = h (x) a (x) . D.h., jedes Polynom
in J, das von Null verschieden ist, ist als h (x) a (x) darstellbar.
Ist A ‚ K [x] , 0 ∈ A, so wissen wir aus dem obigen Satz, dass ein Polynom
/
a (x) = 0 existiert mit JA = (a (x)) . Nach der Bemerkung 6.5 c) wissen wir, dass
a (x) eindeutig ist bis auf Multiplikation mit einem K¨rperelement = 0. Somit
o
ist 6.5 a (x) eindeutig, wenn es als normiert vorausgesetzt wird.
Wir betrachten nun eine nicht leere Teilmenge A ‚ K [x] , 0 ∈ A und das
/
davon erzeugte Ideal. Nach dem vorangegangenen Satz wissen wir, dass JA =
(a (x)), wobei wir a (x) als normiert voraussetzen.

Lemma 6.7 a (x) hat die folgenden Eigenschaften:
a) a (x) | p (x) fur alle p (x) ∈ A
¨
b) Ist b (x) ∈ K [x] , b (x) = 0 mit b (x) | p (x) fur alle p (x) ∈ A, so gilt
¨
b (x) | a (x) .
a (x) ist eindeutig charakterisiert durch diese Eigenschaften und die Bedin-
gung, dass es normiert ist.

Beweis. a) folgt aus A ‚ JA = (a (x)) . Wir zeigen b): Wegen a (x) ∈ JA
folgt, dass es Polynome p1 (x) , . . . , pn (x) ∈ A und h1 (x) , . . . , hn (x) ∈ K [x] gibt
mit a (x) = n hi (x) pi (x) . Da b (x) | pi (x) gilt folgt sofort b (x) | a (x) .
i=1
Sind a (x) und a (x) zwei normierte Polynome mit den Eigenschaften a) und
b) so gilt a (x) | a (x) und a (x) | a (x) . Daraus folgt a (x) = a (x) .
Das Lemma legt die folgende De¬nition nahe:

De¬nition 6.15 Sei A ‚ K [x] , A = …, 0 ∈ A. Dann bezeichnet man das eindeu-
/
tige normierte Polynom a (x) mit (a (x)) = JA als den gr¨ssten gemeinsamen
o
Teiler von A. Notation: a (x) = ggT (A) . Sind p1 (x) , . . . , pn (x) endlich viele
von 0 verschiedene Polynome, so schreiben wir ggT (p1 (x) , . . . , pn (x)) fur den
¨
gr¨ssten gemeinsamen Teiler von {p1 (x) , . . . , pn (x)} .
o

Bemerkung 6.6 Nach der obigen Diskussion ist a (x) = ggT (p1 (x) , . . . , pn (x))
eindeutig durch die folgenden Eigenschaften charakterisiert

• a (x) ist normiert

• a (x) | pi (x) fur i = 1, . . . , n
¨

• Es existieren Polynome h1 (x) , . . . , hn (x) = 0 mit
n
a (x) = hi (x) pi (x) .
i=1




128
Beweis. Der normierte ggT a (x) ist eindeutig dadurch charakterisiert, dass
er alle Polynome pi (x) teilt und gleichzeitig Element des Ideals J{p1 (x),...,pn (x)} ist.
Letzteres ist aber nichts anderes als der dritte Punkt der obigen Liste.
Wir betrachten den Spezialfall, wo die pi (x) teilerfremd sind (siehe De¬nition
6.10). Dies bedeutet, dass es kein nicht konstantes Polynom gibt, das alle pi (x)
teilt. Demzufolge ist ggT (p1 (x) , . . . , pn (x)) = 1. Nach dem dritten Punkt in
der obigen Bemerkung existieren dann Polynome h1 (x) , . . . , hn (x) = 0 mit 1 =
n
i=1 hi (x) pi (x) . Damit gelangen wir zu dem folgenden Lemma:

Lemma 6.8 n Polynome p1 (x) , . . . , pn (x) = 0 sind genau dann teilerfremd,
wenn es Polynome h1 (x) , . . . , hn (x) ∈ K [x] gibt mit
n
1= hi (x) pi (x) . (6.9)
i=1

Beweis. Die Tatsache, dass die Eigenschaft der Teilerfremdheit die Existenz
von Polynomen hi (x) impliziert, sodass die obige Gleichung erfullt ist, haben wir
¨
schon eben diskutiert. Umgekehrt teilt naturlich 1 alle Polynome, sodass nach
¨
der vorangegangenen Bemerkung die Existenz der hi (x) mit (6.9) auch impliziert,
dass 1 der gr¨sste gemeinsame Teiler ist, d.h. dass p1 (x) , . . . , pn (x) teilerfremd
o
sind.
Wir diskutieren nun kurz den Euklidschen Algorithmus zur Bestimmung
des ggT von zwei Polynomen. Der Einfachheit halber beschr¨nken wir uns auf
a
zwei Polynome; der Algorithmus kann jedoch leicht verallgemeinert werden. Die-
ser Algorithmus ist ausserordentlich wichtig und spielt in der Kodierungstheorie
eine ganz herausragende Rolle. Die schnellen Dekodierungsalgorithmen, die fur ¨
die Codes benutzt werden, die in den CDs verwendet werden, benutzen Varianten
¨ ¨
des Euklidschen Algorithmus.
Hier der Algorithmus zur Berechnung von ggT (p (x) , q (x)) . p (x) , q (x) = 0.
Wir k¨nnen voraussetzen, dass grad (q (x)) ¤ grad (p (x)) gilt. Wir de¬nieren
o
l1 (x) := p (x) und l2 (x) := q (x) , und de¬nieren ln (x) rekursiv mit einer Division
mit Rest:
ln’1 (x) = hn (x) ln (x) + ln+1 (x) , n ≥ 2, (6.10)
mit grad (ln+1 (x)) < grad (ln (x)) . Da der Grad bei jeder Iteration f¨llt, existiert
a

N := min {n : ln+1 (x) = 0} .

Lemma 6.9 Der ggT (p (x) , q (x)) ist das Polynom lN (x) nach Normierung.

Beweis. Wir beweisen die Eigenschaften a)-c) der vorangegangenen Be-
merkung 6.6. a) ist klar. Wegen lN +1 (x) = 0 folgt lN (x) | lN ’1 (x) . Wegen
lN ’2 (x) = hN ’1 (x) lN ’1 +lN (x) und lN (x) | lN ’1 (x) folgt lN (x) | lN ’2 (x) . F¨hrt
a
man in dieser Weise weiter, so folgt sehr einfach, dass lN (x) alle li (x) teilt,
1 ¤ i ¤ N ’ 1. Damit ist b) der Bemerkung bewiesen.

129
Beweis von c). Wir beweisen mit Induktion nach n, dass ln (x) eine Darstel-
lung
ln (x) = an (x) p (x) + bn (x) q (x) (6.11)
hat, wobei an (x) , bn (x) ∈ K [x] sind, wobei wir naturlich nur an n ¤ N interes-
¨
siert sind. Fur n = 1, 2 ist das trivial. Sei 2 ¤ n < N. Wir verwenden (6.10) und
¨
wenden die Induktionsvoraussetzung auf ln (x) und ln’1 (x) an. Somit erhalten
wir

ln+1 (x) = ln’1 (x) ’ hn (x) ln (x)
= an’1 (x) p (x) + bn’1 (x) q (x) ’ hn (x) (an (x) p (x) + bn (x) q (x))
= [an’1 (x) ’ hn (x) an (x)] p (x) + [bn’1 (x) ’ hn (x) bn (x)] q (x) .

Mit an+1 (x) := an’1 (x) ’ hn (x) an (x) und bn+1 (x) := bn’1 (x) ’hn (x) bn (x) ist
(6.11) fur n + 1 bewiesen.
¨
Damit folgt, dass auch lN (x) eine derartige Darstellung hat.
Somit ist gezeigt, dass der Euklidsche Algorithmus tats¨chlich zum gr¨ssten
a o
gemeinsamen Teiler fuhrt.
¨

Beispiel 6.10

p (x) = x4 + x3 + x + 1
q (x) = x3 + 2x2 + 2x + 1.

Dann ist
p (x) = (x ’ 1) q (x) + 2x + 2,
12
q (x) = (2x + 2) x + x + 1 + 0.
2
Demzufolge ist
ggT (p (x) , q (x)) = x + 1.

6.4.4 Primfaktorzerlegung von Polynomen
Um uns nicht st¨ndig zu wiederholen, legen wir fur dieses Unterkapitel die Kon-
a ¨
vention fest, dass alle betrachteten Polynome = 0 und normiert sind, d.h. mit
hochstem Koe¬zienten 1.
¨

Lemma 6.10 Seien h (x) , p1 (x) , . . . , pn (x) Polynome, und fur jedes i seien die
¨
zwei Polynome h (x) und pi (x) teilerfremd. Dann sind die beiden Polynome h (x)
und p1 (x) · · · · · pn (x) teilerfremd.

Beweis. Wir fuhren Induktion nach n. Fur n = 1 ist nichts zu beweisen. Sei
¨ ¨
also n ≥ 2. Nach Induktionsvoraussetzung sind h (x) und p1 (x) · · · · · pn’1 (x)
teilerfremd und nach Voraussetzung h (x) und pn (x) und wir mussen nun zeigen,
¨

130
dass h (x) und (p1 (x) · · · · · pn’1 (x)) · pn (x) teilerfremd sind. Es genugt also, den
¨
Fall n = 2 zu betrachten.
Nach Lemma 6.8 existieren Polynome r1 (x) , r2 (x) , l1 (x) , l2 (x) mit

<<

. 29
( 60 .)



>>