Lineare Algebra, Teil I - mathematik.tu-dortmund.de · Lineare Algebra, Teil I 11. Oktober 2010 0. Kapitel I. Grundbegriﬀe Inhalt: 1. Logik 2. Mengen und Abbildungen 3. Primfaktorzerlegung

Lineare Algebra, Teil I

(Folien zur Vorlesung)Joachim Stockler

Auszuge aus dem Vorlesungsskript von Prof. Rudolf Scharlau aus dem WS2009/10 werden auf den Folien verwendet. Fur die Bereitstellung dieses

Materials und der Tex-Files danke ich herzlich.

Lineare Algebra, Teil I 11. Oktober 2010 0

Kapitel I. Grundbegriffe

Inhalt:

1. Logik

2. Mengen und Abbildungen

3. Primfaktorzerlegung und euklidischer Algorithmus

4. Algebraische Strukturen: Gruppe, Ring, Korper

5. Aquivalenzrelationen

6. Der Korper der komplexen Zahlen


Logik Definition: Aussagen

1 Logik

Die Vorlesung beginnt mit einem kleinen Einstieg in die Aussagenlogik. Dies sollspater das Verstandnis auch bei komplizierteren Beweisgangen erleichtern.

1.1 Definition: Aussagen

Eine Aussage im Sinne der Logik ist eine sprachliche Formulierung, die entwederwahr (TRUE) oder falsch (FALSE) ist.


Logik Definition: Logische Verknupfungen

1.3 Definition: Logische Verknupfungen

Aussagen konnen miteinander verknupft werden. Die grundlegendenVerknupfungen werden durch die folgenden Wahrheitstafeln definiert.

a) Logisches UND:

A B A ∧ Bw w ww f ff w ff f f

Entspricht dem sprachlichen “sowohl ...

als auch”

b) Logisches ODER:

A B A ∨ Bw w ww f wf w wf f f

Entspricht dem sprachlichen nicht-

exklusiven “oder”


Logik Definition: Logische Verknupfungen

c) Negation:

A ¬Aw ff w

Sprich “nicht A”

d) Logische Folgerung, Implikation:

A B A ⇒ Bw w ww f ff w wf f w

Sprich “Aus A folgt B” oder “Wenn A, dann

B”

e) Aquivalenz:

A B A ⇔ Bw w ww f ff w ff f w

Sprich “A ist aquivalent zu B” oder “A

genau dann, wenn B”


Logik Bemerkung

1.5 Bemerkung: Das Wesen einer mathematischen Theorie besteht darin,mathematische Strukturen anhand von Axiomen aufzustellen und hieraus weitereAussagen herzuleiten. Die Axiome sind Aussagen, deren Gultigkeit vorausgesetztwird (Wahrheitswert TRUE) und die in einer Definition der Strukturzusammengefasst werden. Die weiteren Aussagen (sog. Satze, Theoreme,Lemmata) sind kompliziertere Aussagen, die durch logische Schlusse aus denAxiomen hergeleitet werden. Die Herleitung nennt man Beweis.


Logik Bemerkung: Beweismethoden

1.6 Bemerkung: BeweismethodenFur Beweise (oder einzelne Teile von Beweisen) gibt es gangige Methoden:

a) direkter Beweis: A =⇒ B

b) indirekter Beweis: Um A =⇒ B zu zeigen, beweist man stattdessen¬B =⇒ ¬A (vgl. Beispiel ??)

c) Widerspruchsbeweis: Um A zu zeigen, nimmt man ¬A als wahr an(Widerspruchsannahme) und schließt so lange auf weitere wahre Aussagen,bis eine Aussage entsteht, die im Widerspruch zur Voraussetzung, zu einemAxiom oder zur Widerspruchsannahme steht.

d) Aufteilung der Aquivalenz: Um A ⇐⇒ B zu zeigen, beweist man(A =⇒ B) ∧ (B =⇒ A). (Man prufe dies anhand der Wahrheitstafeln.)

