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

Elementare Zahlentheorie

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

1. Untersuchen Sie, ob die folgenden Kongruenzen lösbar sind :

(a) x^{2} ≡ 82 mod 229 ,

(b) x^{2} ≡ 238 mod 263 ,

(c) 2x^{2} + 93x − 83 ≡ 0 mod q, wobei q := 29^{2} · 37 .

2. Zeigen Sie, daß die Gleichung (∗) x^{2} + 3xy − 2y^{2} = 122 keine Lösungen x, y ∈ ℤ besitzt.

Anleitung: Zeigen Sie zunächst, daß aus der Lösbarkeit von (∗) die Lösbarkeit der Kongruenz z^{2} ≡ 488 mod 17 folgt.

3. Ermitteln Sie alle Primteiler der Folge (n^{2} − 28).

Es sei 1 ≠ q ∈ ℕ. Gibt es in der primen Restklassengruppe G(q) ein Element a der Ordnung φ(q), so ist G(q) zyklisch und a heißt eine Primitivwurzel mod q. Die beiden folgenden Aufgaben haben die Existenz von Primitivwurzeln mod p für Primzahlen p zum Ziel.

4. Es sei p eine Primzahl und a ∈ G(p) ein Element der Ordnung h. Zeigen Sie :

(a) Alle Lösungen der Kongruenz x^{h} ≡ 1 mod p sind gegeben durch die Restklassen a^{k} mit k = 0, 1, …, h − 1 .

(b) Alle Elemente von G(p) der Ordnung h sind durch a^{k} mit k ∈ {0, …, h − 1}, ggT (h, k) = 1, gegeben.

5. Es sei p eine Primzahl. Zu jedem Teiler h ∈ ℕ von p − 1 bezeichne ψ(h) die Anzahl der Elemente von G(p) der Ordnung h.

(a) Zeigen Sie ∑_{h|p−1} ψ(h) = ∑_{h|p−1} φ(h) .

(b) Folgern Sie, daß G(p) zyklisch ist.