Fundamentalsatz der Arithmetik

Der Fundamentalsatz der Arithmetik sagt uns, dass sich jede natürliche Zahl größer als 1 eindeutig als Produkt von Primzahlen schreiben lässt. Zum Beispiel lässt sich die Zahl 15 als Produkt zweier Primzahlen 3 · 5 schreiben, die Zahl 30 als Produkt dreier Primzahlen 2 · 3 · 5 und etwa die Zahl 16 als Produkt von vier Primzahlen 2 · 2 · 2 · 2. Ein solches Produkt nennen wir Primfaktorzerlegung. Wir sagen also, dass die Primfaktorzerlegung der Zahl 10 gleich 2 · 5 ist.

Die einfachste Primfaktorzerlegung haben die Primzahlen selbst, denn diese müssen wir nicht weiter zerlegen. Die Primfaktorzerlegung der Zahl 7 ist schlicht 7.

Berechne die Primfaktorzerlegung

Was uns der Fundamentalsatz der Arithmetik sagt

Der Fundamentalsatz der Arithmetik, manchmal auch Hauptsatz der Arithmetik genannt, sagt uns also zwei Dinge:

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

Beweisen wir, dass es wirklich so ist.

Beweis der Existenz

Zuerst beweisen wir, dass es für jede natürliche Zahl größer als 1 tatsächlich mindestens eine Primfaktorzerlegung gibt. Dazu verwenden wir die vollständige Induktion. Der Induktionsanfang besteht darin, dass die kleinste natürliche Zahl, die größer als 1 ist, nämlich die Zahl 2, eine Primzahl ist.

Nun zeigen wir: Wenn wir schon eine Folge von Zahlen 2, …, n haben, für die sich eine Primfaktorzerlegung finden lässt, dann existiert auch für die Zahl n + 1 eine Primfaktorzerlegung, wenn wir sie zu dieser Folge hinzufügen. Zuerst zeigen wir das an einem Beispiel.

Am Anfang ist unsere Folge 2, …, n etwas verkümmert, denn sie enthält nur eine einzige Zahl, die Zahl 2. Wir sagen: Wenn wir zu dieser Folge die Zahl n + 1, also die Zahl 3, hinzufügen, dann existiert für diese Zahl eine Primfaktorzerlegung. Da die Zahl 3 eine Primzahl ist, existiert für sie natürlich eine Primfaktorzerlegung – nämlich die Zahl 3.

Unsere Folge 2, …, n hat jetzt zwei Glieder: 2, 3. Wir fügen die Zahl 4 hinzu. Die Zahl 4 ist keine Primzahl, sie muss sich also als Produkt zweier anderer natürlicher Zahlen schreiben lassen, die größer als 1, aber kleiner als 4 sind. Alle diese Zahlen sind aber Teil unserer Folge! Und in dieser Folge stehen nur Zahlen, die eine Primfaktorzerlegung haben! Also muss auch die Zahl 4 eine Primfaktorzerlegung haben: 2 · 2.

Wenn wir zum allgemeinen Beweis zurückkehren, können wir schreiben: Die Zahl 2 ist eine Primzahl und hat also eine Primfaktorzerlegung. Nehmen wir nun an, dass sich jede Zahl der Folge 2, …, n in Primfaktoren zerlegen lässt – das ist unsere Induktionsvoraussetzung. Dann gilt: Die Zahl n + 1 ist entweder eine Primzahl und lässt sich damit trivial in Primzahlen zerlegen, oder sie ist eine zusammengesetzte Zahl. Für diese Zahl müssen dann Zahlen a, b existieren, sodass

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

wobei diese natürlichen Zahlen selbstverständlich kleiner als n + 1 und größer als 1 sein müssen:

$$\begin{array}{rcl}a>1,& & a<n+1\\ b>1,& & b<n+1\end{array}$$

Die Zahlen a, b müssen also Teil der Folge 2, …, n sein. Für jede Zahl dieser Folge existiert aber eine Primfaktorzerlegung (das ist unsere Induktionsvoraussetzung), das heißt, wir können schreiben

$$\begin{array}{rcl}a& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ b& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Dabei sind alle p_i und q_j Primzahlen, und p₁ · p₂ · … · p_i und q₁ · q₂ · … · q_j sind somit deren Primfaktorzerlegungen. Da wir aber gesagt haben, dass sich n + 1 als Produkt n + 1 = a · b schreiben lässt, gilt zugleich

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