e) Ringschluss: Sind mehrere Aussagen A1, A2, . . . ,An als aquivalentnachzuweisen, zeigt man

(A1 =⇒ A2) ∧ (A2 =⇒ A3) ∧ · · · ∧ (An−1 =⇒ An) ∧ (An =⇒ A1).


Logik Bemerkung: Induktionsbeweis

1.8 Bemerkung: Induktionsbeweis

Fur jede naturliche Zahl n sei eine Aussage A(n) formuliert. Wenn wir beweisen,dass die folgenden beiden Aussagen gelten:

(i) A(1) ist wahr. (Induktionsanfang)

(ii) Wenn fur eine naturliche Zahl n die Aussage A(n) wahr ist, dann ist auchA(n + 1) wahr. (Induktionsschluss von n auf n + 1)

Dann ist bewiesen, dass die Aussage A(n) fur jede naturliche Zahl n wahr ist.

Formal lautet das Induktionsprinzip:

(A(1) ∧ “Fur alle n ∈ N gilt A(n) ⇒ A(n + 1)”) =⇒ “Fur alle n ∈ N gilt A(n)”


Logik Bemerkung: Varianten des Induktionsbeweises

1.10 Bemerkung: Varianten des Induktionsbeweises

Als Induktionsanfang beweist man A(n0) fur ein n0 ∈ Z. Gilt dann derInduktionsschluss von n nach n + 1 fur jedes n ≥ n0, so ist die Aussage A(n)fur alle n ≥ n0 bewiesen.

(A(n0) ∧ “Fur alle n ∈ Z mit n ≥ n0 gilt A(n) ⇒ A(n + 1)”)

=⇒ “Fur alle n ∈ Z mit n ≥ n0 gilt A(n)”

Als Voraussetzung fur den Induktionsschluss von n nach n + 1 darf manverwenden, dass A(k) wahr ist fur alle 1 ≤ k ≤ n:

(A(1) ∧ “Fur alle n ∈ N gilt (A(1) ∧ A(2) ∧ · · · ∧ A(n)) ⇒ A(n + 1)”)

=⇒ “Fur alle n ∈ N gilt A(n)”


Logik Notation: Quantoren

1.11 Notation: Quantoren

Zur Abkurzung verwendet man in Aussagen die folgenden Quantoren:

∀ heißt “fur alle”∃ heißt “es gibt ein”, “es existiert”∄ heißt “es gibt kein”, “es existiert kein”


Mengen und Abbildungen Erlauterung

2 Mengen und Abbildungen

Im Zentrum mathematischer Theorien steht die Definition abstrakter,ubergreifender Strukturen und deren Verknupfung. Wir beginnen hier mitBegriffen aus der “Naiven Mengenlehre”.

2.1 Erlauterung: (Georg Cantor 1845 - 1918)

Eine Menge ist eine Zusammenfassung bestimmter wohlunterschiedener Objekteunserer Anschauung oder unseres Denkens – welche die Elemente der Mengegenannt werden – zu einem Ganzen.

Schreibweise:x ∈ M “x ist ein Element von M”x 6∈ M “x ist nicht ein Element von M”


Mengen und Abbildungen Standard-Bezeichnungen

2.2 Standard-Bezeichnungen

N die Menge der naturlichen Zahlen: 1, 2, 3, 4, . . .N0 die Menge der naturlichen Zahlen mit Null: 0, 1, 2, 3, 4, . . .Z die Menge der ganzen Zahlen: . . . , −3, −2, −1, 0, 1, 2, 3, . . .

Q die Menge der rationalen Zahlen:m

n| m ∈ Z, n ∈ N

R die Menge der reellen Zahlen

C die Menge der komplexen Zahlen

∅ die leere Menge

Zur Veranschaulichung dient die Zahlengerade.

0 1 2 3−1−2√2 e1/2

Jedem Punkt auf der Zahlengeraden entspricht genau eine reelle Zahl, undumgekehrt.


