Universität des Saarlandes FR 6.1, Mathematik Prof. Dr. E.-U. Gekeler Dipl.-Math. M. Gebhardt �

9. Übung zur elementaren Zahlentheorie, SS 2003

Aufgabe 1:(10 Punkte) Zeigen Sie:

∑_{m>k} \frac{1}{m(m − 1)} = \frac{1}{k}

Aufgabe 2:(10 Punkte) Es bezeichne p_{k} die k-te Primzahl. Zeigen Sie:

a) π(p_{1}p_{2} ⋯ p_{m}) ≥ 2m + 4 für m ≥ 3.

b) p_{m+1}^{2} < p_{1}p_{2} ⋯ p_{m} für m ≥ 4. (Hinweis: Nutzen Sie die (bewiesene) Bertrand’sche Vermutung, daß für alle n ∈ ℕ eine Primzahl p mit n < p ≤ 2n existiert.) Aufgabe 3:(10 Punkte) In der ganzen Aufgabe sind f, g, h Funktionen auf ℕ. Zeigen Sie:

a) f, g = O(h) ⇒ f + g = O(h)

b) f = O(g), g = O(h) ⇒ f = O(h)

c) f = O(g) ⇒ fh = O(gh)

d) die gültigen unter den folgenden Implikationen

f = O(g) ⇒ f + h = O(g + h)
f + h = O(|g + h|)
f + h = O(|g| + |h|)

e) ∑_{i=0}^{d} a_{i}n^{i} = O(n^{d}) (a_{0}, …, a_{d} ∈ ℝ beliebig )

f) Sind a, b > 0, so gilt log_{a}(n) = O(log_{b}(n)).

Aufgabe 4:(10 Punkte) Seien f und g die Funktionen f(x) = x^{a} und g(x) = x^{b} auf einer Teilmenge D von ℝ_{>0}, mit 0 < a < b. Unter welchen Voraussetzungen an D gilt

a) f = O(g) ?

b) g = O(f) ?

Abgabe am 04. Juli 2003 vor der Vorlesung