1. Die Existenz einer Primfaktorzerlegung

In diesem Abschnitt zeigen wir:

Satz (Fundamentalsatz der Zahlentheorie)

Sei n ≥ 2. Dann gibt es eine eindeutige Darstellung der Form

n = p₁^e₁ · … · p_k^e_k

mit Primzahlen p₁ < … < p_k und Exponenten e₁, …, e_k ≥ 1.

Der Satz rechtfertigt die Anschauung, die Primzahlen als multiplikative Bausteine oder Atome der natürlichen Zahlen anzusehen. Jede natürliche Zahl n ≥ 2 hat einen eindeutigen Bauplan. Die Primzahlen bilden die Atome der Zahl.

Die Darstellung einer Zahl n wie im Satz nennen wir die kanonische Primfaktorzerlegung von n. Allgemein nennen wir jede Darstellung von n als Produkt von Primzahlen eine Primfaktorzerlegung von n. So sind zum Beispiel

60 = 2² · 3 · 5

60 = 3 · 5 · 2²

60 = 2 · 5 · 2 · 3

Primfaktorzerlegungen der Zahl 60. Die erste Zerlegung ist kanonisch. Die Zahl 60 hat vier multiplikative nicht weiter zerlegbare Bausteine, nämlich zwei Zweien, eine Drei und eine Fünf. Aufgrund der Kommutativität der Multiplikation können diese Bausteine in beliebiger Reihenfolge angeordnet werden.

Ein leeres Produkt mit Null Faktoren wird in der Mathematik als 1 definiert. Mit dieser Konvention besitzt auch die Zahl 1 eine eindeutige kanonische Primfaktorzerlegung, nämlich das leere Produkt. Dies entspricht dem Fall k = 0 im Fundamentalsatz. Bilden wir das Produkt zweier Zahlen, so vereinigen wir ihre Atome. Da n · 1 = n für alle n gilt, kommen bei der Multiplikation mit 1 keine Atome hinzu, d. h. die 1 hat keine Atome und ist in diesem Sinne leer.

Der Fundamentalsatz der Zahlentheorie ist ein Existenz- und Eindeutigkeitssatz: Er behauptet die Existenz eines Objekts und seine Eindeutigkeit. Entsprechend zeigen wir den Satz in zwei Teilen. Zuerst betrachten wir die Frage der Existenz einer Primfaktorzerlegung, danach die Frage der Eindeutigkeit. Die Reihenfolge ist beliebig, wir könnten auch zuerst die Eindeutigkeit zeigen. Wir beginnen mit der Existenz, da diese deutlich einfacher zu beweisen ist.

Satz (Existenz einer Primfaktorzerlegung)

Sei n ≥ 2. Dann gibt es (nicht notwendig paarweise verschiedene) Primzahlen p₁, … p_k mit n = p₁ · … · p_k.

Ein kurzer informaler Beweis lautet:

Spalte wiederholt den kleinsten Primteiler ab.

Wir betrachten diesen Ansatz nun genauer. Den Ausgangspunkt bilden Primteiler.

Die Existenz eines Primteilers

Fast selbsterklärend ist:

Definition (Primteiler)

Sei n eine natürliche Zahl. Dann heißt jede Primzahl p, die ein Teiler von n ist, ein Primteiler von n.

Wir hatten schon verwendet:

Satz (Existenz eines Primteilers)

Sei n ≥ 2 eine natürliche Zahl. Dann besitzt n einen Primteiler.

Wir geben zur Illustration noch einmal verschiedene Beweise dieses Satzes.

Beweis durch schrittweise Überprüfung auf Teilbarkeit

Wir überprüfen die Zahlen

2, 3, 4, 5, 6, …, n

der Reihe nach auf die Eigenschaft, ob sie n teilen. Da n selbst ein Teiler von n ist, finden wir eine erste Zahl p ≤ n, die n teilt. Dann ist p ein Teiler von n und zudem eine Primzahl. Denn sei d ≥ 2 ein Teiler von p. Da d ein Teiler von p und weiter p ein Teiler von n ist, ist d ein Teiler von n (Transitivität der Teilbarkeit). Nach minimaler Wahl von p ist also d = p. Dies zeigt, dass p eine Primzahl ist.

Das „schrittweise Überprüfen bis zum ersten Fund“ können wir auch mit Hilfe des Prinzips von kleinsten Element formulieren:

Beweis durch Anwendung des Prinzips vom kleinsten Element

Wir setzen

A = { d | 2 ≤ d ≤ n und d ist ein Teiler von n }.

Wegen n  ∈  A ist A nichtleer. Also besitzt A ein kleinstes Element p (Prinzip vom kleinsten Element). Wie im ersten Beweis folgt, dass p ein Primteiler von n ist.

Sehr klar ist wie immer auch ein induktiver Beweis. In der Zahlentheorie wird oft die starke Induktion verwendet, bei eine Eigenschaft ℰ(n) mit Hilfe der Annahme der Gültigkeit von ℰ(m) für alle m < n bewiesen wird, nicht nur mit Hilfe der Gültigkeit von ℰ(n − 1). Bei dieser Form kann ein Induktionsanfang entfallen. Er wird im Induktionsschritt automatisch mit erfasst.

