Primzahlen

Was eine Primzahl ist und warum die 1 keine ist, warum es unendlich viele gibt, warum jede Zahl genau eine Zerlegung in Primzahlen hat, und warum das Sieb des Eratosthenes erst beim Quadrat einer Primzahl zu streichen beginnt.

Die Primzahlen sind die Bausteine, aus denen sich alle anderen Zahlen durch Multiplizieren zusammensetzen. Euklid bewies um 300 v. Chr. in den Elementen, dass es unendlich viele gibt, und legte mit dem Lemma, das seinen Namen trägt, den Grund für die zweite Grundtatsache: dass jede Zahl auf genau eine Weise in Primzahlen zerfällt. Als erste vollständige Formulierung mit Beweis gilt die von Gauß 1801. Dieses Kapitel führt beide Beweise vor.

Definition

Eine Zahl $p \in \mathbb{N}$ heißt Primzahl, wenn $p \ge 2$ ist und $p$ keine Teiler außer $1$ und $p$ hat:

\begin{aligned} p \text{ prim} \;:\Longleftrightarrow\;& p \ge 2 \text{ und für alle } d \in \mathbb{N} \\ & \text{gilt } d \mid p \Rightarrow d = 1 \lor d = p. \end{aligned}

Eine Zahl $n \ge 2$ , die nicht prim ist, heißt zusammengesetzt.

Warum ist die 1 ausgeschlossen, obwohl sie ebenfalls nur durch 1 und sich selbst teilbar ist? Weil sonst die Zerlegung in Primzahlen nicht mehr eindeutig wäre: $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3$ . Das ist keine Entdeckung, sondern eine Festlegung, die sich bewährt hat. Bis ins frühe 20. Jahrhundert haben manche Mathematiker die 1 mitgezählt, und die Seite Die Ordnung der Primzahlen wirbt für eine andere Einteilung, in der die 1 neben 2 und 3 eine Sonderrolle spielt. Beides ist eine Frage der Definition, nicht der Wahrheit.

Jede Zahl hat einen Primteiler

Satz 1

Jede Zahl $n \ge 2$ hat einen Teiler, der eine Primzahl ist. Genauer: Der kleinste Teiler $d > 1$ von $n$ ist eine Primzahl.

Beweis

Die Menge der Teiler $d > 1$ von $n$ ist nicht leer, denn sie enthält $n$ . Sei $d$ ihr kleinstes Element. Hätte $d$ einen Teiler $e$ mit $1 < e < d$ , so wäre $e$ nach Kapitel 3, Satz 1 auch ein Teiler von $n$ , kleiner als $d$ . Das widerspricht der Wahl von $d$ . Also ist $d$ prim.

∎

Es gibt unendlich viele

Satz 2

Es gibt unendlich viele Primzahlen.

Beweis

Seien $p_1, p_2, \dots, p_k$ irgendwelche Primzahlen. Wir zeigen, dass es eine weitere gibt. Sei

N := p_1 \cdot p_2 \cdots p_k + 1.

Nach Satz 1 hat $N$ einen Primteiler $q$ . Wäre $q$ eine der Zahlen $p_i$ , so teilte $q$ das Produkt $p_1 \cdots p_k$ und die Zahl $N$ , nach Kapitel 3, Satz 1 also auch ihre Differenz 1. Das ist unmöglich. Also ist $q$ eine neue Primzahl. Keine endliche Liste enthält alle.

∎

So steht der Beweis bei Euklid (Elemente IX 20). Er sagt übrigens nicht, dass $N$ selbst prim ist: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ . Er sagt nur, dass $N$ einen Primteiler hat, der noch nicht auf der Liste steht. Die Lean-Fassung unten benutzt statt des Produkts die Fakultät $n! + 1$ und zeigt damit, dass es zu jeder Zahl $n$ eine größere Primzahl gibt.

Das Lemma von Euklid

Satz 3

Ist $p$ eine Primzahl und teilt $p$ ein Produkt $ab$ , so teilt $p$ einen der Faktoren:

p \mid ab \;\Longrightarrow\; p \mid a \;\lor\; p \mid b.

Beweis

Angenommen, $p \nmid a$ . Der Teiler $\gcd(p, a)$ von $p$ ist 1 oder $p$ , und $p$ ist ausgeschlossen, weil $p$ die Zahl $a$ nicht teilt. Also ist $\gcd(p, a) = 1$ , und nach Kapitel 3, Satz 4 gibt es ganze Zahlen $x, y$ mit $1 = px + ay$ . Multipliziert mit $b$ :

b = p\,(bx) + (ab)\,y.

Beide Summanden sind durch $p$ teilbar, also auch $b$ .

∎