Mengen und Abbildungen Definition

2.3 Definition

Eine Menge M heißt endlich, wenn sie aus nur endlich vielen Elementen besteht.In diesem Fall heißt die Anzahl der Elemente die Machtigkeit oder auchKardinalitat von M , in Zeichen: |M | oder #M .


Mengen und Abbildungen Definition: Teilmenge

2.5 Definition: Teilmenge

a) Eine Menge N heißt Teilmenge einer Menge M , falls jedes Element von Nauch Element von M ist. Die entsprechende Beziehung zwischen N und Mheißt auch Inklusion (von N in M).

Bezeichnung: N ⊆ M .

b) Eine Menge N heißt echte Teilmenge einer Menge M , falls N Teilmenge vonM und N 6= M ist. Die entsprechende Beziehung zwischen N und M heißtauch echte Inklusion (von N in M).

Bezeichnung: N ( M oder N & M .

Bemerkung: Die Gleichheit M = N von Mengen wird oft mit folgender Aquivalenzgezeigt:

M = N ⇐⇒ (M ⊆ N) ∧ (N ⊆ M)


Mengen und Abbildungen Definition: Mengenverknupfungen

2.6 Definition: Mengenverknupfungen

M ∩ N = x | x ∈ M und x ∈ N Durchschnitt, Schnittmenge

M ∪ N = x | x ∈ M oder x ∈ N Vereinigung

M \ N = x | x ∈ M und x 6∈ N Differenz(menge) “M ohne N”

Bemerkung:

a) Falls M ∩ N = ∅ gilt, nennen wir M und N disjunkt.

b) Die Vereinigung disjunkter Mengen M und N wird auch mit M∪N bezeichnet.

c) In manchen Situationen ist eine Grundmenge Ω vorgegeben und allebetrachteten Mengen sind Teilmengen von Ω. Dann (und nur dann!)verwenden wir die abkurzende Schreibweise

M := Ω \M oder ∁M := Ω \M .


Mengen und Abbildungen Satz: Rechenregeln

2.7 Satz: Rechenregeln

a) Kommutativitat von ∪, ∩: M ∩ N = N ∩M , M ∪ N = N ∪M

b) Assoziativitat von ∪, ∩: (L ∩M) ∩ N = L ∩ (M ∩ N)

(L ∪M) ∪ N = L ∪ (M ∪ N)

c) Distributivitat von ∪, ∩: L ∪ (M ∩ N) = (L ∪M) ∩ (L ∪ N)

L ∩ (M ∪ N) = (L ∩M) ∪ (L ∩ N)

d) Vereinfachungen: (M \ N) ∪ N = M ∪ N , (M \ N) ∩ N = ∅

e) de Morgansche Regeln: L \ (M ∩ N) = (L \M) ∪ (L \ N)

L \ (M ∪ N) = (L \M) ∩ (L \ N)


Mengen und Abbildungen Definition: Kartesisches Produkt

2.9 Definition: Kartesisches Produkt

a) Das kartesische Produkta zweier Mengen A und B (auch Produktmenge)genannt) ist definiert als

A× B := (a, b) | a ∈ A und b ∈ B.

Ein Element (a, b) ∈ A× B heißt geordnetes Paar.

b) Allgemeiner ist das kartesische Produkt von n Mengen A1,A2, . . . ,An

definiert als

A1 × A2 × · · · × An = (a1, a2, . . . , an) | ai ∈ Ai fur i = 1, . . . , n .

Ein Element (a1, a2, . . . , an) ∈ A1 × A2 × · · · × An heißt n-Tupel.

abenannt nach Rene Descartes, 1596 – 1650, franzosischer Philosoph und Mathematiker

Bemerkung: Nach Definition gilt fur beliebige ai , bi ∈ Ai , i = 1, . . . , n:

(a1, a2, . . . , an) = (b1, b2, . . . , bn) genau dann, wenn ai = bi fur i = 1, . . . , n .


Mengen und Abbildungen Satz