Beweis durch starke Induktion

Wir zeigen die Aussage durch starke Induktion nach n ≥ 2.

Induktionssschritt n

Ist n eine Primzahl, so ist n ein Primteiler von n. Andernfalls gibt es d, k mit 2 ≤ d, k < n und n = d k. Wegen 2 ≤ d < n besitzt d nach Induktionsvoraussetzung einen Primteiler p. Nach Transitivität der Teilbarkeit ist p ein Primteiler von n.

Nach diesen Vorbereitungen können wir uns dem Existenzsatz zuwenden.

Die Existenz einer Primfaktorzerlegung

Satz (Existenz einer Primfaktorzerlegung)

Sei n ≥ 2. Dann gibt es (nicht notwendig paarweise verschiedene) Primzahlen p₁, … p_k mit n = p₁ · … · p_k.

Auch hier geben wir verschiedene Beweise. Unser erster Beweis ist eine direkte Umsetzung unserer Grundidee:

Beweis durch wiederholte Abspaltung von Primteilern

Sei p₁ der kleinste Primteiler von n, und sei n₁ derart, dass n = p₁ n₁. Dann gilt n₁ < n. Ist n₁ = 1, so sind wir fertig. Ist n₁ ≥ 2, so sei p₂ der kleinste Primteiler von n₁, und es sei n₂ derart, dass n₁ = p₂ n₂. Dann gilt n₂ < n₁ und

n = p₁ n₁ = p₁ p₂ n₂.

Ist n₂ = 1, so sind wir fertig. Ist n₂ ≥ 2, so sei p₃ der kleinste Primteiler von n₂, und es sei n₃ derart, dass n₂ = p₃ n₃. Dann gilt n₃ < n₂ und

n = p₁ p₂ p₃ n₃.

Wegen n > n₁ > n₂ > … ≥ 1 erhalten wir nach endlich vielen Schritten eine Zahl n_k + 1 mit n_k = 1. Damit ergibt sich die Primfaktorzerlegung

n = p₁ … p_k.

Der Beweis verwendet das Prinzip des unendlichen Abstiegs: Es gibt keine unendliche Folge n₁, n₂, n₃, … in den natürlichen Zahlen mit

n₁ > n₂ > n₃ > …

Dieses Prinzip ist wie das Prinzip vom kleinsten Element eine (logische äquivalente) Variante der starken Induktion. Induktiv notiert lautet der Beweis:

Beweis durch starke Induktion

Wir zeigen die Aussage durch starke Induktion nach n ≥ 2.

Induktionssschritt n

Ist n eine Primzahl, so ist n eine Primfaktorzerlegung von n. Andernfalls sei p der kleinste Primteiler von n, und es sei n₁ derart, dass n = p n₁. Dann gilt 2 ≤ n₁ < n. Nach Induktionsvoraussetzung gibt es eine Primfaktorzerlegung

n₁ = p₁ … p_k

von n₁. Dann ist aber

n = p p₁ … p_k

eine Primfaktorzerlegung von n.

Beide Beweise liefern bei dieselbe Primfaktorzerlegung n = p₁ … p_k. Nach Konstruktion gilt p₁ ≤ … ≤ p_k.

Folgende Variante des induktiven Beweises benötigt die Existenz eines Primteilers nicht (sie wird mit bewiesen). Wir nutzen beide Faktoren einer Zerlegung n = d k und erhalten eine Primfaktorzerlegung von n durch Zusammensetzen von Primfaktorzerlegungen der Faktoren:

Beweis durch starke Induktion, II

Wir zeigen die Aussage durch starke Induktion nach n ≥ 2.

Induktionssschritt n

Ist n eine Primzahl, so ist n eine Primfaktorzerlegung von n. Andernfalls existieren d, k mit 2 ≤ d, k < n und n = d k. Nach Induktionsvoraussetzung gibt es Primfaktorzerlegungen

d = p₁ … p_k, k = q₁ … q_m

von d und k. Wegen n = d k ist dann

n = p₁ … p_k q₁ … q_m

eine Primfaktorzerlegung von n.

Explizit notieren wir noch:

Satz (Existenz einer Primfaktorzerlegung mit vorgegebenem Faktor)

Sei n ≥ 2. Weiter sei p ein Primteiler von n. Dann gibt es eine Primfaktorzerlegung von n, in der p vorkommt.

Zum Beweis müssen wir nur beobachten, dass wir unsere Konstruktion einer Primfaktorzerlegung nicht nur mit dem kleinsten, sondern mit einem beliebigen Primfaktor starten können. Innerhalb einer Induktion können wir eine Primfaktorzerlegung von n/p betrachten und dann p an diese Zerlegung anfügen.

Primzahlen als Atome: Farbdarstellung der Primfaktorzerlegungen der Zahlen von 2 bis 80. Gleiche Farben entsprechen gleichen Primzahlen.