Proseminar Infinitesimalrechnung II Elementareigenschaften von Primzahlen

Gregor Schmitt, Markus Struzyna

21. April 1998

Definition 1.0 Seien a, b ∈ ℤ b ≠ 0. Dann heißt a teilbar durch b , wenn ∃c ∈ ℤ so daß a = cb. Dann heißt b Teiler von a, Bezeichnung: b|a. Ist b ≠ 0 und a nicht durch b teilbar, so schreibt man b ∤ a.

Lemma 1.1 Seien a, b, c ∈ ℤ. Aus :

i) b|a; b, a > 0 ⟹ 1 ≤ b ≤ a
ii) b|a ∧ c|b  ⟹ c|a (Transitivität)
iii) b|a ∧ c ≠ 0. ⟹ bc|ca
iv) c|a ∧ c|b  ⟹ c|(ma + nb), ∀m, n ∈ ℤ .

Beweis :i) b, a < 1 nicht möglich, da a, b > 0 vorausgesetzt. Da aber b|a ⟹ a = bc mit c ∈ ℕ . Daraus folgt aber b ≤ a □

ii) b|a ∧ c|b ⟹ ∃e, f ∈ ℤ so daß a = be ∧ b = cf ⟹ a = (cf)e ⟺ a = c(fe) ⟹ c|a □

iii) Sei c ≠ 0. Angenommen, es gelte bc ∤ ac ⟺ ∀e ∈ ℤ gilt bce ≠ ac ⟹ be ≠ a ∀e ∈ ℤ ⟹ b ∤ a. Widerspruch □

iv) Da c|a ∧ c|b∃e, f ∈ ℤ so daß ce = a ∧ cf = b. Nach 1.1.iii) gilt ∀m, n ∈ ℤ\{0} cem = am bzw. cfn = bn ⟹ c|bn ∧ c|am Es gilt ferner c(em) + c(fn) = am + nb ⟺ c(em + fn) = am + nb ⟹ c|(am + bn). □

Definition 1.2 Eine Zahl p ∈ ℕ , p > 1 heißt prim (Primzahl) genau dann, wenn ∀t ∈ ℕ mit t|p ⟹ t = 1 ∨ t = p. Eine Zahl n > 1, die nicht prim ist, heißt zusammengesetzt.

Satz 1.3 Fundamentalsatz der Arithmetik (Primfaktorzerlegung) Zu jeder Zahl n ∈ ℕ gibt es eindeutig bestimmte Zahlen a_{p} ∈ ℕ_{0}, so daß gilt:

n = ∏_{p} p^{a_{p}}

Insbesondere sind nur endlich viele a_{p} ≠ 0.

Beweis (Existenz): Da n > 1 ist n prim oder zusammengesetzt. Der Fall n ist prim ist klar. Sei also n zusammmengesetzt. Nach 1.2 ∃m ∈ ℤ mit 1 < m < n so daß m|n . Sei m der kleinste Teiler von n.

Behauptung : m ist prim. Angenommen m sei nicht prim, dann ∃k ∈ ℤ, so daß k|m ∧ 1 < k < m . Dann ist nach 1.1.ii) k|n ∧ k < m Widerspruch ! □

Nun setzte man m = p_{1} und r, so daß n = p_{1}r. Es ist nun 1 < r < n und man fahre fort mit der gleichen Überlegung für r. Es liefert wieder eine Zerlegung von n der Art, daß n = p_{1}p_{2}s. Das Verfahren bricht nach endlich vielen Schritten ab, da es zwischen 1 und n nur endlich viele Zahlen gibt. Es liefert nun die Zerlegung :

n = p_{1}p_{2} … p_{i}

wobei p_{1} ≤ p_{2} ≤ … ≤ p_{i} oder aber die sogenannte kanonische Zerlegung

n = p_{1}^{a_{p_{1}}}p_{2}^{a_{p_{2}}} … p_{j}^{a_{p_{j}}}

wobei a_{p_{l}} ∈ ℕ, p_{1} < p_{2} < … < p_{j}.

