4. Übungsblatt

ZAHLENTHEORIE (SS 2007)

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

13. Aufgabe: Für n ∈ ℕ bezeichne R_{n} := {0, 1, 2, …, n − 1} die Menge der möglichen Reste bei Division durch n. Beweise: Für teilerfremde Zahlen m, n ∈ ℕ gilt

R_{mn} = { (lm + kn) mod (mn) | l ∈ R_{n} , k ∈ R_{m} } .

(2)

14. Aufgabe: Sei n ∈ ℕ. Für t ∈ T^{+}(n) sei

C_{t} := { r | r ∈ ℕ, 1 ≤ r ≤ n, ggT(r, n) = t } .
Beweise: a) C_{t} ≠ ∅  b) C_{s} ∩ C_{t} = ∅ für s ≠ t  c) ⋃_{t | n} C_{t} = {1, 2, …, n}
d) | C_{t} | = φ(\frac{n}{t})  e) ∑_{t | n} φ(t) = n.  (5)

15. Aufgabe: a) Beweise die Assoziativität der Faltung.

b) Welche bekannte zahlentheoretische Funktion ist 11⋆ I ? (Begründung!) Hierbei bezeichne 11 die Einsfunktion (n ⟼ 1 ∀ n ∈ ℕ) und I die Identität (n ⟼ n ∀ n ∈ ℕ) .

c) Untersuche, ob die Funktionen σ oder φ vollständig multiplikativ sind. (4)

16. Aufgabe: a) Seien m, n ∈ ℕ Zahlen, die nicht teilerfremd sind. Ferner sei P das Produkt der verschiedenen Primteiler von ggT(m, n) . Beweise:

φ(m · n) · φ(P) = φ(m) · φ(n) · P .

b) Sei n ≥ 3 eine ungerade natürliche Zahl und r die Anzahl der verschiedenen Primteiler von n. Beweise: 2^{r} | φ(n) . (3)

Wenn Sie mit dem Korrektor Andreas Kottmann sprechen wollen, schicken Sie ihm bitte eine email an die Adresse

kottmann@zitmail.uni-paderborn.de