2.10 Satz

Fur zwei endliche Mengen M und N gilt

a) #(M ∪ N) + #(M ∩ N) = #M + #N ,

b) #(M × N) = (#M) · (#N).


Mengen und Abbildungen Definition und Satz: Potenzmenge

2.11 Definition und Satz: Potenzmenge

Die Menge aller Teilmengen einer Menge M heißt Potenzmenge von M und wirdmit P(M) bezeichnet:

P(M) := X | X ⊆ M .Wenn M endlich mit n Elementen ist, dann besteht P(M) aus 2n Elementen:

#P(M) = 2#M .


Mengen und Abbildungen Definition: Abbildung

Abbildungen

2.12 Definition: Abbildung

Es seien X und Y zwei Mengen. Eine Abbildung f : X → Y ist eine Vorschrift, diejedem Element x ∈ X eindeutig ein Element y ∈ Y zuordnet.

Man schreibtf : X → Y , x 7→ f (x),

und spricht “f von X nach Y , x wird abgebildet auf f (x)”.

f (x) heißt das Bild von x unter f .X heißt Definitionsbereich.Y heißt Zielbereich, Wertevorrat, oder Zielmenge.

Die Elemente von X heißen auch die Argumente der Abbildung.



2.13 Definition

Zwei Abbildungen f : X → Y und g : X ′ → Y ′ sind genau dann gleich(Schreibweisen f = g oder f ≡ g), wenn

X = X ′ ∧ Y = Y ′ ∧ (∀x ∈ X : f (x) = g(x))

gilt.


Mengen und Abbildungen Definition: Bild, Urbild, Graph

2.15 Definition: Bild, Urbild, Graph

Es sei f : X → Y eine Abbildung.

a) Fur A ⊆ X ist

f (A) := y ∈ Y | es gibt ein a ∈ A mit f (a) = y= f (a) | a ∈ A

das Bild von A unter f . Die Menge f (X ) (also das Bild von ganz X unter f )heißt auch die Bildmenge oder einfach das Bild von f .

b) Fur B ⊆ Y ist

f −1(B) := x ∈ X | f (x) ∈ B

das Urbild von B unter f .

c) Der Graph ist die Menge der geordneten Paare (x , f (x)) ∈ X × Y ,

Graph(f ) := (x , f (x)) | x ∈ X ⊆ X × Y .



2.17 Definition

Eine Abbildung f : X → Y heißtinjektiv :⇐⇒ fur alle x , x ′ ∈ X gilt: x 6= x ′ =⇒ f (x) 6= f (x ′);

(Verschiedene Argumente haben verschiedene Bilder unter f .)

surjektiv :⇐⇒ fur alle y ∈ Y gibt es ein x ∈ X mit f (x) = y ;(Jedes Element in Y kommt als Bild unter f vor.)

bijektiv :⇐⇒ f ist injektiv und surjektiv.



Fur Selbstabbildungen f : M → M einer endlichen Menge M fallen die dreiBegriffe injektiv, surjektiv, bijektiv wieder zusammen. Dies kann man sich mitPfeildiagrammen leicht veranschaulichen.

2.19 Satz

Es sei M eine endliche Menge und f : M → M eine Abbildung. Dann sind diefolgenden Aussagen aquivalent:

a) f ist injektiv.

b) f ist bijektiv.

c) f ist surjektiv.


Mengen und Abbildungen Definition: Komposition

2.20 Definition: Komposition

Es seien f : X → Y und g : Y ′ → Z zwei Abbildungen und es gelte Y ⊆ Y ′; d.h.der Zielbereich von f ist im Definitionsbereich von g enthalten. Die Komposition,Verkettung oder Hintereinanderausfuhrung

g f : X → Z

(lies:”g nach f“) ist definiert durch

(g f )(x) = g(f (x)) fur alle x ∈ X .

Beachte: Die Reihenfolge beim Einsetzen der Argumente (d.h. Einsetzen von x inf und Einsetzen von f (x) in g) geschieht “von rechts nach links”.