Für zusammengesetzte Zahlen gilt das nicht: $6 \mid 4 \cdot 9$ , aber $6 \nmid 4$ und $6 \nmid 9$ . Das Lemma ist genau die Eigenschaft, die Primzahlen zu Bausteinen macht, und es wird in Kapitel 6 gebraucht, um zu zeigen, wie viele Teile eine Figur $\{n/k\}$ hat.

Die eindeutige Zerlegung

Satz 4

Jede Zahl $n \ge 2$ ist ein Produkt von Primzahlen, und diese Darstellung ist bis auf die Reihenfolge eindeutig.

Beweis

Existenz, durch Induktion: Angenommen, alle Zahlen von 2 bis $n - 1$ sind Produkte von Primzahlen. Ist $n$ prim, sind wir fertig. Sonst ist $n = ab$ mit $2 \le a, b < n$ , und $a$ und $b$ sind nach Annahme Produkte von Primzahlen, also auch $n$ .

Eindeutigkeit: Sei $p_1 \cdots p_r = q_1 \cdots q_s$ mit Primzahlen $p_i, q_j$ . Dann teilt $p_1$ das rechte Produkt, nach Satz 3, mehrfach angewandt, also eines der $q_j$ . Da $q_j$ prim ist, folgt $p_1 = q_j$ . Man kürzt beide Seiten durch $p_1$ und wiederholt den Schluss mit den übrigen Faktoren, bis keine mehr übrig sind.

∎

Man nennt Satz 4 den Fundamentalsatz der Arithmetik. Er ist der Grund, warum man die Primzahlen die Atome der Zahlen nennt. Ohne ihn könnte man aus der Zerlegung einer Zahl nichts sicher ablesen.

Das Sieb des Eratosthenes

Wie findet man alle Primzahlen bis zu einer Grenze? Eratosthenes von Kyrene, um 240 v. Chr. Leiter der Bibliothek von Alexandria, schrieb die Zahlen auf und strich nacheinander die Vielfachen jeder gefundenen Primzahl. Was übrig bleibt, ist prim. Ein Satz zeigt, warum man dabei viel Arbeit sparen kann.

Satz 5

Ist $n \ge 2$ zusammengesetzt, so hat $n$ einen Primteiler $p \le \sqrt{n}$ , also mit $p^2 \le n$ .

Beweis

Sei $n = ab$ mit $2 \le a \le b$ . Dann ist $a^2 \le ab = n$ . Ein Primteiler $p$ von $a$ nach Satz 1 teilt auch $n$ , und es ist $p^2 \le a^2 \le n$ .

∎

Für das Sieb heißt das zweierlei. Erstens muss man die Vielfachen einer Primzahl $p$ erst ab $p^2$ streichen, denn jedes kleinere Vielfache hat einen kleineren Primteiler und ist schon gestrichen. Zweitens kann man aufhören, sobald $p^2$ die Grenze übersteigt. Für die Zahlen bis 100 genügen deshalb 2, 3, 5 und 7.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

Das Sieb bis 100. Jeder Knopfdruck nimmt die nächste Primzahl und streicht ihre Vielfachen ab ihrem Quadrat: 4, 9, 25, 49. Danach ist die Arbeit getan, denn 11² ist schon größer als 100.

Hier liegt der mathematische Kern einer Beobachtung, die auf dieser Website viele Seiten trägt: Nach dem Streichen der Vielfachen von 2 und 3 ist die erste Zahl, die das Sieb noch trifft, $25 = 5^2$ . Von 2 bis 24 sind deshalb alle Zahlen, die weder durch 2 noch durch 3 teilbar sind, prim (siehe Die Unordnung der Primzahlen). Das ist Satz 5 für die Primzahl 5, und mit dem nächsten Kapitel wird klar, warum diese Zahlen genau die Zwillingsplätze $6n \pm 1$ sind.

Vom Computer geprüft: der Beweis in Lean

IstPrim ist die Definition oben. primteiler ist Satz 1, bewiesen durch starke Induktion (Nat.strongRecOn): Ist $n$ nicht prim, hat es einen kleineren Teiler, und für den gilt die Aussage schon. fakt ist die Fakultät, teilt_fakt zeigt, dass jede Zahl von 1 bis $n$ die Zahl $n!$ teilt, und unendlich_viele ist Satz 2 mit $n! + 1$ statt des Produkts. lemma_von_euklid ist Satz 3. Den Schritt über den ggT nimmt Lean aus seiner Bibliothek, wo Kapitel 3, Satz 4 bereits bewiesen ist.

/-! Kapitel 4: Primzahlen -/

def IstPrim (n : Nat) : Prop :=
  2 ≤ n ∧ ∀ d, d ∣ n → d = 1 ∨ d = n

