Übungen

Übung 1

Beweisen Sie die Eigenschaften (G1) − (G5) des größten gemeinsamen Teilers mit Hilfe der Eigenschaften der Teilbarkeitsrelation.

Übung 2

Beweisen Sie die Eigenschaft (G6) − (G10) des größten gemeinsamen Teilers mit Hilfe der Eigenschaften der Teilbarkeitsrelation und der Eindeutigkeit der Primfaktorzerlegung.

Übung 3

Sei n ≥ 2, und seien a₁, …, a_n + 1  ∈  ℤ. Zeigen Sie:

(a₁, …, a_n + 1)  =  ((a₁, …, a_n), a_n + 1).

Übung 4

Seien a, b, c  ∈  ℤ. Zeigen Sie, dass die folgenden Distributivgesetze gelten:

Übung 5

Führen Sie den Euklidischen Algorithmus für a = 132 und b = 84 in beiden Versionen durch und stellen Sie (a, b) als Linearkombination von a und b dar.

Übung 6

Zeigen Sie mit Hilfe der Teilbarkeitseigenschaften (T1) − (T7) und der Division mit Rest (ohne Verwendung der Eindeutigkeit der Primfaktorzerlegung), dass für alle a, b, c, d, p gilt:

[ zu (a):  Verwenden Sie Division mit Rest.

zu (b):  Sei v = [ d, (a, b) ]. Zeigen Sie v = (a, b) mit Hilfe von (a).

zu (c):  Ohne Einschränkung seien a, b ≠ 0 und c > 0. Wir setzen d = (a, b) und d′ = (ca, cb). Zeigen Sie cd ≤ d′ und weiter d′ ≤ cd mit Hilfe von (b).

zu (d): Verwenden Sie (c). ]

Übung 7

Zeigen Sie den Teilbarkeitssatz von Euklid mit Hilfe des Ergebnisses, dass der größte gemeinsame Teiler zweier Zahlen eine Linearkombination der beiden Zahlen ist.

Übung 8

Zeigen Sie die Eindeutigkeit der Primfaktorzerlegung mit Hilfe des Teilbarkeitssatzes von Euklid.

Übung 9

Sei A eine unendliche Menge ganzer Zahlen, und sei d ≥ 1 die größte Zahl, die alle Elemente von A teilt. Zeigen Sie, dass a₁, …, a_n  ∈  A existieren mit

d  =  (a₁, …, a_n).

Übung 10

Sei n ≥ 2, und seien a₁, …, a_n  ∈  ℤ. Zeigen Sie, dass

{ k₁a₁ + … + k_na_n | k₁, …, k_n   ∈  ℤ }  =  { d (a₁, …, a_n) | d  ∈  ℤ }.

Übung 11

Zeigen Sie, dass für alle q₀, …, q_n ≥ 1 gilt: [ q₀, …, q_n, 1 ] = [ q₀, …, q_n + 1 ].

Übung 12

Seien q₀, …, q_n ≥ 1 mit q_n ≠ 1. Weiter seien a > b ≥ 1 mit a/b = [ q₀, …, q_n ]. Zeigen Sie, dass q₀, …, q_n die Folge der Quotienten ist, die der Euklidische Algorithmus für a, b erzeugt.

Übung 13

Berechnen Sie die Kettenbrüche

[ 2 ],  [ 2, 2 ],  [ 2, 2, 2 ],  [ 2, 2, 2, 2 ],  [ 2, 2, 2, 2, 2 ]

in Form gekürzter Brüche. Bestimmen Sie zudem den Wert der unendlichen Kettenbrüche [ 2, 2, 2, … ] und [ 1, 2, 2, 2, … ].

Übung 14

Seien A, B, C, D, E die Ecken eines regelmäßigen Fünfecks mit Seitenlänge AB = 1 und Diagonale d = AC. Zeigen Sie durch geometrische Argumentation, dass der Euklidische Algorithmus für d und 1 die unendliche Quotientenfolge 1, 1, 1, … erzeugt, sodass d der goldene Schnitt ist.

Übung 15

Sei d die Länge der Diagonale des Einheitsquadrats. Zeigen Sie durch geometrische Argumentation, dass der Euklidische Algorithmus für d und 1 die unendliche Quotientenfolge 2, 1, 1, 1, … erzeugt. Dies liefert einen weiteren Beweis für die Irrationalität der Quadratwurzel aus 2.

Übung 16

Bestimmen Sie die kleinste natürliche Zahl x ≥ 1, die bei Division durch 2, 3, 5 und 7 die Reste 0, 2, 3 bzw. 4 besitzt.

Übung 17

Lösen Sie die Kongruenz 17x ≡  1 mod(60), indem die Kongruenzen

17x ≡  1 mod(4),  17x ≡  1 mod(3),  17x ≡  1 mod(5)

durch Probieren lösen und den Chinesischen Restsatz anwenden.

Übung 18

Sei r ≥ 2, und seien m₁, …, m_r ≥ 1 und a₁, …, a_r ≥ 1 beliebig. Zeigen Sie, dass die folgenden Aussagen äquivalent sind:

Zeigen Sie weiter, dass im Fall der Existenz eine Lösung x modulo dem kgV m = [ m₁, …, m_r ] der Moduln eindeutig bestimmt ist.