Skript EZT PDF

Preview

Summary

Skript zur elementaren Zahlentheorie...

Description

Prof. Dr. Lydia Außenhofer

WS 2016/17

Elementare Zahlentheorie 1

Einleitung

Im Zentrum der Elementaren Zahlentheorie stehen Fragestellungen, die die nat¨ urlichen Zahlen betreffen. Einige Grundlagen sollen in dieser Vorlesung erarbeitet werden. Zun¨achst wird eine Einf¨uhrung in den Aufbau des Zahlensystems gegeben: Durch die Peano Axiomen werden die nat¨urlichen Zahlen definiert. Darauf aufbauend werden die ganzen und rationalen Zahlen hergeleitet. Auf jeder dieser Mengen ist sowohl eine Addition als auch eine Multiplikation definiert. Eigenschaften dieser Abbildungen wie Kommutativit¨at und Assoziativit¨at werden nachgewiesen. Sodann wenden wir uns der Teilbarkeitstheorie zu. Es wird der Euklidische Algorithmus besprochen, der eine konstruktives Verfahren zur Berechnung des gr¨oßten gemeinsamen Teilers zweier ganzer Zahlen erlaubt. Von großer Bedeuurliche Zahl ≥ 2 als tung sind auch Primzahlen und die Tatsache, dass jede nat¨ Produkt von Primzahlen dargestellt werden kann. Der n¨ achste große Abschnitt besch¨aftigt sich mit der g–adischen Darstellung rationaler Zahlen, insbesondere der Klassifikation rein- und gemischt periodischer Dezimalbr¨uche. Im n¨achsten Abschnitt besch¨aftigen wir uns mit der Modulorechnung. Ein wichtiges Ergebnis wird der Chinesische Restsatz sein, der es erlaubt, simultane Kongruenzen zu l¨ osen. Der Satz von Wilson gibt eine Charakterisierung an, wann eine Zahl eine Primzahl ist und der Satz von Euler erm¨oglicht es, Potenzen einer Zahl modulo einer anderen Zahl zu berechnen. So kann man mit seiner 9 Hilfe sehr leicht die letzten drei Ziffern der Dezimaldarstellung der Zahl 99 berechnen, was mit einem gew¨ ohnlichen Taschenrechner nicht m¨oglich ist. Schließlich wollen wir uns quadratischen Resten zuwenden, also der Frage, wie man leicht erkennen kann, ob eine Zahl modulo einer anderen Zahl ein Quadrat ist oder nicht. Im Fall, dass noch Zeit bleibt, werden Kettenbr¨uche behandelt. Zur Motivation und zur Hinf¨uhrung auf das Thema sollen hier einige (mehr oder weniger) ber¨ uhmte offene Probleme der elementaren Zahlentheorie vorgestellt werden:

1

