Technische Universität Clausthal WS 1999/2000 Institut für Mathematik 15.11.1999 Prof. Dr. L. G. Lucht 4. Übungsblatt

Elementare Zahlentheorie

Diese Aufgaben werden in der Übungsstunde vom 24.11.1999 besprochen; Abgabe schriftlicher Lösungen bitte am Montag, 22.11.1999, vor der Vorlesung.

1. Bestimmen Sie ggf. alle Lösungen der folgenden Kongruenzen:

(a) 20 x ≡ 30 mod 4 ; (c) 15 x ≡ 25 mod 35 ;

(b) 15 x ≡ 0 mod 35 ; (d) 353 x ≡ 254 mod 400 .

2. Bestimmen Sie ggf. die Lösungen folgender Kongruenzsysteme:

(a) x ≡ 1 mod 8  (b) 4x ≡ 7 mod 15
x ≡ 2 mod 25  5x ≡ 2 mod 21
x ≡ 3 mod 11 ;  49x ≡ 7 mod 35 .

3. Es seien a, b ∈ ℤ teilerfremd und n ∈ ℕ. Zeigen Sie die Existenz eines x ∈ ℤ mit ggT (ax + b, n) = 1.

(Hinweis: Es sei p ein Primteiler von n. Die Kongruenz ax + b ≡ 0 mod p ist lösbar genau für p ∤ a. Chinesischer Restsatz.)

4. Es seien a ∈ ℤ und p prim mit p ∤ 2a. Zeigen Sie, daß die Kongruenz x^{2} ≡ a mod p^{k} für jedes k ∈ ℕ lösbar ist, wenn sie für k = 1 lösbar ist.

5. (a) Beweisen Sie: 561 ist keine Primzahl, aber dennoch gilt x^{561} ≡ x mod 561 für alle x ∈ ℤ.

(b) Eine zusammengesetzte Zahl n heißt Carmichaelzahl, wenn x^{n} ≡ x mod n für alle x mit (n, x) = 1 gilt.

Zeigen Sie : Wenn die drei Zahlen 6m + 1, 12m + 1 und 18m + 1 alle prim sind, dann ist die Zahl n = (6m + 1)(12m + 1)(18m + 1) eine Carmichaelzahl. Geben Sie ein Beispiel für eine solche Zahl an.