Universität Heidelberg Mathematisches Institut

Dr. Rolf Busam Andreas Riedel

Aufbau der Zahlsysteme

Sommersemester 2010

Aufgabenblatt 10 21. Juni 2010

Aufgabe 1. (4 Punkte) Seien m, n ∈ ℕ, a, b ∈ ℤ. Zeigen Sie, dass das Kongruenzsystem

x ≡ a mod (m)
x ≡ b mod (n)

genau dann lösbar ist, wenn ggT(m, n) | (a − b) gilt und die Lösungsmenge dann eine Restklasse mod kgV(m, n) ist.

Aufgabe 2. (4 Punkte) Bestimmen Sie das kleinste Vielfache von 7, dass bei Division durch 2, 3, 4, 5, 6 jeweils den Rest 1 lässt.

Aufgabe 3. (4 Punkte) Zeigen Sie: Eine natürliche Zahl n > 1 ist genau dann eine Primzahl, wenn (n − 1)! ≡ −1 mod (n) gilt.

Aufgabe 4. (4 Punkte) Sei p = 11, q = 13 und n = pq = 143. Bestimmen Sie φ(n) und ein e > 1 mit 1 < e < n und ggT(e, φ(n)) = 1. Bestimmen Sie d mit ed ≡ 1 mod φ(n). Codieren Sie x = 17 mit der Funktion E(x) = x^{e}. Wie lautet die decodierte Zahl, wenn Sie als verschlüsselte Nachricht y = 81 erhalten, wobei Sie n = 221 und e = 23 als öffentlichen Schlüssel herausgegeben hatten?

         Homepage zur Vorlesung: www.mathi.uni-heidelberg.de/~ariedel/zahlen

Abgabe bis spätestens 28. Juni 2010, in der Vorlesung.