Mengen und Abbildungen Bemerkung

2.21 Bemerkung

Die Komposition ist assoziativ: Fur Abbildungen f : X → Y , g : Y ′ → Z undh : Z ′ → W , mit Y ⊆ Y ′ und Z ⊆ Z ′, gilt

h (g f ) = (h g) f : X → W .

Sie ist im Allgemeinen nicht kommutativ.


Mengen und Abbildungen Definition und Proposition: identische Abbildung

2.22 Definition und Proposition: identische Abbildung

a) Es sei X eine Menge. Die identische Abbildung

idX : X → X

ist definiert durch idX (x) = x fur alle x ∈ X .

b) Es seien X und Y Mengen. Fur jede Abbildung f : X → Y gilt dann

f idX = f = idY f .


Mengen und Abbildungen Definition: Umkehrabbildung

2.23 Definition: Umkehrabbildung

Es sei f : X → Y eine Abbildung. Dann heißt eine weitere Abbildung g : Y → Xinverse Abbildung oder Umkehrabbildung, wenn

g f = idX und f g = idY

gilt.

2.24 Satz

Es sei f : X → Y eine Abbildung.

a) Genau dann besitzt f eine inverse Abbildung, wenn f bijektiv ist.

b) Falls f eine inverse Abbildung besitzt, so ist diese eindeutig. Sie ist gegebendurch f −1 : Y → X mit der Zuordnungsvorschrift

f −1(y) = x ⇐⇒ f (x) = y .


Mengen und Abbildungen Satz: Rechenregeln fur die inverse Abbildung

2.25 Satz: Rechenregeln fur die inverse Abbildung

Es seien f : X → Y und g : Y → Z bijektive Abbildungen. Dann ist dieKomposition g f : X → Z ebenfalls bijektiv, und die inverse Abbildung ist

(g f )−1 = f −1 g−1 : Z → X .



2.26 Satz

Es seien f : X → Y und g : Y → Z zwei injektive (surjektive, bijektive)Abbildungen. Dann ist auch die Verkettung g f injektiv (bzw. surjektiv, bijektiv).


Mengen und Abbildungen Definition: gleichmachtige Mengen

Die Machtigkeit von Mengen

2.27 Definition: gleichmachtige Mengen

a) Eine Menge M heißt gleichmachtig zu einer Menge N , falls eine bijektiveAbbildung f : M → N existiert.

b) Eine Menge M heißt abzahlbar, falls sie gleichmachtig zur Menge dernaturlichen Zahlen ist.

Bemerkung:

a) Endliche Mengen M und N sind genau dann gleichmachtig, wenn #M = #Ngilt. Der Beweis ist ganz ahnlich zu Satz 2.19. Was folgt daraus?

Falls #M = n mit n ∈ N gilt, so gibt es eine Aufzahlung der Elemente von M ,

M = x1, . . . , xn.

Dies ist gleichbedeutend mit der bijektiven Abbildung

1, 2, . . . , n → M , i 7→ xi .


Mengen und Abbildungen Definition: gleichmachtige Mengen

Bemerkung (fortges.):

b) Auch die Elemente abzahlbarer Mengen lassen sich “aufzahlen”, allerdingsdurch eine unendliche Folge mit paarweise verschiedenen Folgengliedern,

M = x1, x2, x3, . . ..

Dies entspricht der Bijektion

N → M , i 7→ xi .

c) Verwendet man anstatt der Bijektion f : M → N die inverse Abbildungf −1 : N → M , so erkennt man, dass die Gleichmachtigkeit von Mengen einesymmetrische Eigenschaft ist: M ist gleichmachtig zu N genau dann, wenn Ngleichmachtig zu M ist.


Primfaktorzerlegung und Euklidischer Algorithmus Die naturlichen Zahlen

3 Primfaktorzerlegung und Euklidischer Algorithmus

