Übungen
Übung 1 (Teilbarkeit, I)
Zeigen Sie, dass für alle a, b, c, d, …, n, m, … gilt:
(T1) a|a, 1|a, a|0, 0|a gdw a = 0, d|a gdw |d|||a|,
(T2) d|a und a|d gdw |d| = |a|,
(T3) d|a und a ≠ 0 impliziert |d| ≤ |a|,
(T4) e|d und d|a impliziert e|a,
(T5) d|a impliziert d|(a b) und (n d)|(n a),
(T6) (ca)|(cb) und c ≠ 0 impliziert a|b,
(T7) d|a und d|b impliziert d|(na + mb).
Übung 2 (Teilbarkeit, II)
Zeigen Sie, dass für alle n gilt:
(i) | 6|(n (n + 1) (n + 2)), |
(ii) | 2|(n2 − n), 6|(n3 − n), 30|(n5 − n), |
(iii) | 8|(n2 − 1), falls n ungerade. |
Übung 3 (Teilbarkeit, III)
Zeigen Sie, dass die Kongruenz modulo m eine Äquivalenzrelation auf ℤ ist. Zeigen Sie weiter, dass aus a ≡ b mod(m) und c ≡ d mod(m) stets folgt:
(i) | a + c ≡ b + d mod(m), |
(ii) | k a ≡ k b mod(m) für alle k, |
(iii) | a · c ≡ b · d mod(m), |
(iv) | an ≡ bn mod(m) für alle n ≥ 0. |
(v) | a ≡ b mod(d) für alle Teiler d von m mit d ≥ 1. |
Insbesondere ist die Kongruenz modulo m also eine Kongruenzrelation für die Addition und die Multiplikation auf ℤ.
Übung 4 (Teilbarkeit, IV)
Bestimmen Sie für m = 13 und m = 15 alle Paare a, b mit 0 ≤ a, b < m mit
ab ≡ 1 mod(m).
Sehen Sie eine Besonderheit für m = 13? Erstellen Sie weitere Tabellen, um Ihre Hypothesen zu überprüfen.
Übung 5 (Größter gemeinsamer Teiler, I)
Zeigen Sie, dass für alle a, b, c, n, m gilt:
(G1) ggT(a, a) = ggT(0, a) = |a|,
(G2) ggT(a, b) = ggT(b, a) = ggT(|a|, |b|),
(G3) a|b gdw ggT(a, b) = |a|,
(G4) ggT(a, b) ≤ ggT(a, na + mb),
(G5) ggT(a, b) = ggT(a, na + b).
Übung 6 (Größter gemeinsamer Teiler, II)
Sei v = kgV(m, n). Zeigen Sie, dass für alle a, b gilt:
a ≡ b mod(m) und a ≡ b mod(n) gdw a ≡ b mod(v).
Übung 7 (Größter gemeinsamer Teiler, III)
Sei n ≥ 1, und seien a1, …, an ganze Zahlen, die nicht alle gleich 0 sind.
Dann ist der größte gemeinsame Teiler von a1, …, an, in Zeichen ggT(a1, …, an), definiert als das größte m ≥ 1 mit m|ai für alle 1 ≤ i ≤ n. Wir setzen zudem ggT(0, …, 0) = 0. Zeigen Sie, dass für alle n ≥ 2 und alle a1, …, an + 1 gilt:
ggT(a1, …, an + 1) = ggT(ggT(a1, …, an), an + 1).
Übung 8 (Größter gemeinsamer Teiler, IV)
Sei A ⊆ ℕ unendlich, und sei d ≥ 1 die größte Zahl, die alle a ∈ A teilt. Zeigen Sie: Es gibt a1, …, an ∈ A mit d = ggT(a1, …, an).
Übung 9 (Der Euklidische Algorithmus, I)
Führen Sie den Euklidischen Algorithmus für die Zahlen 84 und 132 durch, und stellen Sie ggT(84, 132) in der Form a · 84 + b · 132 dar.
Übung 10 (Der Euklidische Algorithmus, II)
Zeigen Sie, dass sich die Reste, die der Euklidische Algorithmus erzeugt, nach jedem zweiten Schritt mindestens halbiert haben.
Übung 11 (Linearkombinationen, I)
Zeigen Sie, dass für alle n ≥ 2 und alle a1, …, an gilt:
{ m1 a1 + … + mn an | mi ∈ ℤ } = { k · ggT(a1, …, an) | k ∈ ℤ }.
Übung 12 (Linearkombinationen, II)
(a) | Zeigen Sie, dass für alle a, b gilt: |a · b| = ggT(a, b) · kgV(a, b). |
(b) | Sei d = ggT(k, m). Zeigen Sie, dass für alle a, b gilt: ka ≡ kb mod(m) gdw a ≡ b mod(m/d). Ist also ggT(k, m) = 1, so gilt: ka ≡ kb mod(m) gdw a ≡ b mod(m). |
[ Zeigen Sie (a) mit Hilfe von (G8) zuerst für den Fall ggT(a, b) = 1. Im allgemeinen Fall ist dann weiter Übung 6 nützlich. ]
Übung 13 (Linearkombinationen, III)
Ein nichtleeres I ⊆ ℤ heißt ein Ideal, falls I abgeschlossen unter Linearkombinationen ist, d. h. für alle a, b ∈ I und alle n, m ∈ ℤ ist na + mb ∈ I.
Zeigen Sie, dass für jedes Ideal I ein eindeutiges d ∈ ℕ existiert mit
I = { kd | k ∈ ℤ }.
Übung 14 (Linearkombinationen, IV)
Sei A ⊆ ℕ nichtleer und abgeschlossen unter Addition, d. h. für alle a, b ∈ A ist a + b ∈ A. Weiter sei 1 der größte gemeinsame Teiler aller Zahlen in A.
Zeigen Sie: Es gibt ein k0 ∈ ℕ derart, dass k ∈ A für alle k ≥ k0 gilt.
[ Seien a1, …, an ∈ A mit ggT(a1, …, ak) = 1. Seien ni ∈ ℤ mit n1 a1 + … + nk ak = 1. Gruppierung in positive und negative Summanden liefert 1 = c − d mit c, d ∈ A. Dann ist k0 = (d + 1)(d − 1) wie gewünscht: Wir schreiben hierzu ein k ≥ k0 als k = a d + r, mit 0 ≤ r < d. Dann ist a ≥ d − 1, und k = a d + r = a d + r (c − d) ∈ A. ]
Übung 15 (Primzahlen, I)
Sei p eine Primzahl mit p ≡ 1 mod(3). Zeigen Sie, dass p ≡ 1 mod(6).
Übung 16 (Primzahlen, II)
Sei p = 2n − 1 eine Primzahl. Zeigen Sie, dass n eine Primzahl ist.
[ Es gilt (an − 1) = (an − 1 + an − 2 + … + a1 + 1)(a − 1) für alle a. ]
Übung 17 (Primzahlen, III)
Sei k ≥ 1 beliebig. Zeigen Sie, dass es ein n gibt, sodass alle Zahlen n, n + 1, n + 2, …, n + k zusammengesetzt sind.
Übung 18 (Primzahlen, IV)
Zeigen Sie, dass es unendlich viele Primzahlen p der Form p = 4 k + 3 gibt.
[ Betrachten Sie n = 2 · 2 · p1 · … · pn − 1. ]
Übung 19 (Primzahlen, V)
Zeigen Sie, dass es unendlich viele Primzahlen p der Form p = 6 k + 5 gibt.
Übung 20 (Primzahlen, VI)
Für n ≥ 1 sei Fn = 22n − 1 die n-te Fermatsche Zahl. Zeigen Sie:
ggT(Fn, Fm) = 1 für alle n < m.
Folgern Sie hieraus, dass es unendlich viele Primzahlen gibt.
[ Zeigen Sie, dass Fn ein Teiler von Fm − 2 ist. Dann ist jeder gemeinsame Teiler von Fn und Fm ein Teiler von Fm − 2 und von Fm und daher gleich 1.
Zum Beweis von Fn|(Fm − 2) schreiben Sie (Fm − 2)/Fn in der Form (ak − 1)/(a + 1), a ≥ 1, k ≥ 2 gerade, und beweisen und verwenden, dass für diese a, k gilt:
(ak − 1)/(a + 1) = ak − 1 − ak − 2 + … − a0. ]
Übung 21 (Eindeutigkeit der Primfaktorzerlegung, I)
Seien n, m ≥ 2. Wie lassen sich alle Teiler von n anhand der kanonischen Primfaktorzerlegung von n beschreiben? Wie ermittelt man den größten gemeinsamen Teiler ggT(n, m) und das kleinste gemeinsame Vielfache kgV(n, m) von n und m anhand der kanonischen Primfaktorzerlegungen von n und m? Zeigen Sie mit Hilfe dieser Ergebnisse noch einmal, dass n · m = ggT(n, m) · kgV(n, m).
Übung 22 (Eindeutigkeit der Primfaktorzerlegung, II)
Die Zahlen 1, 4, 9, 16, …, n2, …, heißen Quadratzahlen.
Seien a, b ≥ 1 ungerade. Zeigen Sie, dass a2 + b2 keine Quadratzahl ist.
Übung 23 (Eindeutigkeit der Primfaktorzerlegung, III)
Zeigen Sie, dass die positive Quadratwurzel aus 3 irrational ist.
Übung 24 (Eindeutigkeit der Primfaktorzerlegung, IV)
Seien a0, …, ak − 1 ganze Zahlen, und sei x ∈ ℝ − ℤ mit
xk + ak − 1 xk − 1 + … + a0 = 0.
Zeigen Sie, dass x irrational ist.
[ Wir nehmen an, dass x = n/m für n ∈ ℤ und m ∈ ℕ+ gilt, wobei der Bruch n/m gekürzt sei. Dann gilt nk + ak − 1 nk − 1 m1 + … + a0 mk = 0, im Widerspruch zu ggT(n, m) = 1. ]