Die Zahl n + 1 lässt sich also als Produkt der Primzahlen p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j schreiben, und somit hat auch die neu hinzugefügte Zahl n + 1 eine Primfaktorzerlegung. Daraus folgt, dass jede natürliche Zahl größer als 1 mindestens eine Primfaktorzerlegung hat.

Beweis der Eindeutigkeit

Zeigen wir nun, dass es für jede natürliche Zahl größer als 1 nicht mehrere Primfaktorzerlegungen gibt. Diesen Satz beweisen wir mit einem Widerspruchsbeweis. Wir nehmen an, dass der Satz nicht wahr ist, und nehmen also an, dass es eine natürliche Zahl n größer als 1 gibt, die zwei verschiedene Primfaktorzerlegungen hat:

$$\begin{array}{rcl}n& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ n& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Zugleich nehmen wir an, dass n von allen Zahlen, die mehrere Primfaktorzerlegungen haben, die kleinste ist. Das heißt, es gibt keine kleinere natürliche Zahl, die mehr als eine Primfaktorzerlegung hätte. Da q₁ eine der Primzahlen ist, die die Zahl n teilen, muss selbstverständlich auch gelten, dass q₁ die Zahl p₁ · p₂ · … · p_i teilt.

Weiter müssen wir das Lemma von Euklid verwenden. Es besagt: Wenn eine Primzahl p ein Produkt zweier ganzer Zahlen a · b teilt, dann teilt p auch mindestens eine der Zahlen a oder b. Zum Beispiel: Die Primzahl 3 teilt die Zahl 84. Die Zahl 84 können wir als Produkt der Zahlen 12 · 7 schreiben. Das Lemma von Euklid sagt, dass die Primzahl 3 mindestens eine der Zahlen 12 oder 7 teilt – in diesem Fall teilt sie die Zahl 12.

Mit diesem Lemma können wir sagen: Wenn q₁ das Produkt p₁ · p₂ · … · p_i teilt, dann muss es auch mindestens eine der Zahlen p₁, p₂, …, p_i teilen. Wir können – ohne Beschränkung der Allgemeinheit – annehmen, dass q₁ die Zahl p₁ teilt. Nun ist aber auch p₁ eine Primzahl. Wann kann eine Primzahl eine andere Primzahl teilen? Zum Beispiel: Welche Primzahl ist durch die Primzahl 7 teilbar? Wieder nur die Primzahl 7. Sie kann keine andere Primzahl teilen, denn dann wäre es keine Primzahl. Es muss also p₁ = q₁ gelten.

Das bedeutet, dass in beiden Primfaktorzerlegungen eine Primzahl vorkommt, die gleich ist: die Primzahl p₁ bzw. q₁. Teilen wir beide Gleichungen durch p₁ bzw. q₁:

$$\begin{array}{rcl}\frac{n}{p_1}& =& \frac{p_1\cdot p_2\cdot \dots \cdot p_i}{p_1}\\ \frac{n}{q_1}& =& \frac{q_1\cdot q_2\cdot \dots \cdot q_j}{q_1}\end{array}$$

Da p₁ = q₁ gilt, erhalten wir auf der linken Seite dieselbe Zahl, bezeichnen wir sie etwa mit m. Es gilt also

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

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

$$\begin{array}{rcl}m& =& p_2\cdot p_3\cdot \dots \cdot p_i\\ m& =& q_2\cdot q_3\cdot \dots \cdot q_j\end{array}$$

Die Zahl m ist bestimmt eine natürliche Zahl, die kleiner ist als die Zahl n, denn die Zahl m ist dadurch entstanden, dass wir n durch einen seiner Primfaktoren geteilt haben. Auf der rechten Seite der Gleichungen haben wir aber in beiden Fällen eine Primfaktorzerlegung der Zahl m. Wir haben also eine andere Zahl m konstruiert, die kleiner ist als die Zahl n und die ebenfalls zwei verschiedene Primfaktorzerlegungen hat. Das steht aber im Widerspruch zu unserer Annahme, dass n die kleinste Zahl ist, die mehr als eine Primfaktorzerlegung hat.

Die einzige Erklärung ist also, dass es keine „kleinste Zahl mit mehr als einer Primfaktorzerlegung“ gibt. Und dass es keine „kleinste Zahl mit mehr als einer Primfaktorzerlegung“ gibt, bedeutet, dass es überhaupt keine Zahl mit mehreren Primfaktorzerlegungen gibt – jede ganze Zahl größer als eins hat also genau eine eindeutige Primfaktorzerlegung.