Bereits die naturlichen und die ganzen Zahlen geben in der Geschichte derMathematik Anlass zu umfangreichen strukturellen Uberlegungen. Man denke nuran die Primfaktorzerlegung (Fundamentalsatz der Arithmetik) oder den erst1993/95 bewiesenen Großen Satz von Fermat1, der ca. 350 Jahre unbewiesenblieb.

Die allgemeine Vertrautheit mit den ganzen Zahlen nutzen wir, um unsere erstenstrukturellen Uberlegungen anzustellen. Diese Uberlegungen sind auch imMathematikunterricht verwertbar, da nur einfache Rechenmethoden aus derUnterstufe benotigt werden. Die hier gewahlte Darstellung ist jedoch fur denEinsatz im Schulunterricht noch nicht geeignet, da sie streng formalisiert ist.

1Pierre de Fermat, 1607/8 – 1665, franzosischer Mathematiker und JuristLineare Algebra, Teil I 11. Oktober 2010 32

Primfaktorzerlegung und Euklidischer Algorithmus Die naturlichen Zahlen

3.A Axiomatische Definition von N0 und Z

Die Peano-Axiome2 sind eine abstrakte Charakterisierung der MengeN0 = 0, 1, 2, 3, . . .. Wir wahlen eine Beschreibung, die der heutigen Sprechweiseangemessen ist.

3.1 Die naturlichen Zahlen

Die Menge N0 ist durch die folgenden Festlegungen eindeutig bestimmt:

1. 0 ∈ N0.

2. Es gibt eine injektive Abbildung s : N0 → N0 \ 0 (die“Nachfolge-Operation”).

3. Fur jede Menge X gilt: Enthalt X die 0 und mit jedem n ∈ N0 auch denNachfolger s(n), so gilt N0 ⊂ X .

2Giuseppe Peano, Turin, 1858 – 1932Lineare Algebra, Teil I 11. Oktober 2010 33

Primfaktorzerlegung und Euklidischer Algorithmus Rechengesetze und Anordnung naturlicher Zahlen

3.2 Rechengesetze und Anordnung naturlicher ZahlenPeano definierte rekursiv die Operationen der

Addition: n + 0 = n, n+ s(m) = s(n +m),

Multiplikation: n · 0 = 0, n · s(m) = n ·m + n

der naturlichen Zahlen (mit 0). Setzt man noch 1 := s(0), so ist dieNachfolge-Operation offensichtlich gegeben durch

s(n) = s(n + 0) = n+ s(0) = n + 1.

Dies fuhrt zu den ublichen Rechenoperationen auf N0: Es gelten die Kommutativ-,Assoziativ- und Distributivgesetze fur Addition und Multiplikation. Auch dieubliche Anordnung

0 < 1 < 2 < 3 < · · ·wird axiomatisch definiert durch

a < b :⇐⇒ ∃x ∈ N : a + x = b.


Primfaktorzerlegung und Euklidischer Algorithmus Axiomatische Beschreibung von Z

Eine axiomatische Einfuhrung der ganzen Zahlen ist nun ein kleiner Schritt.

3.3 Axiomatische Beschreibung von Z

1. Die Menge der ganzen Zahlen Z enthalt die naturlichen Zahlen N0 alsTeilmenge.

2. Zu jedem Paar (a, b) ∈ Z× Z ist eine Zahl a+ b ∈ Z definiert derart, dassgilt:

a) Fur alle a, b, c ∈ Z ist (a+ b) + c = a + (b + c). (Assoziativgesetz)b) Fur alle a, b ∈ Z ist a + b = b + a. (Kommutativgesetz)c) Das Element 0 ∈ Z erfullt 0 + a = a fur alle a ∈ Z (neutrales Element).d) Zu jedem Element a ∈ Z gibt es ein Element −a ∈ Z (das Negative zu a),

so dass a+ (−a) = 0 ist.

Fur a, b ∈ N hat + dabei die fruhere Bedeutung.

3. Zu jedem Paar (a, b) ∈ Z×Z ist eine Zahl a ·b ∈ Z definiert derart, dass gilt:

