Der grundlegende Satz der Arithmetik

Der Fundamentalsatz der Arithmetik besagt, dass jede natürliche Zahl größer als 1 eindeutig in ein Produkt von Primzahlen zerlegt werden kann. Zum Beispiel kann die Zahl 15 in das Produkt von zwei Primzahlen 3 · 5, die Zahl 30 in das Produkt von drei Primzahlen 2 · 3 · 5 und die Zahl 16 in das Produkt von vier Primzahlen 2 · 2 · 2 · 2 zerlegt werden. Ein solches Produkt von Zahlen wird dann Primzahlzerlegung genannt. Wir sagen also, dass die Primzahlzerlegung der Zahl 10 2 · 5 ist.

Die Primzahlen selbst haben die einfachste Primzahlzerlegung, weil wir sie nicht weiter zerlegen müssen. Die Primzahlzerlegung von 7 ist einfach 7.

Berechnen Sie die Primzahlzerlegung

Was uns der Fundamentalsatz der Arithmetik sagt

Der Fundamentalsatz der Arithmetik, manchmal auch als Fundamentalsatz der Arithmetik bezeichnet, sagt uns also zwei Dinge:

• Für jede natürliche Zahl, die größer als 1 ist, können wir die Primzahlzerlegung finden,
• jede Zahl hat genau eine einzige Primzahlzerlegung.

Wir wollen nun beweisen, dass dies tatsächlich der Fall ist.

Beweis der Existenz

Zunächst beweisen wir, dass es für jede natürliche Zahl größer als 1 tatsächlich mindestens eine Primzahlzerlegung gibt. Wir verwenden dazu die mathematische Induktion. Der erste Schritt der mathematischen Induktion besteht darin zu sagen, dass die kleinste natürliche Zahl, die größer als 1 ist, also die Zahl 2, eine Primzahl ist.

Wir werden nun zeigen, dass, da wir eine Zahlenfolge 2, …, n haben, für die eine Primzahlzerlegung gefunden werden kann, wenn wir die Zahl n + 1 zu dieser Folge hinzufügen, es eine Primzahlzerlegung für diese neue Zahl gibt, die die Primzahlen der Folge 2, …, n verwendet. Lassen Sie uns dies zunächst an einem Beispiel zeigen.

Am Anfang ist unsere Folge 2, …, n ein wenig deformiert, weil sie nur eine Zahl enthält, die Zahl 2. Wir sagen, wenn wir die Zahl n + 1, also die Zahl 3, zu dieser Folge hinzufügen, gibt es eine Primzahlzerlegung für diese Zahl. Da die Zahl 3 eine Primzahl ist, gibt es natürlich auch eine Primzahlzerlegung für sie - es ist die Zahl 3.

Unsere Folge 2, …, n hat nun zwei Glieder: 2, 3 Fügen wir die Zahl 4 zu der Folge hinzu. Die Zahl 4 ist keine Primzahl, also muss sie sich in das Produkt zweier anderer natürlicher Zahlen zerlegen, die größer als 1, aber kleiner als 4 sind. Aber alle diese Zahlen sind Teil unserer Folge! Und doch sind nur Zahlen, die eine Primzahlzerlegung haben, in dieser Folge! Also muss auch die Zahl 4 eine Primzahlzerlegung haben: 2 · 2.

Um zum allgemeinen Beweis zurückzukehren, können wir schreiben, dass die Zahl 2 prim ist und daher eine Primzahlzerlegung hat. Nehmen wir nun an, dass jede Zahl in der Folge 2, …, n primzahlzerlegt werden kann - das ist unsere induktive Annahme. Dann ist entweder die Zahl n + 1 prim und kann somit trivial in Primzahlen zerlegt werden oder sie ist eine zusammengesetzte Zahl. Für diese Zahl muss es also solche Zahlen a, b geben, dass

$$n+1=a\cdot b$$

wobei es so sein muss, dass diese natürlichen Zahlen natürlich kleiner als n + 1 und größer als 1 sind:

$$\begin{eqnarray} a > 1,&\quad&a < n+1 \\ b > 1,&\quad&b < n+1 \\ \end{eqnarray}$$

Die Zahlen a, b müssen also Teil der Folge 2, …, n sein. Dabei gibt es aber für jede Zahl in dieser Folge eine Primzahlzerlegung (das ist unsere induktive Annahme), d.h. wir können schreiben

$$\begin{eqnarray} a&=&p_1\cdot p_2 \cdot \ldots \cdot p_i\\ b&=&q_1\cdot q_2 \cdot \ldots \cdot q_j\\ \end{eqnarray}$$

Wobei p_i und q_j alle Primzahlen sind und p₁ · p₂ · … · p_i und q₁ · q₂ · … · q_j somit ihre Primzahlzerlegungen sind. Da wir aber gesagt haben, dass n + 1 in das Produkt n + 1 = a · b zerlegbar ist, heißt das gleichzeitig

