6. Übungsblatt

ZAHLENTHEORIE (SS 2007)

Abgabe: Mi. 23.5.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!

21. Aufgabe: Seien n ∈ ℕ und a ∈ ℤ. Beweise die Äquivalenz der folgenden Aussagen:

a) ggT(a, n) = 1

b) Es existiert ein k ∈ ℕ mit a^{k} ≡ 1 (mod n) . (2)

22. Aufgabe: Seien a, b ∈ ℤ und n_{1}, n_{2}, …, n_{r} ∈ ℕ (r ≥ 2) .

a) Sei k := kgV(n_{1}, n_{2}, …, n_{r}) . Beweise:

a ≡ b (mod n_{i}) (∀ i = 1, 2, …, r) ⟹ a ≡ b (mod k)

b) Welche Form hat das Ergebnis aus a) wenn man voraussetzt, daß die Zahlen n_{1}, n_{2}, …, n_{r} paarweise teilerfremd sind? Begründung! (2)

23. Aufgabe: Stelle nach der in der Vorlesung behandelten Methode eine Regel für die Teilbarkeit einer natürlichen Zahl a durch 16 auf und beweise diese. Benutze diese Regel, um zu prüfen, ob die Zahl 1 975 296 durch 16 teilbar ist.

b) Stelle eine Regel für die Teilbarkeit einer natürlichen Zahl a durch 176 auf und beweise diese. Benutze diese Regel, um zu prüfen, ob die Zahl 608 394 864 durch 176 teilbar ist. (3)

24. Aufgabe: Seien n ∈ ℕ und a ∈ ℤ mit ggT(a, n) = 1 . Beweise:

a) a hat genau dann die Ordnung k modulo n, wenn die beiden folgenden Bedingungen erfüllt

sind: i) a^{k} ≡ 1 (mod n) und ii) a^{\frac{k}{p}} ≢ 1 (mod n) für alle p ∈ T_{IP}(k) .

b) a hat genau dann die Ordnung φ(n) modulo n, wenn gilt: a^{\frac{φ(n)}{p}} ≢ 1 (mod n) für alle p ∈ T_{IP}(φ(n)) .

c) Ist p ∈ IP eine Primzahl mit p ≡ 1 (mod 4) und p |̸ a und gilt ord_{p}(a) = p − 1 , so folgt auch ord_{p}(−a) = p − 1 .

d) Untersuche, ob die Aussage in c) auch für alle Primzahlen p mit p ≡ 3 (mod 4) richtig ist. (5)

25. Aufgabe: Bestimme die kleinste positive Zahl a ∈ ℤ mit ord_{23}(a) = 22 . (2)

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