§ 5. Primzahlen

Jede ganze Zahl a besitzt die sog. trivialen oder unechten Teiler ±1 und ±a. Davon verschiedene Teiler von a heißen echt oder nichttrivial . Primzahlen sind Zahlen ohne echte Teiler, genauer

\underline{(5.1) DEF:} Eine natürliche Zahl p ∈ ℕ heißt Primzahl oder prim, wenn gilt:

P_{1}) p ≥ 2

P_{2}) 1 und p sind die einzigen positiven Teiler von p. IP bezeichne die Menge aller Primzahlen .

\underline{Beispiele:} \{2, 3, 5, 7, 11, 13\} ⊆ IP 1 ∉ IP , 4 ∉ IP , 6 ∉ IP , − 2 ∉ IP , − 3 ∉ IP , − 13 ∉ IP

\underline{(5.2) BEM:} a) 1 ist \underline{keine} Primzahl !!!

b) Eine natürliche Zahl p ≥ 2 ist genau dann eine Primzahl, wenn gilt

∀ t ∈ ℕ : t | p ⟹ t = 1 ∨ t = p .

c) Eine natürliche Zahl n ≥ 2 ist genau dann \underline{keine} Primzahl, wenn n einen echten Teiler besitzt, d.h. wenn es ein

t ∈ ℕ mit 1 < t < n und t | n

gibt. In dem Falle ist dann auch der zu t komplementäre Teiler s ein echter Teiler von n. Also

n ∈ ℕ, n ≥ 2 : n ∉ IP ⟺ es gibt s, t ∈ ℕ mit 1 < s, t < n und n = s · t .

d) Eine natürliche Zahl, die einen echten Teiler besitzt, heißt eine zusammengesetzte Zahl. Es gilt also

ℕ = {1} ∪ IP ∪ M ,

wobei M die Menge der zusammengesetzten natürlichen Zahlen bezeichnet.

e) 2 ist die einzige \underline{gerade} Primzahl, alle anderen Primzahlen sind ungerade.

f) Für n ∈ ℕ gilt : n prim ⟺ | T^{+}(n) | = 2 ⟺ | T (n) | = 4 .

\underline{(5.3) LEMMA:} Für a ∈ ℤ und p ∈ IP gilt:

a) ggT(a, p) ∈ {1, p}

b) ggT(a, p) = p ⟺ p | a

c) ggT(a, p) = 1 ⟺ p |̸ a.

\underline{(5.4) SATZ:} Für p ∈ ℕ , p ≥ 2 sind folgende Aussagen äquivalent:

a) p ist eine Primzahl

b) ∀ a, b ∈ ℤ : p | (a · b) ⟹ ( p | a ∨ p | b) .

\underline{(5.5) BEM:} Wir haben gesehen, daß Primzahlen zwei zueinander äquivalente Bedingungen erfüllen. Eine natürliche Zahl p ≥ 2 ist genau dann eine Primzahl, wenn

∀ t ∈ ℕ : t | p ⟹ t = 1 ∨ t = p

oder

∀ a, b ∈ ℤ : p | (a · b) ⟹ p | a ∨ p | b.

gilt. Im ersten Falle sagen wir, daß p unzerlegbar ist: p läßt sich nicht in ein Produkt echter Teiler zerlegen. Die zweite Eigenschaft wollen wir zur Unterscheidung die Primeigenschaft von p nennen. In späteren Verallgemeinerungen werden wir sehen, daß diese beiden Bedingungen nicht mehr übereinstimmen müssen.

\underline{(5.6) SATZ:} Sei n ∈ ℕ , n ≥ 2 . Dann gilt:

a) Es gibt unter allen Teilern von n, die > 1 sind, einen kleinsten Teiler p

b) Dieser kleinste Teiler p ist eine Primzahl, also ein Primteiler von n.

c) n läßt sich als ein Produkt von endlich vielen Primzahlen darstellen.

Verteilung der Primzahlen

Mit Hilfe des Satzes (5.6) können wir jetzt mit Ideen, die schon in den Elementen des Euklid zu finden sind, beweisen, daß es unendlich viele Primzahlen gibt. Wir werden später noch weitere Beweise für dieses Ergebnis kennenlernen.

\underline{(5.7) SATZ:} (Euklid)

Ist IP′ ⊆ IP eine \underline{endliche} Menge von Primzahlen, so gibt es eine Primzahl p , die nicht in IP′ liegt (d.h. IP \ IP′ ≠ ∅) .

\underline{(5.8) KOROLLAR:} Es gibt unendlich viele Primzahlen (I. Beweis) .

\underline{(5.9) KOROLLAR:} Ist (p_{k})_{k∈ℕ} die Folge der Primzahlen in ihrer natürlichen Reihenfolge, so gilt

p_{n+1} < p_{n}^{n} + 1 .

\underline{(5.10) KOROLLAR:} Ist (p_{k})_{k∈ℕ} die Folge der Primzahlen in ihrer natürlichen Reihenfolge, so gilt

p_{n} < 2^{2^{n}} .

\underline{(5.11) DEF:} Eine natürliche Zahl F_{n} (n ∈ ℕ_{0}) der Form F_{n} = 2^{2^{n}} + 1 heißt n–te Fermat’sche Zahl .

Die Fermat’schen Zahlen F_{0}, F_{1}, F_{2}, F_{3}, F_{4} sind Primzahlen, weitere Fermat’sche Primzahlen sind nicht bekannt.

Ungelöstes Problem: Gibt es unendlich viele Fermat’sche Primzahlen ???