Beweis (Eindeutigkeit nach Zermelo-Hasse-Lindemann). Angenommen es gibt eine ganze Zahl mit zwei gleichen Zerlegungen. Sei N nun die kleinste solche Zahl mit den kanonischen Zerlegungen :

N = p_{1}p_{2} … p_{i} = q_{1}q_{2} … q_{l}

Nun gilt aber ∀p, q sind paarweise verschieden. Angenommen es gelte nicht, dann gebe es eine ganze Zahl, die die Gleichung teilen würde, aber N als minimal angenommen.

O.b.d.A. Sei nun

p_{1} ≤ p_{2} ≤ … ≤ p_{i} ; q_{1} ≤ q_{2} ≤ … ≤ q_{l}

ferner p_{1} < q_{1}. Man bilde eine neue Zahl

P = p_{1}q_{2} … q_{l}

Es gilt nun p_{1}|P ∧ p_{1}|N. Nach 1.1.iv). ist p_{1}|(N − P). Demnach gilt:

N − P = p_{1}t_{1} … t_{h},

wobei t_{i} prim mit i ∈ {1 … h} Da N − P = (q_{1} − p_{1})q_{2} … q_{l} > 0 existiert eine Primfaktorzerlegung q_{1} − p_{1} = r_{1}r_{2} … r_{t} so daß:

N − P = r_{1}r_{2} … r_{t}q_{2} … q_{l}

also eine zweite Darstellung von N − P als Primzahlenprodukt, ferner ist p_{1} ∤ (q_{1} − p_{1}) also ist p_{1} ≠ r_{i}, i ∈ {1 … t} Damit ist es tatsächlich eine andere Zerlegung von N − P, denn genau eine enhält die Zahl p_{1}. Aber 0 < N − P < N und N als die kleinste angenommen. Widerspruch! □

Satz 1.4 Es gibt unendlich viele Primzahlen. Beweis (Euklid). Angenommen es gebe endlich viele Primzahlen, dann auch eine größte p. Man bilde eine Zahl q mit

q = 2 · 3 · 5 … p

also eine, die alle Primzahlen bis p als Faktoren enthlt. Nun bilde man

q + 1 = 2 · 3 · 5 … p + 1

q + 1 ist aber eintweder eine Primzahl q + 1 > p oder, falls (q+1) zusammengesetzt existiert nach 1.3 eine Primzahl r > p, mit r|(q + 1). Eine Zerlegung mit r ≤ p ist nicht möglich, denn sonst wäre r|(q + 1) mit r ≤ p nach 1.1.iv) r|1 □.

Beweis (Euler). Sei u = \frac{1}{p}, p ∈ P Dann gilt zunächst:

\frac{1}{1 − u} = lim_{m→∞} \frac{1 − u^{m+1}}{1 − u} = lim_{m→∞} 1 + u + u^{2} + … + u^{m}

mit P als einer endlichem Primzahlenmenge. Multipliziert man nun über alle p ∈ P so eintsteht der Ausdruck :

∏_{p∈P}(1 − \frac{1}{p})^{−1} = ∏_{p∈P} ∑_{k=0}^{∞} \frac{1}{p^{k}} = ∑_{n∈N} \frac{1}{n}

mit N (P) = {n ∈ ℕ : p|n ⟹ p ∈ P} ∪ { 1 }

Zu beliebigen x ≥ 2 wählt man füer P die Menge aller Primzahlen p ≤ x. Aus 1.1.i). und 1.3 folgt unmittelbar, daß {1, 2, … [x]} ⊂ N (P).

∏_{p≤x}(1 − \frac{1}{p})^{−1} = ∑_{n≤x} \frac{1}{n} + ∑_{{n>x \atop p|n⟹p≤x}} \frac{1}{n}

und schließlich mit dem infinitesimalen Übergang:

∏_{p≤x}(1 − \frac{1}{p})^{−1} ≥ ∑_{n≤x} \frac{1}{n} > ∫_{1}^{x} \frac{dξ}{ξ} = log x