a) Fur alle a, b, c ∈ Z ist (a · b) · c = a · (b · c). (Assoziativgesetz)b) a · b = b · a (Kommutativgesetz)c) Fur alle a, b, c ∈ Z gilt a · (b + c) = a · b + a · c. (Distributivgesetz)

Fur a, b ∈ N hat a · b dabei die fruhere Bedeutung.


Primfaktorzerlegung und Euklidischer Algorithmus Axiomatische Beschreibung von Z

4. Wenn man fur zwei Elemente a, b ∈ Z die “Relation”

a < b :⇐⇒ ∃x ∈ N : a + x = b,

definiert, dann gilt fur zwei beliebige Elemente a, b ∈ Z genau eine derfolgenden drei Alternativen:

a < b oder a = b oder b < a.

d.h. die Relation “<” definiert eine totale Ordnung auf Z.


Primfaktorzerlegung und Euklidischer Algorithmus Definition und Satz: Division mit Rest

Als weitere Grundoperation in Z fuhren wir ein:

3.4 Definition und Satz: Division mit Rest

a) Es seien a, b ∈ Z. a heißt teilbar durch b, wenn eine Zahl q ∈ Z existiert mita = qb.

Schreibweisen: b | a b teilt ab ∤ a b teilt a nicht

b) Es sei b ∈ N. Dann gibt es zu jedem a ∈ Z eindeutig bestimmte Zahlenq ∈ Z und r ∈ 0, 1, . . . , b − 1 so, dass

a = qb + r

gilt. q heißt der Quotient und r heißt der Rest von a bei Division durch b.

Schreibweisen: r = a mod b oder r = a% b.


Primfaktorzerlegung und Euklidischer Algorithmus Definition: Primzahl

3.B Die eindeutige Primzahlzerlegung naturlicher Zahlen

Der folgende Begriff ist sicher bekannt.

3.5 Definition: Primzahl

Eine naturliche Zahl p mit p > 1 heißt Primzahl, falls sie nicht als Produkt zweierkleinerer Zahlen dargestellt werden kann. Mit anderen Worten:

p = ab mit a, b ∈ N =⇒ a = 1 oder b = 1


Primfaktorzerlegung und Euklidischer Algorithmus Fundamentalsatz der Arithmetik: Eindeutige Primfaktorzerlegung

Der folgende (bekannte) Satz ist nicht so harmlos, wie er auf den ersten Blickaussehen mag.

3.6 Fundamentalsatz der Arithmetik: Eindeutige Primfaktorzerlegung

a) Jede naturliche Zahl n > 1 lasst sich als ein Produkt

n = p1 · p2 · . . . · pr

mit Prinzahlen p1, p2, . . . , pr ∈ N schreiben.

b) Diese Zerlegung ist eindeutig bis auf die Reihenfolge der Faktoren. D.h.,wenn auch

n = q1 · q2 · . . . · qsmit Primzahlen qj , j = 1, . . . , s, gilt, so ist r = s, und wenn wir ferner

p1 ≤ p2 ≤ . . . ≤ pr und q1 ≤ q2 ≤ . . . ≤ qr

annehmen, so ist pi = qi fur i = 1, . . . , r .


Primfaktorzerlegung und Euklidischer Algorithmus Lemma

Die Eindeutigkeit der Zerlegung in Primfaktoren wird bewiesen mit Hilfe einerzweiten charakteristischen Eigenschaft der Primzahlen.

3.7 Lemma

Wenn eine Primzahl ein Produkt teilt, so teilt sie wenigstens einen der Faktoren:

(p Primzahl ∧ a, b ∈ N ∧ p | ab) =⇒ (p | a ∨ p | b) .

Wenn allgemeiner eine Primzahl p ein Produkt a1a2 . . . as teilt, dann teilt sie einender Faktoren.