\underline{(5.12) SATZ:} Für alle m, n ∈ ℕ_{0} mit m ≠ n gilt ggT(F_{m}, F_{n}) = 1 .

Chr.Nelius : Zahlentheorie (SS 2007) 17 \underline{(5.13) KOROLLAR:} Es gibt unendlich viele Primzahlen (II. Beweis) . \underline{(5.14) DEF:} Ein Zahlenpaar (p, p + 2) , bei dem sowohl p als auch p + 2 Primzahlen sind, heißt ein Primzahlzwilling . \underline{Beispiele:} für Primzahlzwillinge: (3, 5) , (5, 7) , (11, 13) , (17, 19) , (29, 31) , (q, q + 2) mit q = 242 206 083 · 2^{38 880} − 1 (q hat 11 713 Dezimalziffern) . Das letzte Beispiel wurde 1995 von Indlekofer/Jarai/Wassing hier in Paderborn gefunden und war damals der größte bekannte Primzahlzwilling (jetzt gibt es aber schon viel größere!). Ungelöstes Problem: Gibt es unendlich viele Primzahlzwillinge ??? \underline{(5.15) SATZ:} Zu jeder natürlichen Zahl n gibt es n aufeinanderfolgende zusammengesetzte Zahlen. \underline{(5.16) KOROLLAR:} Ist (p_{k})_{k∈ℕ} die Folge der Primzahlen in ihrer natürlichen Reihenfolge, so gibt es zu jedem n ∈ ℕ ein m ∈ ℕ mit

p_{m+1} − p_{m} ≥ n

\underline{(5.17) BEM:} a) Ist n ∈ ℕ , n ≥ 3 , so gibt es mindestens eine Primzahl p mit

n < p ≤ n! − 1 .

b) “Bertrand’sches Postulat” (1845) , bewiesen von Tschebyscheff Zu jeder natürlichen Zahl n gibt es eine Primzahl p mit

n < p ≤ 2n .

\underline{(5.18) SATZ:} Ist f ∈ ℤ[T] ein nichtkonstantes Polynom, so ist f(n) für unendlich viele n ∈ ℕ eine zusammengesetzte Zahl (d.h. keine Primzahl) . Fazit: Es gibt kein nichtkonstantes Polynom f ∈ ℤ[T] mit der Eigenschaft: f(n) ∈ IP für fast alle n ∈ ℕ. \underline{(5.19) LEMMA:}

a) Für jede ungerade Primzahl p ∈ IP gilt: p mod 4 = 1 oder p mod 4 = 3

b) Für jede Primzahl p ≥ 5 gilt: p mod 6 = 1 oder p mod 6 = 5 . (5.20) KOROLLAR:

a) Für jede ungerade Primzahl p ∈ IP gibt es ein k ∈ ℕ mit p = 4k ± 1 .

b) Für jede Primzahl p ≥ 5 gibt es ein l ∈ ℕ mit p = 6l ± 1 . \underline{(5.21) SATZ:} Es gibt unendlich viele Primzahlen der Form 4n + 3 (n ∈ ℕ) .

\underline{(5.22) SATZ:} Dirichlet (1837) Sei n ∈ ℕ. Sind a, b ∈ ℕ teilerfremd mit 0 < b < a, so gibt es in der “arithmetischen Progression” (an + b)_{n∈ℕ} unendlich viele Primzahlen.

Primzahltest:

\underline{(5.23) SATZ:} Für eine natürliche Zahl n ≥ 2 sind folgende Aussagen äquivalent:

a) n ist eine Primzahl

b) n besitzt keinen Teiler t ∈ ℕ mit 2 ≤ t ≤ ⌊\sqrt{n}⌋

c) n besitzt keinen Primteiler p mit p ≤ ⌊\sqrt{n}⌋.

(5.24) Ein einfacher Primzahltest Sei n ≥ 7 eine ungerade Zahl. (u_{k})_{k∈ℕ} sei eine streng monoton wachsende Folge ungerader natürlicher Zahlen, die alle ungeraden Primzahlen enthält. Dann gilt

n ∈ IP ⟺ ∀ k ∈ ℕ : u_{k} ≤ ⌊\sqrt{n}⌋ ⟹ u_{k} |̸ n .

\underline{(5.25) BEISPIELE:} Für die Folge (u_{k}) in (5.24) kann man wählen:

a) Die Folge aller ungeraden natürlichen Zahlen ≥ 3 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, …

b) 3 und dann die Zahlen 6k − 1, 6k + 1 (k ∈ ℕ)

3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, …

(Diese Folge enthält nach (5.20b) alle ungeraden Primzahlen)

c) Die Folge aller ungeraden Primzahlen in der natürlichen Reihenfolge 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, . . ..

Primzahllisten:

(5.26) Das Sieb des Eratosthenes Sei n ∈ ℕ. Es sollen alle Primzahlen ≤ n bestimmt werden. Sei U = (3, 5, 7, 9, 11, …) die Folge der ungeraden Zahlen ≤ n in der natürlichen Reihenfolge.

a) Streiche in U alle echten Vielfachen von 3 .

b) Ist a die nächste ungestrichene Zahl, so brich das Verfahren im Falle a > ⌊\sqrt{n}⌋ ab, ansonsten streiche die echten Vielfachen von a.

c) Setze das Verfahren fort, bis die nächste ungestrichene Zahl > ⌊\sqrt{n}⌋ ist. Es bleiben dann alle Primzahlen ≤ n übrig.