Da die Logarithmusfunktion divergiert, gilt es nach dem Minorantenkriterium auch für das Produkt.

Lemma 1.5 Sei 0 ≤ u < 1 Dann gilt :

log(\frac{1}{1 − u}) = ∑_{k=1}^{∞} \frac{u^{k}}{k}

Speziell gilt für u = \frac{1}{p} :

Satz 1.6 Für x ≥ 2 gilt :

∑_{p≤x} \frac{1}{p} > log log x − \frac{1}{2}

insbesondere ist ∑_{p≤x} \frac{1}{p} divergent. Beweis :

∑_{p≤x} log(1 − \frac{1}{p})^{−1} = ∑_{p≤x} ∑_{k=1}^{∞} \frac{1}{kp^{k}}

= ∑_{p≤x} \frac{1}{p} + ∑_{p≤x} ∑_{k=2}^{∞} \frac{1}{kp^{k}}

≤ ∑_{p≤x} \frac{1}{p} + \frac{1}{2} ∑_{p≤x} ∑_{k=2}^{∞} \frac{1}{p^{k}}

= ∑_{p≤x} \frac{1}{p} + \frac{1}{2} ∑_{p≤x} (\frac{1}{p^{2}} ∑_{k=0}^{∞} \frac{1}{p^{k}} )

Die geometrische Reihe konvergiert nun, da |\frac{1}{p}| < 1, so daß gilt

= ∑_{p≤x} \frac{1}{p} + \frac{1}{2} ∑_{p≤x} \frac{1}{p^{2}} \frac{1}{(1 − \frac{1}{p})}

= ∑_{p≤x} \frac{1}{p} + \frac{1}{2} ∑_{p≤x} \frac{1}{p(p − 1)}

< ∑_{p≤x} \frac{1}{p} + \frac{1}{2} ∑_{m=2}^{∞} \frac{1}{m(m − 1)} = \frac{1}{2}

= ∑_{p≤x} \frac{1}{p} + \frac{1}{2} ∑_{m=2}^{∞} (\frac{1}{m − 1} − \frac{1}{m}) = ∑_{p≤x} \frac{1}{p} + \frac{1}{2}

Verbindet man nun die beiden Ungleichungen, so gilt :

∑_{p≤x} \frac{1}{p} > log ∏_{p≤x}(1 − \frac{1}{p})^{−1} − \frac{1}{2} > log log x − \frac{1}{2}

□

Satz 1.7 Es existieren beliebig lange Ketten nicht primer Zahlen. Beweis: Man betrachte die Zahlen

n! + 2, n! + 3, …, n! + n

Offensichtlich sind diese nicht prim, da jede dieser Zahlen der Form n!+k ist, wobei k = 2 … n Da n! + k := 1 · 2 . . . · k · . . . n + k. Also ist k|(n! + k) Für hinreichend große n werden diese Ketten unendlich lang. □

Definition 1.8 π(x) := #{p ≤ x|p ∈ P}

Satz 1.9 Für π(x) gilt:

∏_{p≤x} ((1 − \frac{1}{p})^{−1}) − 1 ≤ π(x)

Beweis : Man ersätze zunchst alle Primzahlen durch die laufenden natürlichen Zahlen.

∏_{p≤x}(1 − \frac{1}{p})^{−1} ≤ ∏_{k=2}^{π(x)+1}(1 − \frac{1}{k})^{−1} = \frac{2 · 3 · . . . · (π(x) + 1)}{1 · 2 · . . . · (π(x))} = π(x) + 1

□

Quellen^{1} :

• J.Brüdern; Einführung in die analytische Zahlentheorie

• K.Chandrasekharan; Einführung in die analytische Zahlentheorie • K.Prachar; Primzahlenverteilung

• R.Remmert, P.Ullrich; Elementare Zahlentheorie

• A.Lautbecher, Zahlentheorie

• I.Peterson, Mathematische Expeditionen

1Scriptum \begin{matrix}c \\ ◯ \end{matrix}Markus Struzyna, Bonn 1998