11. Übungsblatt

ZAHLENTHEORIE (SS 2007) Abgabe: Mi. 27.6.2007, bis 9.10 Uhr Fach Nr. 11 (orangener Schrank bei D1.348) Internet: http://math-www.uni-paderborn.de/˜ chris

Schreiben Sie bitte auf die erste Seite gut leserlich Namen, Vornamen, Matrikel–Nr. und Ihre Übungsgruppe. Heften Sie bitte die Seiten zusammen!

Die folgenden Aufgaben sind auf Grundlage der Vorlesung und der Übungen zu bearbeiten!

43. Aufgabe: Berechne die folgenden Legendre– bzw. Jacobi–Symbole:

a) (\frac{5}{11}) , (\frac{7}{13}) mit Hilfe des Lemmas von Gauß (13.15) .

b) (\frac{131}{151}) , (\frac{2340}{28041}) , (\frac{392}{667}). (3)

44. Aufgabe: a) p, p′ und q seien ungerade Primzahlen. Beweise:

p ≡ p′ (mod 4q) ⟹ (\frac{q}{p}) = (\frac{q}{p′} ) .

b) Beweise: Zu jeder Primzahl q > 5 existiert eine Primzahl p mit 2 < p < q und (\frac{q}{p}) = 1 . (3)

45. Aufgabe: n > 2 sei eine beliebige natürliche Zahl. Die Zahlen a, b ∈ ℤ seien beide teilerfremd zu n. Beweise:

a) Sind a und b QR’e modulo n, so ist auch a · b ein QR modulo n

b) Ist a ein QR modulo n und b ein QNR modulo n, so ist a · b ein QNR modulo n

c) Existiert eine PW modulo n, so ist das Produkt zweier QNR’e ein QR modulo n

d) Untersuche, ob die Aussage in c) für beliebige natürliche Zahlen > 2 richtig ist. (3)

46. Aufgabe: a) (Dieser Aufgabenteil ist unabhängig vom Teil b) zu bearbeiten!) Bestimme die Anzahl der Lösungen von x^{6} ≡ 1 (mod 15) . Wieviele 6–te Potenzreste modulo 15 gibt es? Was ist der Zusammenhang zwischen diesen beiden Anzahlen. Wieviele Lösungen hat die Kongruenz x^{6} ≡ 4 (mod 15) ?

b) Seien m, n ∈ ℕ mit m ≥ 2 . Es bezeichne k die Anzahl der modulo n verschiedenen Lösungen der Kongruenz (⋆) x^{m} ≡ 1 (mod n) . Beweise:

1) E_{m} := { [a]_{n} | a ist Lösung von (⋆) } ist eine Untergruppe der Ordnung k von ℤ_{n}^{⋆}.

2) Ist c ∈ ℤ ein beliebiger m–ter Potenzrest modulo n, so hat die Kongruenz x^{m} ≡ c (mod n) genau k verschiedene Lösungen modulo n

3) Es gibt genau \frac{φ(n)}{k} verschiedene m–te Potenzreste modulo n. (5)

Wenn Sie mit dem Korrektor Andreas Kottmann sprechen wollen, schicken Sie ihm bitte eine email an die Adresse kottmann@zitmail.uni-paderborn.de