/-- Satz 1: Jede Zahl n ≥ 2 hat einen Primteiler. -/
theorem primteiler (n : Nat) (h : 2 ≤ n) :
    ∃ p, IstPrim p ∧ p ∣ n := by
  induction n using Nat.strongRecOn with
  | ind n ih =>
    by_cases hp : IstPrim n
    · exact ⟨n, hp, Nat.dvd_refl n⟩
    · -- n ist nicht prim: es gibt einen Teiler d mit 1 < d < n
      have : ∃ d, d ∣ n ∧ d ≠ 1 ∧ d ≠ n := by
        apply Classical.byContradiction
        intro hne
        apply hp
        refine ⟨h, fun d hd => ?_⟩
        apply Classical.byContradiction
        intro hd2
        apply hne
        exact ⟨d, hd, fun h1 => hd2 (Or.inl h1),
          fun h2 => hd2 (Or.inr h2)⟩
      obtain ⟨d, hd, hd1, hdn⟩ := this
      have hd0 : 0 < d := Nat.pos_of_dvd_of_pos hd (by omega)
      have hdle : d ≤ n := Nat.le_of_dvd (by omega) hd
      obtain ⟨p, hp, hpd⟩ := ih d (by omega) (by omega)
      exact ⟨p, hp, Nat.dvd_trans hpd hd⟩

/-- Die Fakultät n! = 1 · 2 · … · n -/
def fakt : Nat → Nat
  | 0 => 1
  | n + 1 => (n + 1) * fakt n

theorem fakt_pos (n : Nat) : 0 < fakt n := by
  induction n with
  | zero => decide
  | succ n ih =>
    simp only [fakt]
    exact Nat.mul_pos (by omega) ih

/-- Jede Zahl d von 1 bis n teilt n! -/
theorem teilt_fakt (d n : Nat) (h1 : 1 ≤ d) (h2 : d ≤ n) :
    d ∣ fakt n := by
  induction n with
  | zero => omega
  | succ n ih =>
    by_cases hd : d = n + 1
    · subst hd
      exact Nat.dvd_mul_right _ _
    · exact Nat.dvd_trans (ih (by omega)) (Nat.dvd_mul_left _ _)

/-- Satz 2 (Euklid): Zu jeder Zahl n gibt es eine
    größere Primzahl. -/
theorem unendlich_viele (n : Nat) : ∃ p, IstPrim p ∧ n < p := by
  have hf := fakt_pos n
  obtain ⟨p, hp, hpd⟩ := primteiler (fakt n + 1) (by omega)
  refine ⟨p, hp, ?_⟩
  apply Classical.byContradiction
  intro hle
  have hp2 := hp.1
  have hp1 : 1 ≤ p := by omega
  have h1 : p ∣ fakt n := teilt_fakt p n hp1 (by omega)
  have h2 : p ∣ 1 := (Nat.dvd_add_right h1).mp hpd
  have := Nat.le_of_dvd (by decide) h2
  have := hp.1
  omega

/-- Satz 3 (Lemma von Euklid): Teilt eine Primzahl ein
    Produkt, so teilt sie einen der Faktoren. Der Schritt
    „aus ggT(p, a) = 1 und p ∣ a · b folgt p ∣ b“ steht in
    Leans Bibliothek und ist dort bewiesen. -/
theorem lemma_von_euklid (p a b : Nat) (hp : IstPrim p) (h : p ∣ a * b) :
    p ∣ a ∨ p ∣ b := by
  by_cases ha : p ∣ a
  · exact Or.inl ha
  · right
    -- ggT(p, a) teilt p, ist also 1 oder p. Es ist nicht p,
    -- weil p die Zahl a nicht teilt.
    have hg : Nat.gcd p a = 1 := by
      rcases hp.2 (Nat.gcd p a) (Nat.gcd_dvd_left p a) with h1 | h2
      · exact h1
      · exfalso
        apply ha
        have := Nat.gcd_dvd_right p a
        rw [h2] at this
        exact this
    exact Nat.Coprime.dvd_of_dvd_mul_left hg h

Im Browser ausprobieren auf live.lean-lang.org ↗Wie man Lean liest

Quellen und Literatur

Quellen

Euklid, Elemente, um 300 v. Chr., Buch VII, 30 bis 32, und Buch IX, 20
Nikomachos von Gerasa, Einführung in die Arithmetik, um 100 n. Chr., Buch I, Kap. 13 (das Sieb des Eratosthenes)
Carl Friedrich Gauß, Disquisitiones arithmeticae, Leipzig 1801, Artikel 16

Zum Weiterlesen

G. H. Hardy und E. M. Wright, An Introduction to the Theory of Numbers, Oxford 1938, 6. Aufl. 2008