08 Die ganzen Zahlen III

0:00 ...

Auf das Video Klicken zum Abspielen & Im Video ziehen zum Vor-/Zurückspielen

Timestamps

Daten werden geladen...

Die ganzen Zahlen III - Aufgabe 1 (von 6)

Erinnern Sie sich an den Euklidischen Algorithmus zur Bestimmung des ggt zweier natürlicher Zahlen $\geq 1$ ?

1. EINGABE $m, n > 0$ .
2. Falls $m = n$ ist, dann gib $m$ aus - ENDE.
3. Falls $m > n$ ist, vertausche die Zahlen $m$ und $n$ .
4. Ersetze $n$ durch $n - m$ und gehe zu Schritt 2.

Dieser Algorithmus ist schlecht, wenn die beiden Zahlen sehr weit auseinander liegen: Dann muss die kleinere Zahl sehr oft von der größeren Zahl subtrahiert werden. Durch die Division mit Rest kann der Algorithmus aber deutlich verbessert werden:

1. EINGABE $m, n > 0$ .
2. Falls $n = 0$ ist, dann gib $m$ aus - ENDE.
3. Falls $m > n$ ist, vertausche die Zahlen $m$ und $n$ .
4. Ersetze $n$ durch $n$ mod $m$ und gehe zu Schritt 2.

