[figure: TU CLAUSTHAL; INSTITUT FÜR MATHEMATIK; Prof. Dr. W. Klotz; Lineare Algebra I; WS 1999/2000; Übungsblatt 1; Übung vom 28.10.99]

Bitte beschäftigen Sie sich bis zur Übung mit folgenden Aufgaben. Machen Sie sich die Begriffe und die Notation klar, suchen Sie Beispiele und versuchen Sie, die gefragten Beweise zu führen. Die Aufgaben werden in der Übung besprochen; Lösungen sind nicht abzugeben.

1. Man definiert die Teilbarkeit ganzer Zahlen durch

a|b ⇔ ∃x(x ∈ ℤ ∧ b = ax).

Man zeige:

a) a|b ∧ b|a ⇒ b = ±a,

b) a|b ∧ b|c ⇒ a|c,

c) a|b ∧ a|c ⇒ ∀x, y ∈ ℤ : (a | xb + yc).

2. Bekanntlich nennt man eine natürliche Zahl p > 1 eine Primzahl, wenn ihre positiven Teiler nur die trivialen Teiler 1 und p sind. Man zeige:

a) Ist n ∈ ℕ, n > 1 und a ∈ ℕ der kleinste Teiler von n, der größer als 1 ist, dann ist a eine Primzahl.

b) Jede natürliche Zahl n > 1 ist Produkt von Primzahlen.

3. Sind a, b ∈ ℕ, b ≠ 0, dann gibt es eindeutig bestimmte Zahlen q, r ∈ ℕ_{0} = ℕ ∪ {0} mit

a = qb + r, 0 ≤ r < b.

Wir nennen diese Darstellung die Euklidische Zerlegung von a bzgl. b. Dabei ist r der Rest der Division von a durch b. Man bilde folgendes Schema Euklidischer Zerlegungen:

a  = q \underline{b}  + \underline{r}, 0 ≤ r < b
b  = q_{1} \underline{r}  + \underline{r}_{1}, 0 ≤ r_{1} < r
r  = q_{2} \underline{r}_{1}  + \underline{r}_{2}, 0 ≤ r_{2} < r_{1}
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
r_{n−2} = q_{n} \underline{r_{n−1}} + \underline{r_{n}}, 0 ≤ r_{n} < r_{n−1}
r_{n−1} = q_{n+1} r_{n}.

Man zeige:

a) Das Schema endet mit einem letzten nichtverschwindenden Rest r_{n}.

b) Es gibt ganze Zahlen x, y mit r_{n} = xa + yb.

c) Es ist r_{n} der größte gemeinsame Teiler von a und b, in Zeichen: r_{n} = ggT (a, b).

Man nennt das skizzierte Verfahren zur Bestimmung von ggT (a, b) den Euklidischen Algorithmus.

4. Man beweise:

a) a|bc ∧ ggT (a, b) = 1 ⇒ a|c.

b) Die Darstellung einer natürlichen Zahl n als Produkt von Primzahlen ist bis auf die Reihenfolge der Faktoren eindeutig.