Prof. Dr. M. Kreuzer Abgabetermin: 15.11.2002, 9.00 Uhr

Lineare Algebra I

Übungsblatt 4

Aufgabe 1 (P): (Ein Ring, sie zu knechten, sie alle zu finden, ins Dunkel zu treiben und ewig zu binden.) Sei R ein Integritätsring mit Einselement. Besitzt R nur endlich viele Elemente, so ist (R\{0}, ·) eine Gruppe.

Aufgabe 2 (P): (Das also war des Pudels Kern! Ein fahrender Skolast? Der Casus macht mich lachen.) Seien R, S zwei kommutative Ringe mit Einselement, und sei f : R → S ein Ringhomomorphismus.

a) Zeigen Sie, dass der Kern von f, also die Menge Kern(f) = {a ∈ R | f(a) = 0} ein Ideal in R ist.

b) Beweisen Sie, dass f genau dann injektiv ist, wenn Kern(f) = {0} gilt.

Aufgabe 3 (P): (Ringhomomorphismus = die irrationale Hoffnung, Karten für die Bayreuther Festspiele zu ergattern.) Gegeben sei eine positive ganze Zahl n.

a) Zeigen Sie, dass die Abbildung \begin{aligned}φ & : & ℤ → ℤ/nℤ \\ & & a ↦ a + nℤ \end{aligned} einen Ringhomomorphismus defi-

niert. Ist φ injektiv? Ist φ surjektiv? Was ist der Kern von φ?

b) Für welche Zahlen m ∈ ℕ_{+} gibt es einen von der Nullabbildung verschiedenen Ringhomomorphismus ψ : ℤ/nℤ → ℤ/mℤ?

Tipp: Untersuchen Sie zuerst die Fälle m = 2n und m = n + 1.

Aufgabe 4 (D+L): (In der Theorie gibt es keinen Unterschied zwischen Theorie und Praxis. In der Praxis jedoch gibt es ihn.)

a) Schreiben Sie ein Maple–Programm Euklid (a, b), das den größten gemeinsamen Teiler zweier ganzer Zahlen a, b mit Hilfe des euklidischen Algorithmus berechnet. Wenden Sie Ihr Programm an mindestens zehn selbst gewählten Beispielen an und demonstrieren Sie so seine korrekte Funktion.

b) Bauen Sie in Ihr Programm Euklid (a, b) einen Zähler ein, der protokolliert, wie oft die Division mit Rest in Schritt 6 aufgerufen wurde. Finden Sie dann die zwei Zahlen a, b zwischen 1 und N = 40, für die der euklidische Algorithmus die meisten Schritte braucht. c) Wiederholen Sie Teil b) mit N = 80 und N = 160. Fällt Ihnen etwas auf? Formulieren

Sie eine Vermutung und geben Sie möglichst schlagkräftige Argumente dafür an.

Aufgabe 5 (D): (Buch 7, Proposition 2: Antenaresis) Seien a, b ∈ ℤ. Betrachten Sie die folgenden Instruktionen:

1) Ist a = b = 0, so gib (0, 0, 0) aus und stoppe.

Ist a = 0 und b ≠ 0, so gib (0, \frac{|b|}{b}, |b|) aus und stoppe.

Ist a ≠ 0 und b = 0, so gib (\frac{|a|}{a}, 0, |a|) aus und stoppe.

2) Bilde die Tripel (c_{0}, d_{0}, e_{0}) = (\frac{|a|}{a}, 0, |a|) und (c_{1}, d_{1}, e_{1}) = (0, \frac{|b|}{b}, |b|).

3) Prüfe, ob e_{1} ≤ e_{0} gilt. Falls nicht, so vertausche (c_{0}, d_{0}, e_{0}) und (c_{1}, d_{1}, e_{1}) miteinander.

4) Schreibe e_{0} in der Form e_{0} = qe_{1} + r mit q ∈ ℕ und 0 ≤ r < e_{1}. Bilde dann das Tripel (c_{2}, d_{2}, e_{2}) = (c_{0} − qc_{1}, d_{0} − qd_{1}, r).

5) Ersetze (c_{0}, d_{0}, e_{0}) mit (c_{1}, d_{1}, e_{1}) und (c_{1}, d_{1}, e_{1}) mit (c_{2}, d_{2}, e_{2}).

6) Wiederhole die Schritte 4) und 5) solange, bis e_{1} = 0 gilt. Dann gib das Tripel (c_{0}, d_{0}, e_{0}) aus und stoppe.

a) Beweisen Sie, dass dies einen Algorithmus definiert, der ein Tripel (c, d, e) berechnet, so dass e =ggT(a, b) und ac + bd = e gilt.

b) Schreiben Sie eine Maple–Funktion Ext Euklid (a, b), die diesen Algorithmus implementiert. Wenden Sie Ihre Funktion in mindestens 10 Fällen an, und demonstrieren Sie so ihre korrekte Funktionsweise.

How do you make Windows faster? Throw it harder!