Lieber Erdling,
Rudi ist gerade gar nicht gut gelaunt. Er hatte seine Primzahlsammlung an einen Freund ausgeliehen und nun hat er sie wiederbekommen, aber die Primzahlen sind total durcheinander! Nun muss er sie ganz mühsam wieder in die richtige Reihenfolge bringen.
Wie?! Du weißt nicht, was eine Primzahl ist?! Ach komm! Das wusste Rudi schon im Kindergarten! Okay, vielleicht geht man ja auf der Erde keine gefühlte Ewigkeit in den Kindergarten und kann da gar nicht soviel lernen, wie man gerne möchte. Na gut, dann erzähle ich es Dir eben jetzt! Eine Primzahl ist eine natürliche Zahl (also 1, 2, 3, …), die genau 2 Teiler hat: 1 und sich selbst. Die 1 ist also keine Primzahl, da sie nur einen Teiler hat. Die 2 und die 3 sind Primzahlen.
Die 4 ist keine Primzahl (sondern eine zusammengesetzte Zahl), da sie sich neben 1 und 4 auch durch 2 teilen lässt. Genauso wie 6, 8, 10 und jede andere gerade Zahl größer als 2. Die 2 ist also die einzige gerade Primzahl! Frag doch mal Deine Eltern, ob die das wissen!
Wenn Rudi mit dem Sortieren seines Primzahlalbums fertig ist, wird es darin also folgendermaßen losgehen:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, …
Jaja, ich weiß, was Deine nächste Frage ist. Taugen Primzahlen auch noch zu etwas anderem als zum Sammeln oder Eltern beeindrucken? Primzahlen sind doch bestimmt wieder nur so eine mathematische Spielerei, aber in der Praxis braucht das doch niemand. Pah! Da irrst Du Dich aber gewaltig! Auf Deinem Planeten werden Passwörter und sonstige wichtige Daten zum Schutz verschlüsselt, damit niemand sie lesen kann, der das nicht darf. Zum Beispiel wird so Dein gespartes Geld bei Banken geschützt. Diese Daten-Verschlüsselungen benutzen dabei gigantisch große Primzahlen! Und sie nutzen aus, dass es scheinbar noch keinem Erdling gelungen ist herauszufinden, wie man gaaanz große Zahlen als Produkt von Primzahlen schreibt.
Lass uns dieses sogenannte Faktorisierungsproblem mal genauer anschauen. Als erstes überzeuge ich Dich mal davon, dass sich jede natürliche Zahl als Produkt von Primzahlen schreiben lässt, wie zum Beispiel 28 = 2×2×7.
Wir fangen einfach an: Ist die Zahl selbst eine Primzahl, dann ist dieses Produkt kein wirkliches Produkt, wie Du es kennst. Es hat nur einen Faktor, wie in 7 = 7. Na gut, lassen wir uns davon mal nicht irritieren.
Falls die Zahl, wie zum Beispiel die 28, keine Primzahl ist, dann hat sie einen echten Teiler, der weder 1 oder die Zahl selbst ist. Sie lässt sich also als Produkt zweier echt kleinerer natürlicher Zahlen darstellen, zum Beispiel als 28 = 4×7. Diese beiden Faktoren, 4 und 7, sind nun entweder Primzahlen oder sie lassen sich ebenfalls als Produkt noch kleinerer natürlicher Zahlen darstellen. 7 ist eine Primzahl, aber 4 = 2×2. Damit ist also 28 = 2×2×7. Alle drei Faktoren sind Primzahlen und wir sind fertig.
Auf diese Weise kann man jede natürliche Zahl größer als 1 als Produkt von Primzahlen darstellen, da die einzelnen Faktoren in jedem Schritt immer kleiner werden und die Faktoren sich damit irgendwann nicht mehr als Produkt zweier kleinerer natürlicher Zahlen darstellen lassen. Und noch toller: Bis auf die Reihenfolge der Primzahlfaktoren ist diese Produktdarstellung sogar eindeutig! Egal in welcher Reihenfolge wir unsere Zahl in immer kleinere Faktoren zerlegen! Die 28 hätten wir auch so zerlegen können:
28 = 14×2 = (2×7)×2 = 7×2×2
Wir erhalten die gleichen Primzahlen als Faktoren. Cool, was?!
Auch wenn das Faktorisieren bei der 28 so einfach aussieht, weiß selbst heutzutage kein Erdling, ob dieses Faktorisierungsproblem nun einfach oder schwierig ist! Für große Zahlen kann es jedenfalls kein Erdling schnell lösen. Ich könnte Dir die Antwort darauf zwar verraten, aber ich habe Rudi versprochen, dass ich sein Geheimnis nicht ausplaudere. Tut mir leid.
Aber Du kannst es ja mal selbst probieren: Es ist leicht zu sehen, dass 21 (neben den trivialen Teilern 1 und 21) nur durch 3 und 7 teilbar ist, also ist 21 = 3×7. Ein wenig schwieriger ist da schon 143 = 11×13 herauszubekommen. Aber was ist zum Beispiel mit 608057? Welche Teiler hat diese Zahl? Hah! Das ist schwierig, stimmt’s?! Okay, ich verrate es Dir: 608057 = 19×32003, wobei 19 und 32003 Primzahlen sind. Und nun stell Dir vor, dass die Verschlüsselungssysteme nicht solche winzig kleinen Zahlen wie 608057 verwenden, sondern Zahlen mit mehreren hundert Ziffern!!! Und diese Zahlen sind so konstruiert, dass sie nur zwei Primzahlen als Teiler haben, die beide ebenfalls mehrere hundert Ziffern haben! Ganz klar, dass diese beiden Faktoren noch immer kein Erdling so schnell finden kann. Naja, zumindest glaubt das so ziemlich jeder, dass das nicht so einfach ist. Puh! Bei so großen Zahlen schwirrt mir gleich der Kopf.
Also lass uns lieber mal über andere coole Dinge reden. Zum Beispiel, dass es unendlich viele Primzahlen gibt! Mittlerweile hast Du ja bestimmt keine Angst mehr vor dem Unendlichen, oder?! Gut! Dann lass uns mal schauen, wie wir diese Behauptung mathematisch sauber beweisen könnten. Oder zumindest so überzeugend, dass Du Deine Eltern noch ein zweites Mal verblüffen kannst.
Also, wie können wir beweisen, dass es unendlich viele Primzahlen gibt? Hmm, gute Frage. Da hilft uns ein kleiner Trick! Wir nehmen einfach mal in Gedanken an, das Gegenteil sei richtig. Unsere Gegenannahme ist also: „Es gibt nur endlich viele Primzahlen.“ Wenn wir jetzt herausfinden, dass diese Annahme zu etwas führt, das nicht stimmt, so muss unsere Gegenannahme falsch sein. Was wiederum heißt, dass unsere ursprüngliche Aussage „Es gibt unendlich viele Primzahlen.“ stimmt und unser Beweis ist komplett. (Dieser mathematische Beweisansatz nennt sich übrigens indirekter Beweis, da man die Aussage nicht direkt beweist, sondern den Umweg über die Gegenannahme geht. Diese Technik hatten wir übrigens schon beim Schubfach-Prinzip im letzten Brief verwendet.)
Na gut, nehmen wir also an, es gäbe nur endlich viele Primzahlen. Sagen wir, es seien k Stück, wobei k sicherlich eine ziemlich große Anzahl sein dürfte. Dann ziehen wir diesen Primzahlen jetzt der Reihe nach T-Shirts an, auf denen ihr Name beziehungsweise ihr Wert p1, p2 und so weiter bis pk steht. Und dann betrachten wir mal die natürliche Zahl
p = p1×p2×p3×…×pk+1
Was wissen wir über diese Zahl, außer dass sie unglaublich groß ist? Naja, als erstes sehen wir, dass wir p so konstruiert haben, dass p beim Teilen durch jede der Primzahlen p1, …, pk den Rest 1 lässt. (Siehst Du warum?) Außerdem ist p auch offenbar größer als jede der Primzahlen p1, …, pk. Nun gibt es zwei Möglichkeiten: (1) p ist auch eine Primzahl oder (2) p ist eben keine Primzahl. Jaja, ich weiß, das ist wirklich offensichtlich, dass eines von beiden stimmen muss. Wir wissen aber nicht, welcher dieser beiden Fälle nun gilt. Also müssen wir uns beide Fälle einzeln genauer anschauen:
- p ist eine Primzahl. Da p nach unserer Konstruktion größer als jede der Primzahlen p1, …, pk ist, ist dies eine Primzahl ohne T-Shirt (sprich, keine der uns bekannten Primzahlen) und das ist ein Widerspruch zu unserer Annahme, dass p1, …, pk die einzigen Primzahlen sind. Wir hätten ja eine weitere Primzahl konstruiert.
- p ist keine Primzahl. Dann lässt sich p als Produkt von Primzahlen darstellen. Allerdings kann keine der uns bekannten Primzahlen p1, …, pk in diesem Produkt vorkommen, denn p lässt beim Teilen durch jede dieser Primzahlen nach unserer Konstruktion den Rest 1, ist also durch keine der Primzahlen p1, …, pk teilbar. Also muss in diesem Produkt wieder eine Primzahl ohne T-Shirt vorkommen, die wir noch nicht kennen, und wir erhalten erneut einen Widerspruch zu unserer Annahme, dass p1, …, pk die einzigen Primzahlen sind.
Da dies die zwei einzigen Möglichkeiten für p waren (p ist Primzahl oder p ist es nicht), und da beide Möglichkeiten zu einem Widerspruch führen, kann unsere Gegenannahme, dass es nur die endlich vielen Primzahlen p1, …, pk gibt, nicht stimmen. Es muss also unendlich viele Primzahlen geben! q.e.d.
Puh, das war ganz schön kompliziert. Ich glaube, ich brauche erstmal eine Pause. Bis demnächst mal wieder!
Deine 3,7