Bemerkung: Man mache sich klar, dass die Aussage nicht einfach aus der Definition einerPrimzahl folgt, sondern dass hier eine andere Eigenschaft von Primzahlen beschrieben wird. Inallgemeineren algebraischen Strukturen als Z (sog. Ringen) werden Elemente, die die Eigenschaftim obigen Hilfssatz besitzen, “Primelemente” genannt. Hingegen werden Elemente, die dieEigenschaft in Definition 3.5 besitzen, als “unzerlegbar” (oder “irreduzibel”) bezeichnet. Inallgemeinen Ringen sind diese Begriffe nicht deckungsgleich!


Primfaktorzerlegung und Euklidischer Algorithmus Satz: Großter gemeinsamer Teiler

Den Beweis von Lemma 3.7 verschieben wir ans Ende dieses Abschnitts. Wirbenotigen zuerst den (ebenfalls bekannten) Begriff des großten gemeinsamenTeilers ggT:

3.8 Satz: Großter gemeinsamer Teiler

Gegeben seien zwei ganze Zahlen a, b ∈ Z, wovon wenigstens eine von Nullverschieden ist. Dann gibt es eine ganze Zahl g mit folgenden Eigenschaften:

(1) g | a und g | b;(2) fur d ∈ Z gilt: (d | a ∧ d | b) ⇒ d | g .In Worten: g ist ein Teiler von a und von b, und jede ganze Zahl, die gleichzeitig aund b teilt, ist ein Teiler von g .

3.9 Bemerkung:

a) Die Eigenschaften (1) und (2) gelten gleichzeitig fur g und −g . Wahlen wir g > 0, so istdie Bezeichnung

g = ggT(a, b) großter gemeinsamer Teiler

gerechtfertigt, weil g die großte naturliche Zahl ist, die sowohl a als auch b teilt.

b) Fur a = 0 und b = 0 ist der ggT nicht definiert.


Primfaktorzerlegung und Euklidischer Algorithmus Euklidischer Algorithmus

Der Beweis des Satzes vom ggT wird sich aus folgendem Verfahren ergeben.

3.10 Euklidischer Algorithmus

1 Eingabe: a ∈ Z, b ∈ N.2 Teile a durch b mit Rest r .

3 Ersetze a durch b, ersetze b durch r .

4 Wiederhole Schritt 2 und Schritt 3 mit den neuen Zahlen so lange,bis der Rest 0 wird. Dieses geschieht in endlich vielen Schritten, da b (bzw.r) im Laufe des Verfahrens immer kleiner wird.

5 Ausgabe: der letzte von Null verschiedene Rest


Primfaktorzerlegung und Euklidischer Algorithmus Satz: Lemma von Bezout

3.12 Satz: Lemma von Bezout

Der großte gemeinsame Teiler g zweier ganzer Zahlen a und b besitzt eineDarstellung

g = xa+ yb mit x , y ∈ Z .

3.13 Der erweiterte euklidische Algorithmus

Gegeben seien ganze Zahlen a ∈ Z, b ∈ N. Definiere rekursiv die Zahlenak , bk , rk , qk wie im Euklidischen Algorithmus und zusatzlich xk , yk ∈ Z durch

a0 := a; b0 := b; x−2 := 1; y−2 = 0; x−1 := 0; y−1 = 1;

Fur k = 0, 1, 2, . . ., solange bk 6= 0:

rk := ak mod bk ; qk := (ak − rk)/bk ;xk := xk−2 − qkxk−1; yk := yk−2 − qkyk−1;ak+1 := bk ; bk+1 := rk .

Sei ℓ der kleinste Index mit rℓ = 0. Dann gilt g := ggT(a, b) = rℓ−1 sowie

g = xℓ−1a+ yℓ−1b.


Documents

Lineare Algebra, Teil I - mathematik.tu-dortmund.de · Lineare Algebra, Teil I 11. Oktober 2010 0. Kapitel I. Grundbegriﬀe Inhalt: 1. Logik 2. Mengen und Abbildungen 3. Primfaktorzerlegung