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

Elementare Zahlentheorie

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

1. Für welche a, b ∈ ℤ und A, B ∈ ℕ gilt

\frac{a}{A} + \frac{b}{B} = \frac{a + b}{A + B} ?

2. (a) Es sei 2 < q ∈ ℕ. Zeigen Sie, daß die Summe aller Elemente eines primen Restsystems modq durch q teilbar ist.

(b) Es sei p ≥ 3 prim. Zeigen Sie die Kongruenz

1^{2} · 3^{2} · 5^{2} ⋯ (p − 2)^{2} ≡ (−1)^{\frac{p+1}{2}} mod p .

3. Zu q ∈ ℕ, a ∈ ℤ mit (a, q) = 1 sei h := min {k ∈ ℕ : a^{k} ≡ 1 mod q}. Zeigen Sie

für m ∈ ℕ:

a^{m} ≡ 1 mod q ⟺ h | m .

4. Zeigen Sie φ(m n) φ((m, n)) = (m, n) φ(m) φ(n) für alle m, n ∈ ℕ.

5. Es seien a, n ∈ ℕ \ {1} derart, daß a^{n−1} ≡ 1 mod n, aber a^{d} ≢ 1 mod n für alle echten Teiler d von n − 1 gelten. Zeigen Sie, daß n prim ist.