Vermutung 1.1 (Goldbach) Jede gerade Zahl ≥ 4 ist die Summe zweier Primzahlen. Bereits 1937 zeige Winogradow urliche Zahl N ∈ N, so dass Satz 1.2 (Winogradow) Es existiert eine nat¨ urliche Zahl ≥ N Summe von drei Primzahlen ist. jede ungerade nat¨ Ber¨uhmt ist auch die offene Frage 1.3 Gibt es unendlich viele Primzahlzwillinge? Frage 1.4 (Palindrome) Ein Palindrom ist eine nat¨urliche Zahl, deren Dezimaldarstellung spiegelsymmetrisch ist, z.B. 131 oder 1441 oder 42 788 724. Durch Probieren stellt man fest, dass das folgende Vorgehen h¨aufig zu Palindromen f¨ uhrt: Man addiert zu einer nat¨urlichen Zahl n, die kein Palindrom ist, ihre Spiegelzahl. Ist dies kein Palindrom, so f¨ahrt man fort. Beispiel: 789 −→ 1776 −→ 8547 −→ 16005 −→ 66066 Es ist nicht bekannt, ob dies bei allen Zahlen funktioniert. Bei den sogenannten Lychrel–Zahlen ist nicht bekannt, ob dieser Algorithmus stets zu einem Palindrom f¨uhrt. 196 ist die kleinste Lychrel–Zahl. Vermutung 1.5 Collatz Wir betrachten die folgenden Funktion ( n/2 : n gerade ϕ : N → N, n 7→ . 3n + 1 : n ungerade Die Collatzsche Vermutung besagt, dass man nach endlich vielen Anwendungen von ϕ den Wert 1 erh¨ alt. Zum Beispiel: 7 −→ 22 −→ 11 −→ 34 −→ 17 −→ 52 −→ 26 −→ 13 −→ 40 −→ 20 −→ 10 −→ 5 −→ 16 −→ 8 −→ 4 −→ 2 −→ 1.

2

2

Der Aufbau des Zahlensystems

2.1

¨ Aquivalenzrelationen

¨ quivalenzrelation eingef¨uhrt und an In diesem Abschnitt soll der Begriff der A Hand einiger Beispiele verdeutlicht werden. Hintergrund ist, dass dieser Begriff f¨ ur den Aufbau des Zahlensystem sowie in der Modulorechnung von zentraler Bedeutung ist. Definition 2.1 Es sei M 6= ∅ eine Menge. Eine Teilmenge R ⊆ M × M = {(m1 , m2 ) : m1 , m2 ∈ M } heißt Relation. Eine Relation R heißt reflexiv, falls (m, m) ∈ R f¨ ur alle m ∈ M . symmetrisch, falls aus (m, k) ∈ R folgt, dass auch (k, m) ∈ R gilt. transitiv, falls aus (m, k) ∈ R und (k, n) ∈ R folgt, dass auch (m, n) ∈ R gilt. ¨ Eine Relation R, welche reflexiv, symmetrisch und transitiv ist, wird Aquivalenzrelation genannt. Meist schreibt man statt (m, n) ∈ R kurz m ∼ n. Beispiele 2.2 1. Es sei M = R und R = {(x, x) : x ∈ R}. Wir h¨atten auch schreiben k¨onnen x ∼ y :⇐⇒ x = y ¨ denn: R ist eine Aquivalenzrelation, Reflexivit¨ at: F¨ur alle x ∈ R gilt (x, x) ∈ R (x ∼ x). Symmetrie: Es sei (x, y) ∈ R. D.h. x = y. Dann gilt auch (y, x) = (x, x) = (x, y) ∈ R. at: Es seien (x, y) ∈ R und (y, z) ∈ R. D.h. x = y und y = z . Transitivit¨ Es folgt (x, z) = (x, x) ∈ R. 2. Es sei M eine endliche Menge. Es bezeichne P(M ) die Potenzmenge von M , also die Menge aller Teilmengen von M . F¨ur A ⊆ M bezeichne |A| die Anzahl der Elemente von A. Dann ist R := {(A, B) ∈ P(M ) × P(M ) : ¨ |A| = |B|} (A ∼ B :⇐⇒ |A| = |B |) eine Aquivalenzrelation auf P(M ), denn: ur alle A ∈ P(M ) gilt (A, A) ∈ R, da |A| = |A|. Reflexivit¨ at: f¨ Symmetrie: Es sei (A, B) ∈ R. D.h. |A| = |B|. Dann gilt auch (B, A) ∈ R, da ja |B| = |A|. at: Es seien (A, B) ∈ R und (B, C) ∈ R. D.h. |A| = |B| = |C|. Transitivit¨ Es folgt (A, C) ∈ R, da |A| = (|B =)|C|. 3

¨ quiva3. Es sei R = {(m, n) ∈ Z × Z : m + n ist gerade}. Dann ist R eine A lenzrelation, denn ur alle m ∈ Z ist (m, m) ∈ R, da m + m = 2m gerade ist. Reflexivit¨ at: f¨ Symmetrie: Es sei (m, n) ∈ R. D.h. m + n ist gerade. Dann gilt auch (n, m) ∈ R, da n + m = m + n gerade ist. at: Es seien (m, k) ∈ R und (k, n) ∈ R. D.h. m + k und k + n Transitivit¨ sind gerade. Dann ist auch m + k + k + n = m + n + 2k gerade und damit ist auch m + n gerade. Es folgt (m, n) ∈ R. ¨ Definition 2.3 Es sei M 6= ∅ eine Menge und R (bzw. ∼) eine Aquivalenzreur x ∈ M definieren wir lation auf M . F¨ [x] := [x]R := [x]∼ := {y ∈ M : (x, y) ∈ R}, ¨ die Aquivalenzklasse von x. (Auf den Index R bzw. ∼ verzichten wir, wenn aus ¨ es sich handelt.) dem Kontext klar hervorgeht, um welche Aquivalenzrelation ¨ Die Menge aller Aquivalenzklassen bezeichnen wir mit M/ ∼, also M/ ∼= {[x] : x ∈ M }. Beispiele 2.4 1. Es sei M = R und R = {(x, x) : x ∈ R}. Dann ist f¨ur jedes x ∈ R [x] = {y ∈ R : x ∼ y} = {x}. 2. Es sei M eine endliche Menge. Wie gesehen, ist R := {(A, B) ∈ P(M ) × P(M ) : |A| = |B|} ¨ eine Aquivalenzrelation auf P(M ). Sei A ⊆ M (d.h. A ∈ P(M )). Dann ist [A] = {B ⊆ M : |A| = |B|}. Sehen wir uns konkret die Menge M = {1, 2, 3} an. Dann ist P({1, 2, 3}) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

4

¨ erhalten wir: Als Aquivalenzklassen [∅]

=

{∅}

[{1}]

=

{{1}, {2}, {3}}

[{2}]

=

{{1}, {2}, {3}}

[{3}]

=

{{1}, {2}, {3}}

[{1, 2}]

=

{{1, 2}, {1, 3}, {2, 3}}

[{1, 3}]

=

{{1, 2}, {1, 3}, {2, 3}}

[{2, 3}]

=

{{1, 2}, {1, 3}, {2, 3}}

[{1, 2, 3}]

=

{{1, 2, 3}}

3. Es sei R = {(m, n) ∈ Z × Z : m + n ist gerade}. Wie gesehen, handelt ¨ ¨ es sich bei R um eine Aquivalenzrelation. Als Aquivalenzklassen erhalten wir:

[0] = {n ∈ Z : (0, n) ∈ R} = {n ∈ Z : 0+n ist gerade} = 2Z = {2k : k ∈ Z}. [1] = {n ∈ Z : (1, n) ∈ R} = {n ∈ Z : 1+n ist gerade} = 1+2Z = {1+2k : k ∈ Z}. Allgemeiner gilt f¨ur jede gerade Zahl g ∈ Z: [g] = 2Z und f¨ ur jede ungerade Zahl u ∈ Z gilt [u] = 1 + 2Z. ¨ auf der Menge M . Dann Proposition 2.5 Es sei R eine Aquivalenzrelation gelten: ur jedes x ∈ M ist [x] = 6 ∅. 1. F¨ ¨ 2. F¨ ur x, y ∈ M gilt entweder [x] = [y] oder [x] ∩ [y] = ∅. (Zwei Aquivalenz¨ klassen sind gleich oder disjunkt.) Genau dann sind die Aquivalenzklassen [x] und [y] gleich, wenn x ∼ y gilt. [ [x] = M . 3. x∈M

Beweis (1) Da R reflexiv ist, gilt x ∈ [x]. (2) Wir zeigen zun¨achst, dass x ∼ y [x] = [y] impliziert. ⊆“ Sei also u ∈ [x]. Es gilt also x ∼ u und (nach Voraussetzung) x ∼ y. Wegen ” der Symmetrie gilt u ∼ x und x ∼ y, was mit der Transitivit¨at u ∼ y zur Folge hat. Wieder wegen der Symmetrie gilt y ∼ u, also u ∈ [y]. ⊇“ Zeigt man analog. ” 5

Es seien x, y ∈ M , so dass [x] ∩ [y] 6= ∅. Dann existiert z ∈ [x] ∩ [y]. Wir m¨ussen zeigen, dass [x] = [y] gilt. Wir wissen also x ∼ z, y ∼ z. Auf Grund der Symmetrie folgt x ∼ z und z ∼ y, was wegen der Transitivit¨at x ∼ y impliziert. Mit dem oben Gezeigten folgt [x] = [y]. Es ist nur noch zu zeigen, dass [x] = [y] x ∼ y impliziert. Dies ist aber klar, da nach (1) y ∈ [y] = [x] gilt. offensichtlich. (3) Da f¨ur jedes x ∈ M [x] ⊆ M gilt, ist ⊆’ [ [ Umgekehrt gilt ” [x] ⊇ ur jedes x ∈ M und damit {x} = M . wegen (1) {x} ⊆ [x] f¨ x∈M

x∈M

¨ auf der Menge M 6= ∅. Ist Bezeichnung 2.6 Es sei ∼ eine Aquivalenzrelation ¨ u ∈ [x] (f¨ur ein x ∈ M ), so wird u Repr¨ [x] asentant der Aquivalenzklasse genannt. In dem Fall gilt [u] = [x].

2.2

Die axiomatische Beschreibung der nat¨ urlichen Zahlen und das Beweisprinzip der vollst¨ andigen Induktion

Die nat¨ urlichen Zahlen N0 werden mit Hilfe der sogenannten Peano Axiome beschrieben:

Peano Axiome Die nat¨urlichen Zahlen N0 sind eine Menge. Axiom 1 Es existiert eine Abbildung S : N0 → N0 , n 7→ n+ , welche injektiv ist. n+ wird Nachfolger von n genannt. Axiom 2 0 ∈ / S(N0 ); d.h. 0 6= S(n) f¨ur alle n ∈ N0 . 0 ist also kein Nachfolger. Axiom 3 (Induktionsaxiom) Ist M ⊆ N0 mit den folgenden Eigenschaften: • 0 ∈ M, • S(M ) = {S(m) : m ∈ M } ⊆ M (d.h. m ∈ M =⇒ m+ ∈ M ) Dann gilt M = N0 .

Das Beweisprinzip der vollst¨ andigen Induktion Um zu zeigen, ur alle n ∈ N0 gilt, gen¨ dass eine Aussage A(n) f¨ ugt es zu zeigen, dass die Menge M := {n ∈ N0 : A(n) ist wahr} mit N0 u¨bereinstimmt. Wegen Axiom 3 gen¨ugt es zu zeigen, dass 0 ∈ M gilt (also A(0) eine wahre Aussage ist) und, wenn A(n) wahr ist, auch A(n+ ) wahr ist. Den Nachweis, dass A(0) wahr ist, nennt man Induktionsanfang (kurz IA). Den Nachweis, dass, wenn A(n) wahr ist, auch 6

A(n+ ) wahr ist, nennt man Induktionsschritt (kurz IS). Im Induktionsschritt verwendet man, dass A(n) wahr ist. Dies werden wir als Induktionsvoraussetzung (kurz IV) bezeichnen. Proposition 2.7 Zu jedem n ∈ N0 \ {0} =: N gibt es genau ein m ∈ N0 mit m+ = n. Beweis Existenz: Wir betrachten die Menge M = {0} ∪ {m+ : m ∈ N0 }. Wir zeigen mit Hilfe von vollst¨andiger Induktion, dass M = N0 gilt. IA: 0 ∈ M (nach Definition der Menge M ). IS: Es gelte n ∈ M . Wir m¨ussen zeigen, dass daraus n+ ∈ M folgt. Da n ∈ M , gilt n ∈ N0 , also ist n+ ∈ M . Mit dem Induktionsaxiom folgt, dass M = N0 gilt. Nach Axiom 2 gilt 0 ∈ / {n+ : n ∈ N0 }. Daher ist M die disjunkte Vereinigung der Mengen {0} und der Nachfolgermenge {n+ : n ∈ N0 }. Wir erhalten: N = N0 \ {0} = M \ {0} = {n+ : n ∈ N0 }. D.h. zu jedem m ∈ N existiert ein n ∈ N0 , so dass m = n+ . Eindeutigkeit: Sei n ∈ N und seien m1 , m2 ∈ N0 mit n = m+1 = m2+. Mit Axiom 1 (Injektivit¨at der Abbildung S) folgt m1 = m2 .

2.3

Die Addition nat¨ urlicher Zahlen

Satz 2.8 Addition auf N0 Es gibt genau eine Abbildung + : N0 × N0 −→ N0 , die (A 1) n + 0 := n und (A 2) n + m+ := (n + m)+ f¨ ullt. Sie wird Addition der nat¨urlichen Zahlen genannt. ur alle n, m ∈ N0 erf¨ Bevor wir den Satz beweisen, wollen wir uns die Vorschrift genauer ansehen. (A1) (A2) (A1) Es ist also n + 0 = n und n + 0+ = (n + 0)+ = n+ . Wir werden sp¨ater 0+ als 1 definieren. achst die Idee: Sei n ∈ N0 . Wir wollen zeigen, dass n + m f¨ Beweis Zun¨ ur alle m ∈ N0 eindeutig definiert ist. Wenn m = 0, so ist n + m nach (A 1) definiert. Ist m ∈ N, so existiert nach 2.7 ein eindeutiges k ∈ N0 mit k + = m. Es ist dann also n + m = n + k + = (n + k)+ . 7

Nun der formale Beweis: Es sei n ∈ N0 fest. Wir sollen zeigen, dass n + m ur alle m ∈ N0 eindeutig definiert ist und betrachten dazu die Menge f¨ M = {m ∈ N0 : n + m ist eindeutig definiert}. Mit vollst¨andiger Induktion wollen wir zeigen, dass M = N0 gilt. IA: 0 ∈ M , da n + 0 = n nach (A 1). IS: Es sei m ∈ M , d.h. n + m ist eindeutig definiert. Es ist zu zeigen, dass auch m+ ∈ M gilt. Nach (A 2) ist aber n + m+ = (n + m)+ . Da der Nachfolger nach Peano–Axiom 1 eindeutig ist, folgt m+ ∈ M . Es folgt M = N0 . Somit ist also n + m f¨ur alle n, m ∈ N0 definiert. Proposition 2.9 Assoziativit¨ at der Addition auf N0 Die Addition + : N0 × N0 → N0 ist assoziativ, d.h. f¨ur alle n, m, k ∈ N0 gilt (n + m) + k = n + (m + k). Beweis Seien n, m ∈ N0 fest. Es sei M = {k ∈ N0 : (n + m) + k = n + (m + k)}. Mit vollst¨andiger Induktion wollen wir zeigen, dass M = N0 gilt. (A1)

(A1)

IA: 0 ∈ M , da (n + m) + 0 = n + m = n + (m + 0). IS: Es sei k ∈ M . Wir wollen zeigen, dass auch k + ∈ M . (A2)

(A2)

(A2)

= (n + (m + k))+ = n + (m + k)+ = (n + m) + k + = ((n + m) + k)+ IV + + n + (m + k ). Somit folgt k ∈ M . Es ist also M = N0 und die Proposition damit bewiesen.

Lemma 2.10 F¨ur alle n ∈ N0 gilt 0+n = n+0 = n und 0+ +n = n+ = n +0+ . ¨ Beweis Ubungsaufgabe Proposition 2.11 Kommutativit¨ at der Addition auf N0 Die Addition in N0 ist kommutativ, d.h. f¨ur alle n, m ∈ N0 gilt n + m = m + n. Beweis Es sei n ∈ N0 . Wir wollen zeigen, dass f¨ur dieses feste n mit allen m ∈ N0 kommutiert und betrachten dazu die Menge M = {m ∈ N0 : n + m = m + n}. Mit vollst¨andiger Induktion wollen wir zeigen, dass M = N0 gilt. 8

(A1)

2.10

IA: Es ist n = n + 0 = 0 + n. IS: Es sei m ∈ M . Es gilt also n + m = m + n. Wir wollen zeigen, dass auch n + m+ = m+ + n gilt. (A2)

2.10

(A2)

IV

Ass

n + m+ = (n + m)+ = (m + n)+ = m + n+ = m +(0+ + n) = (m + 0+ ) + (A2)

(A1)

n = (m + 0)+ + n = m+ + n. Somit ist m+ ∈ M und mit damit ist M = N0 . Proposition 2.12 K¨ urzungsregel der Addition Seien m, n, k ∈ N0 . Aus m + k = n + k folgt m = n. Beweis Seien m, n ∈ N0 gegeben. Wir betrachten die Menge M = {k ∈ N0 : m + k = n + k =⇒ m = n}. IA 0 ∈ M , da m = m + 0 = n + 0 = n m = n impliziert. IS Es sei k ∈ M . Wir wollen zeigen, dass auch k + Element von M ist. Es gelte also m + k + = n + k + . Wir wollen zeigen, dass m = n gilt. Mit (A 2) folgt (m + k)+ = m + k + = n + k + = (n + k)+ und wegen Peano–Axiom 1 (Injektivit¨at von S) ist m + k = n + k . Nun folgt, da k ∈ M ist, m = n, was zu zeigen war. Korollar 2.13 Seien m ∈ N0 und k ∈ N. Dann gilt m + k 6= m. Beweis Angenommen, es existiert k ∈ N mit m + k = m. Da k ∈ N, ist 0 6= k . Wir haben also m + k = m + 0 (wegen (A 2)). Mit der Kommutativit¨at der Addition erhalten wir k + m = 0 + m und nun liefert Proposition 2.12 den gew¨ unschten Widerspruch k = 0.

2.4

Die Multiplikation nat¨ urlicher Zahlen

Satz 2.14 Multiplikation auf N0 Es gibt genau eine Abbildung · : N0 × N0 −→ N0 , die (M 1) n · 0 := 0 und (M 2) n · m+ := n · m + n ur alle n, m ∈ N0 erf¨ f¨ ullt. Sie wird Multiplikation der nat¨urlichen Zahlen genannt. 9

(M2)

(M2)

(M1)

Es gilt n·0+ = n·0+n = 0+n = n und n·(0+ )+ = n·0+ + n = n + n. Beweis Wir wollen zeigen, dass n · m f¨ ur alle m ∈ N0 eindeutig definiert ist. Wenn m = 0, so ist n · m nach (M 1) als 0 definiert. Ist m ∈ N, so existiert nach 2.7 ein eindeutiges k ∈ N0 mit k + = m. Es ist dann also n·m = n·k + = n·k +n. Ist aber n · k definiert? Sei n ∈ N0 fest. Es sei M = {m ∈ N0 : n · m ist eindeutig definiert}. Mit vollst¨andiger Induktion wollen wir zeigen, dass M = N0 gilt. IA: 0 ∈ M , da n · 0 = 0 nach (M 1). IS: Es sei m ∈ M , d.h. n · m ist eindeutig definiert. Es ist zu zeigen, dass auch m+ ∈ M gilt. Nach (M 2) ist aber n · m+ = n · m + n. Da n · m nach IV eindeutig definiert ist, folgt m+ ∈ M . Es folgt M = N0 . Somit ist n · m f¨ur alle n, m ∈ N0 definiert. Proposition 2.15 Distributivgesetz auf N0 F¨ ur alle n, m, k ∈ N0 gilt (n + m) · k = n · k + m · k. Beweis Seien n, m ∈ N0 fest. Wir betrachten wir die Menge M = {k ∈ N0 : (n + m) · k = n · k + m · k}. Mit vollst¨andiger Induktion wollen wir zeigen, dass M = N0 gilt. IA: k = 0; (n + m) · 0 = 0 = 0 + 0 = (n · 0) + (m · 0). IS: Es gelte k ∈ M , also (n + m) · k = n · k + m · k (IV). Wir wollen zeigen, dass auch k + ∈ M . (M2) IV Ass,Komm (n + m) · k + = [(n + m) · k] + (n + m) = [(n · k) + (m · k)] + (n + m) = [(n · k) + n] + [(m · k) + m] = (n · k + ) + (m · k + ). Lemma 2.16 F¨ur alle m ∈ N0 gelten 0 · m = 0 und 0+ · m = m. Beweis Zur ersten Aussage: IA F¨ur m = 0 gilt 0 · 0 = 0. IV

(A1)

IS Es gelte 0 · m = 0. Dann ist 0 · m+ = 0 · m + 0 = 0 + 0 = 0. Somit gilt f¨ur alle m ∈ N0 0 · m = 0. Nun zur zweiten Aussage: IA F¨ur m = 0 gilt 0+ · 0 = 0.

10

IV

M2

(A2)

IS Es gelte 0+ · m = m. Dann ist 0+ · m+ = 0+ · m + 0+ = m + 0+ = (A1) (m + 0)+ = m+ . ur alle m ∈ N0 0+ · m = m. Somit gilt f¨ Proposition 2.17 Kommutativit¨ at der Multiplikation auf N0 Die Multiplikation in N0 ist kommutativ, d.h. f¨ur alle n, m ∈ N0 gilt n · m = m · n. Beweis Es sei n ∈ N0 fest und M = {m ∈ N0 : n · m = m · n}.

Mit vollst¨andiger Induktion wollen wir zeigen, dass dass die Menge M aller nat¨ urlichen Zahlen, die mit n kommutieren, mit N0 ¨ubereinstimmt. (M1)

2.16

IA: Es gilt 0 ∈ M , n · 0 = 0 = 0 · n. IS: Es sei m ∈ M . Es gilt also n · m = m · n. Wir wollen zeigen, dass auch n · m+ = m+ · n gilt. (M2)

Dis 2.16 n · m+ = n · m + n IV = m · n + n = m · n + 0+ · n = (m + 0+ ) · n = m+ · n.

Proposition 2.18 Assoziativit¨ at der Multiplikation auf N0 Die Multiplikation · : N0 × N0 → N0 ist assoziativ, d.h. f¨ur alle n, m, k ∈ N0 gilt (n · m) · k = n · (m · k ). Beweis Seien n, m ∈ N0 . Es sei M = {k ∈ N0 : (n · m) · k = n · (m · k)}. Mit vollst¨andiger Induktion wollen wir zeigen, dass M = N0 gilt. (M1) (M1) (M1) IA: 0 ∈ M , da (n · m) · 0 = 0 = n · 0 = n · (m · 0). (M2)

IS: Es sei k ∈ M . Wir wollen zeigen, dass auch k + ∈ M . (n · m) · k + = IV 2.17 2.15 (n·m)·k +(n·m) = n·(m·k)+(n·m) = (m·k)·n+m·n = ((m·k)+ m)·n = 2.17 (m · k + ) · n = n · (m · k + ) Somit folgt k + ∈ M . Proposition 2.19 Seien n, m ∈ N. Dann ist auch n · m ∈ N. Mit Kontraposition erhalten wir: Sind n, m ∈ N0 und gilt n · m = 0, so folgt n = 0 oder m = 0. Beweis Seien n, m ∈ N. Dann existierten u, v ∈ N0 , so dass n = u+ und m = v+ . (A1)

Wir erhalten also n · m = n · v+ = n · v + n = n · v + u+ = (n · v + u)+ . Somit ist wegen Peano Axiom 2 n · m 6= 0, also n · m ∈ N. 11

Proposition 2.20 K¨ urzungsregel der Multiplikation Seien k ∈ N und n, m ∈ N0 . Gilt n · k = m · k, so folgt n = m. Beweis Wir zeigen mit vollst¨ andiger Induktion, dass

M = {m ∈ N0 : ∀n ∈ N0 , ∀k ∈ N gilt n · k = m · k =⇒ n = m} mit N0 ¨ubereinstimmt. IA: m = 0 ∈ M , da n · k = 0 · k = 0 impliziert n = 0 oder k = 0 (2.19). Da nach Voraussetzung k ∈ N, folgt n = 0 = m. IS: Es sei m ∈ M . Aus n · k = m · k folgt also n = m. Um zu zeigen, dass auch m+ ∈ M gilt, nehmen wir an, dass n·k = m+ ·k gilt. Wenn n = 0, so ist n·k = 0. Andererseits sind m+ , k ∈ N und wegen 2.19 ist auch m+ ·k ∈ N im Widerspruch zu n·k = m+ ·k. Daher k¨ onnen wir n ∈ N bzw. n = u+ f¨ur ein geeignetes u ∈ N0 annehmen. Wir haben also k · u+ k = k · u+ = n · k = m+ · k = k · m+ = k · m + k . Mit 2.12 folgt k · u = k · m und da m ∈ N, folgt u = m bzw, n = u+ = m+ , was zu zeigen war.

2.5

Ordnung auf N0

Definition 2.21 Es sei M 6= ∅ eine Menge. Eine Relation ∅ = 6 R ⊆ M ×M heißt antisymmetrisch, wenn aus (x, y) ∈ R und (y, x) ∈ R folgt, dass x = y. Eine Relation R auf M , die • reflexiv, • antisymmetrisch und • transitiv ist, heißt Ordnung. Meist schreibt man statt (x, y) ∈ R x ≤ y oder x ≥ y. Man nennt dann (M, ≤) eine geordnete Menge. Gilt zus¨atzlich, dass f¨ur alle x, y ∈ M (x, y) ∈ R oder (y, x) ∈ R, so spricht man von einer Totalordnung. Beispiel 2.22 Es sei M 6= ∅ eine Menge. Dann wir durch R = {(A, B) ∈ P(M ) × P(M ) : A ⊆ B} eine Ordnung definiert. 12

ur alle A ⊆ M gilt A ⊆ A. Reflexivit¨ at: F¨ Antisymmetrie: Es gelte A ⊆ B und B ⊆ A. Dan...