Teilbarkeit und PrimzahlenPrimzahlen

Bei der Berechnung der Teilerpaare einer Zahl kann es vorkommen, dass die Zahl außer dem ersten Paar keine anderen Teiler mehr hat. Ein Beispiel dafür ist 13 - seine einzigen Teiler sind 1 und 13 selbst. Diese besonderen Zahlen werden als Primzahlen bezeichnet. Sie können nicht in Produkte mit kleineren Zahlen zerlegt werden, was sie gewissermaßen zu “Atomen von Zahlen” macht.

Beachte, dass 1 selbst keine Primzahl ist, so dass die ersten Primzahlen 2, 3, 5, 7, 11, 13,.... sind.

Jede Zahl, die keine Primzahl ist, kann als Produkt von Primzahlen geschrieben werden: Wir teilen sie einfach in mehrere Teile, bis alle Faktoren prim sind. Zum Beispiel,

Jetzt sind 2, 3 und 7 Primzahlen und können nicht weiter unterteilt werden. Das Produkt 2 × 2 × 2 × 3 × 3 × 7 wird als die Primfaktorzerlegung von 84 bezeichnet, und 2, 3 und 7 sind seine Primfaktoren. Beachte, dass einige Primzahlen, wie in diesem Fall 2, in einer Primfaktorzerlegung mehrfach auftreten können.

Jede ganze Zahl hat eine Primfaktorzerlegung und keine zwei ganzen Zahlen haben die gleiche Primfaktorzerlegung. Außerdem gibt es nur eine einzige Möglichkeit, eine beliebige Zahl als Produkt von Primzahlen zu schreiben - es sei denn, wir zählen unterschiedliche Anordnungen der Primzahlen. Das wird als der Fundamentalsatz der Arithmetik (FdA) bezeichnet.

Die Anwendung des FdA kann viele Probleme in der Mathematik viel einfacher machen: Wir teilen Zahlen in ihre Primfaktoren auf, dann lösen wir das Problem für die einzelnen Primzahlen, was oft viel einfacher sein kann, kombinieren zum Schluss diese Ergebnisse und lösen so das anfängliche Problem.

Das Sieb des Eratosthenes

Es stellte sich heraus, dass es ziemlich schwierig war, festzustellen, ob eine Zahl eine Primzahl ist: Man musste immer alle ihre Primfaktoren finden, was mit zunehmender Größe der Zahlen immer schwieriger wird. Stattdessen entwickelte der griechische Mathematiker Eratosthenes von Kyrene einen einfachen Algorithmus, um alle Primzahlen bis 100 zu finden: das Sieb des Eratosthenes.

Durch Abzählen sehen wir, dass es insgesamt Primzahlen gibt, die kleiner als 100 sind.

Wie viele Primzahlen gibt es?

1. Angenommen, es gäbe nur endlich viele Primzahlen.
   P, P, P, P, P
2. Wir wollen nun alle miteinander multiplizieren, um eine sehr große Zahl zu erhalten, die wir N nennen.
   N = P × P × P × P × P
3. Sehen wir uns jetzt N + 1 genauer an. Jede Primzahl, die N teilt, kann nicht auch N + 1 teilen. Und da alle Primzahlen, die wir bisher gefunden haben, N teilen, kann keine davon auch N + 1 teilen.
   P, P, P, P,

   P

   N
   P, P, P, P,

   P

   N + 1
4. Der Fundamentalsatz der Arithmetik besagt, dass N + 1, wie jede andere Zahl in Primfaktoren zerlegt werden kann. Entweder N + 1 ist selbst prim, oder es gibt eine zusätzliche neue Primzahl P’ die Teiler von N + 1 ist.
   P’ N + 1
5. In beiden Fällen hätten wir also eine neue Primzahl gefunden, die nicht in unserer ursprünglichen Liste enthalten ist - aber wir hatten ja angenommen, dass alle Primzahlen in dieser Liste sind.
6. Offensichtlich ist da etwas schiefgelaufen! Aber da die Schritte 2-4 alle korrekt waren, ist die einzige mögliche Erklärung die, dass unsere anfängliche Annahme 1 falsch war. Das bedeutet, dass es tatsächlich unendlich viele Primzahlen geben muss.

Euklids Erklärung ist eines der ersten Beispiele in der Geschichte für einen formalen mathematischen Beweis - ein logisches Argument, das zeigt, dass eine Aussage definitiv wahr sein muss. Dieses Beispiel wird oft als Widerspruchsbeweis bezeichnet: Wir beginnen mit einer Annahme, leiten daraus etwas Unmögliches ab und wissen daher, dass unsere Annahme falsch gewesen sein muss.