$$\begin{eqnarray} n+1&=&a\cdot b\\ &=&p_1\cdot p_2 \cdot \ldots \cdot p_i\cdot q_1\cdot q_2 \cdot \ldots \cdot q_j \end{eqnarray}$$

Die Zahl n + 1 ist also zerlegbar in das Produkt der Primzahlen p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, so dass die neu hinzugekommene Zahl n + 1 eine Primzahlzerlegung hat. Daraus folgt, dass jede natürliche Zahl größer als 1 mindestens eine Primzahlzerlegung hat.

Beweis der Eindeutigkeit

Wir wollen nun zeigen, dass es für jede natürliche Zahl größer als 1 keine weiteren Primzahlzerlegungen gibt. Wir beweisen diesen Satz mit Hilfe eines Widerspruchsbeweises. Wir gehen davon aus, dass der Satz nicht wahr ist und nehmen daher an, dass es eine natürliche Zahl n größer als 1 gibt, die zwei verschiedene Primzahlzerlegungen hat:

$$\begin{eqnarray} n&=&p_1\cdot p_2 \cdot \ldots \cdot p_i\\ n&=&q_1\cdot q_2 \cdot \ldots \cdot q_j \end{eqnarray}$$

Wir nehmen auch an, dass von allen Zahlen, die mehrere Primzahlzerlegungen haben, n die kleinste ist. Das heißt, es gibt keine kleinere natürliche Zahl, die mehr als eine Primzahlzerlegung hat. Da q₁ eine der Primzahlen ist, die n teilt, muss natürlich auch wahr sein, dass q₁ p₁ · p₂ · … · p_i teilt.

Als nächstes müssen wir das Euklidsche Lemma anwenden. Dieses besagt, dass wenn die Primzahl p das Produkt zweier ganzer Zahlen a · b teilt, dann teilt p auch mindestens eine der Zahlen a oder b. Zum Beispiel teilt die Primzahl 3 die Zahl 84. Wir können die Zahl 84 in das Produkt der Zahlen 12 · 7 zerlegen. Das Euklidsche Lemma besagt, dass die Primzahl 3 mindestens eine der Zahlen 12 oder 7 teilt - in diesem Fall also die Zahl 12.

Mit Hilfe dieses Lemmas können wir sagen, dass wenn q₁ p₁ · p₂ · … · p_i teilt, dann muss sie auch mindestens eine der Zahlen p₁, p₂, … p_j teilen. Es kann - ohne Verlust der Allgemeinheit - angenommen werden, dass q₁ die Zahl p₁ teilt. Nur, dass p₁ auch eine Primzahl ist. Wann kann eine Primzahl eine andere Primzahl teilen? Welche Primzahl ist zum Beispiel durch 7 teilbar? Auch hier gilt: nur die Primzahl 7. Sie kann keine andere Primzahl teilen, denn dann wäre sie keine Primzahl. Es muss also wahr sein, dass p₁ = q₁.

Das bedeutet, dass es in beiden Primzahlerweiterungen eine Primzahl gibt, die dieselbe ist: die Primzahl p₁ und q₁. Teilen wir beide Primzahlgleichungen durch p₁ bzw. q₁:

$$\begin{eqnarray} \frac{n}{p_1}&=&\frac{p_1\cdot p_2 \cdot \ldots \cdot p_i}{p_1}\\ \frac{n}{q_1}&=&\frac{q_1\cdot q_2 \cdot \ldots \cdot q_j}{q_1} \end{eqnarray}$$

Da p₁ = q₁ auf der linken Seite die gleiche Zahl ist, nennen wir sie zum Beispiel m.

$$m=\frac{n}{p_1}=\frac{n}{q_1}$$

Auf der rechten Seite kürzen wir die Brüche einfach ab:

$$\begin{eqnarray} m&=&p_2 \cdot p_3 \cdot \ldots \cdot p_i\\ m&=&q_2 \cdot q_3 \cdot \ldots \cdot q_j \end{eqnarray}$$

Die Zahl m ist definitiv eine natürliche Zahl, die kleiner ist als n, weil die Zahl m durch Division von n durch einen ihrer Primfaktoren gebildet wurde. Aber auf der rechten Seite der Gleichungen haben wir in beiden Fällen den Primfaktor von m. Wir konnten also eine andere Zahl m konstruieren, die kleiner ist als n und die ebenfalls zwei verschiedene Primzahlzerlegungen hat. Das widerspricht natürlich unserer Annahme, dass n die kleinste Zahl ist, die mehr als eine einzige Primzahlzerlegung hat.

Die einzige Erklärung ist also, dass es keine "kleinste Zahl mit mehr als einer Primzahlzerlegung" gibt. Und dass es keine "kleinste Zahl mit mehr als einer Primzahlzerlegung" gibt, bedeutet, dass es keine Zahl mit mehreren Primzahlzerlegungen gibt - also hat jede ganze Zahl größer als eins genau eine einzige Primzahlzerlegung.