Dabei ist $n$ mod $m$ (sprich: n modulo m") der Rest, der bei der Division von $n$ durch $m$ bleibt - oder anders ausgedrückt: $n$ mod $m$ definiert die Restklasse $n$ im Ring $ℤ_{m}$ .

Beweisen Sie, dass der verbesserte Algorithmus ebenfalls funktioniert.

Wie schon beim klassischen Algorithmus genügt es zu zeigen, dass im Falle $n > m$ die Menge $M_{1}$ aller gemeinsamen Teiler von $m$ und $n$ gleich der Menge $M_{2}$ aller gemeinsamen Teilen von $m$ $r = n$ mod $m$ ist.
Es sei dazu $\begin{array}{r} n = q \cdot m + r \end{array}$ die zugehörige Division mit Rest.
$M_{1} \subseteq M_{2}$ Es sei $t \in M_{1}$ Dann gibt es natürliche Zahlen $k_{1}$ und $k_{2}$ mit $\begin{array}{r} m = k_{1} \cdot t u n d n = k_{2} \cdot t . \end{array}$ Dann ist $\begin{array}{r} n m o d m = r = n - q \cdot m = k_{2} \cdot t = (k_{2} - q k_{1}) \cdot t \end{array}$ und damit $t \in M_{2} .$
$M_{2} \subseteq M_{1}$ Es sei $x \in M_{2}$ Dann gibt es natürliche Zahlen $l_{1}$ und $l_{2}$ mit $\begin{array}{r} m = l_{1} \cdot x u n d n m o d m = r = l_{2} \cdot x . \end{array}$ Dann ist $\begin{array}{r} n = q \cdot m + r = q l_{1} \cdot x = (q l_{1} + l_{2}) \cdot x \end{array}$ und damit $x \in M_{1}$ .
Fertig!

Die ganzen Zahlen III - Aufgabe 2 (von 6)

Hier nochmal der verbesserte Euklidische Algorithmus.

1. EINGABE $m, n > 0 .$
2. Falls $n = 0$ ist,
dann gib $m$ aus - ENDE.
3. Falls $m > n$ ist, vertausche die Zahlen $m$ und $n$ .
4. Ersetze $n$ durch $n$ mod $m$ und gehe zu Schritt 2.

Wie gut ist er wirklich?

Versuchen Sie, die schrittweise Entwicklung eines Zahlenpaares $(m, n)$ im verbesserten Euklidischen Algorithmus zu konstruieren und zwar so, dass der im Vergleich zur Größe der Zahlen langsamste (schlechteste) Ablauf dabei entsteht. Bei welchen Eingaben braucht der Algorithmus also besonders lange?

Hinweis: Überlegen Sie sich den Ablauf "rückwärts", also ausgehend von einem Ergebnis $= 1$ . Welche (Ihnen bereits bekannte) Zahlenfolge entsteht dabei?

Der langsamste (schlechteste) Ablauf ergibt sich offenbar, wenn wir bei der Verringerung der Zahlen durch die "schnelle" Restbildung $n$ mod $m$ kein Tempo gewinnen im Vergleich zur einfachen Differenzbildung $n - m$ der klassischen Variante. Das bedeutet also stets $\begin{array}{r} n m o d m = n - m \end{array}$ für die ganze Entwicklung des Paares $(m, n)$ während der Laufzeit des Algorithmus. Ausgehend vom Ergebnispaar $(1,0)$ erhalten wir also die langsamste Entwicklung in der Form $\begin{array}{r} (1,0) \leftarrow (1,2) \leftarrow (2,1) \leftarrow \\ (2,3) \leftarrow (3,2) \leftarrow (3,5) \leftarrow (5,3) \\ \leftarrow (5,8) \leftarrow (8,5) \leftarrow (8,13) \\ \leftarrow (13,8) \leftarrow (13,21) \leftarrow (21,13) \\ \leftarrow (21,34) \leftarrow (34,21) \leftarrow (34,55) \\ \leftarrow . . . \end{array}$ Das sind die FIBONACCI-Zahlen! Deren Wachstumsverhalten kennen wir schon von früher, es ist exponentiell. Die Anzahl der Schritte des Algorithmus hängt also im schlechtesten Fall logarithmisch von der größeren der beiden Eingabezahlen $(= N)$ ab. Die Zeitkomplexität dieses Algorithmus schreibt man dann als $O (l o g N) .$

Die ganzen Zahlen III - Aufgabe 3 (von 6)

Zeigen Sie, dass für ein Ideal $I$ in einem Ring $R$ durch $\begin{array}{r} x \sim y ⟺ x - y \in I \end{array}$ eine Äquivalenzrelation auf $R$ definiert wird.
Warum ist in dieser Situation auf der Menge $\begin{array}{r} R / I = {b : a \in R} \end{array}$ durch die Festlegungen $\begin{array}{r} a + b = a + b u n d a \cdot b = a b \end{array}$ tatsächlich eine wohldefinierte Ringstruktur gegeben?

Reflexivität: $x \sim x$ wegen $x - x = 0 \in I .$
Symmetrie: Falls $x \sim y$ , dann ist auch $y \sim z$ $x - y \in I$ , denn es gilt $\begin{array}{r} y - x = - (x - y) \in I \end{array}$ falls $x - y \in I$ ist.
Transitivität: Falls $x \sim y$ und $y \sim z$ ist, dann ist $x - y \in I$ und $y - z \in I .$
Klarerweise ist dann auch $\begin{array}{r} x - z = (x - y) + (y - z) \in I . \end{array}$ also $x \sim z$ . Die Relation ist daher eine Äquivalenzrelation. Wir haben übrigens gar nicht die vollen Idealeigenschaften von $I$ benötigt. Es genügt, dass $I$ bezüglich der Addition eine Untergruppe von $R$ ist.

Zur wohldefinierten Ringstruktur auf $R / I$ betrachten wir die Multiplikation $\begin{array}{r} a \cdot b = a b, \end{array}$ die Addition geht genauso. Warum ist diese Definition unabhängig von der Auswahl der Repräsentanten?

Wir betrachten dazu ein zu $a$ äquivalentes Element $a^{'}$ , also $a - a^{'} \in I .$ Dann ist $a^{'} = a - c$ für ein $c \in I$ und daher $\begin{array}{r} a^{'} - b = a^{'} b = (a – c) b = a b - c b = a b - c b = a b, \end{array}$ da $c \cdot b \in I$ liegt, denn $I$ ist ein Ideal. Hier haben wir also die volle Idealeigenschaft von $I$ benötigt.

Das Ersetzen des Repräsentanten im zweiten Faktor verläuft genauso. Die Ringgesetze gelten klarerweise, da sie für die Repräsentanten gelten. Also haben wir cine wohldefinierte Ringstruktur auf $R / I .$

Die ganzen Zahlen III - Aufgabe 4 (von 6)

Finden Sie in $\begin{array}{r} ℤ = {0, 1, 2, 3, . . ., 7} \end{array}$ die Nullteiler heraus.

Bestimmen Sie danach die Elemente, welche bezüglich der Multiplikation ein inverses Element besitzen. Diese Elemente nennt man übrigens die Einheiten des Ringes. Gibt es Elemente, die weder Nullteiler noch Einheit sind?

Die Nullteiler sind die Elemente $2$ und $4$ (wegen $2 \cdot 4 = 8 = 0$ ), sowie $6$ (wegen $6 \cdot 4 = 24 = 0$ ). Alle übrigen Elemente (außer der $0$ ) sind Einheiten: $\begin{array}{r} 1 \cdot 1 = 1 = 1 \end{array}$ $\begin{array}{r} 3 \cdot 3 = 9 = 1 \end{array}$ $\begin{array}{r} 5 \cdot 5 = 25 = 1 \end{array}$ $\begin{array}{r} 7 \cdot 7 = 49 = 1 \end{array}$ Das einzige Element, welches weder Nullteiler noch Einheit ist, ist das Element $0$ .

Die ganzen Zahlen III - Aufgabe 5 (von 6)

Beweisen Sie: In der Menge $ℤ_{n} {0}$ gibt es nur Nullteiler und Einheiten. Ein Element $a$ ist genau dann eine Einheit, wenn es teilerfremd zu $n$ ist, also ggT $(a, n) = 1$ ist. Folgern Sie daraus, dass $ℤ_{n}$ genau dann ein Körper ist, wenn $n$ eine Primzahl ist.

Es sei ggT $(a, n) = 1$ . Dann gibt es ganze Zahlen $k$ und $l$ mit $k \cdot a + 1 \cdot n = 1$ . Dies bedeutet aber $\begin{array}{r} k \cdot a = k a = 1, \end{array}$ also ist $a$ eine Einheit.

Es sei umgekehrt $a$ eine Einheit in $ℤ_{n}$ . Wir nehmen an, dass ggT $(a, n) > 1$ ist.

Da $a$ eine Einheit ist, gibt es ein $b \in ℤ_{n}$ mit $\begin{array}{r} a b = a \cdot b = 1 . \end{array}$ Also haben wir ein $k \in ℤ$ mit $\begin{array}{r} a \cdot b + k \cdot n = 1 . \end{array}$ Wir können auf der linken Seite ggT $(a, n)$ ausklammern und erhalten den gewünschten Widerspruch, denn das Produkt zweier ganzer Zahlen, bei denen eine $> 1$ ist, kann niemals gleich $1$ sein.

Warum sind die übrigen Elemente allesamt Nullteiler? Es sei dazu $a \neq 0$ keine Einheit, also $g = g g T (a, n) > 1 .$

Mit $n = g \cdot n^{'}$ ist dann $a \cdot n^{'}$ ein Vielfaches von $n$ , denn der Faktor $g$ ist auch in $a$ enthalten. Wegen $1 \leq n^{'} < n$ ist $n^{'} \neq 0$ und die Gleichung $\begin{array}{r} a \cdot n^{'} = 0 \end{array}$ weist $a$ schließlich Nullteiler aus.

Die ganzen Zahlen III - Aufgabe 6 (von 6)

Berechnen Sie im Körper $ℤ_{7}$ $\begin{array}{r} 2 : 3 = \end{array}$ $\begin{array}{r} 6 : 4 = \end{array}$ $\begin{array}{r} 5 : 6 = \end{array}$

In $ℤ_{7}$ ist $\begin{array}{r} 3 \cdot 5 = 1, a l s o 3^{- 1} = 5 . \end{array}$ Genauso ergibt sich $\begin{array}{r} (4)^{- 1} = 2 u n d 6^{- 1} = 6 . \end{array}$
Damit gilt $\begin{array}{r} 2 : 3 = 2 \cdot (3)^{- 1} = 2 \cdot 5 = 3 \end{array}$ $\begin{array}{r} 6 : 4 = 6 \cdot (4)^{- 1} = 6 \cdot 2 = 5 \end{array}$ $\begin{array}{r} 5 : 6 = 5 \cdot (6)^{- 1} = 5 \cdot 6 = 2 . \end{array}$