Primzahlen verstehen – Vollständiger Leitfaden
Erfahren Sie, was Primzahlen sind, wie man sie erkennt, Primfaktorzerlegung, das Sieb des Eratosthenes und warum Primzahlen wichtig sind.
Was ist eine Primzahl?
Eine Primzahl ist eine natürliche Zahl größer als 1, die genau zwei verschiedene positive Teiler hat: 1 und sich selbst. Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23 und 29. Die Zahl 2 ist die einzige gerade Primzahl, weil jede andere gerade Zahl durch 2 teilbar ist. Die Zahl 1 gilt nicht als Primzahl, weil sie nur einen Teiler hat (sich selbst), und die Definition genau zwei erfordert. Primzahlen sind die fundamentalen Bausteine der Arithmetik und faszinieren Mathematiker seit über zweitausend Jahren wegen ihrer scheinbar unregelmäßigen Verteilung unter den natürlichen Zahlen.
Wie man testet, ob eine Zahl prim ist
Die einfachste Methode, um zu prüfen, ob eine Zahl n prim ist, ist die Probedivision: Testen Sie, ob n durch eine ganze Zahl von 2 bis zur Quadratwurzel von n teilbar ist. Wenn keine dieser Zahlen glatt aufgeht, ist n prim. Man muss nur bis √n prüfen, weil wenn n = a × b und sowohl a als auch b größer als √n, dann wäre a × b > n, ein Widerspruch. Zum Beispiel: Um zu testen, ob 97 prim ist, prüfen Sie die Teilbarkeit durch 2, 3, 5, 7 (da √97 ≈ 9,85). Keine teilt glatt, also ist 97 prim. Für größere Zahlen werden anspruchsvollere Algorithmen wie der Miller-Rabin-Test verwendet.
Das Sieb des Eratosthenes
Das Sieb des Eratosthenes ist ein antiker und effizienter Algorithmus zum Finden aller Primzahlen bis zu einer gegebenen Grenze. Listen Sie alle ganzen Zahlen von 2 bis n auf. Beginnen Sie mit der ersten Zahl (2) und streichen Sie alle ihre Vielfachen als zusammengesetzt (nicht prim). Gehen Sie zur nächsten nicht gestrichenen Zahl (3) und streichen Sie alle ihre Vielfachen. Fahren Sie fort. Jede nicht gestrichene Zahl, auf die Sie treffen, ist prim. Sie müssen nur bis √n sieben. Zum Beispiel: Um alle Primzahlen bis 30 zu finden, sieben Sie die Vielfachen von 2, 3 und 5 (da √30 ≈ 5,5), es bleiben 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Der Fundamentalsatz der Arithmetik
Der Fundamentalsatz der Arithmetik besagt, dass jede ganze Zahl größer als 1 auf genau eine Weise als Produkt von Primzahlen dargestellt werden kann (bis auf die Reihenfolge der Faktoren). Das bedeutet, Primzahlen sind wahrhaft die „Atome" des Zahlensystems. Zum Beispiel: 60 = 2² × 3 × 5, und keine andere Kombination von Primzahlen ergibt 60. Diese Eindeutigkeit der Primfaktorzerlegung ist die Grundlage für viele Ergebnisse in der Zahlentheorie und der Grund, warum das Finden der Primfaktorzerlegung großer Zahlen rechnerisch schwierig ist – eine Tatsache, die der modernen kryptografischen Sicherheit zugrunde liegt.
Primfaktorzerlegung
Die Primfaktorzerlegung ist der Prozess, eine zusammengesetzte Zahl in ihre Primfaktoren aufzubrechen. Die Standardmethode ist wiederholte Division: Teilen Sie die Zahl durch die kleinste Primzahl, die glatt aufgeht, teilen Sie dann den Quotienten durch die kleinste Primzahl, und wiederholen Sie, bis der Quotient 1 ist. Zum Beispiel: 360 / 2 = 180, 180 / 2 = 90, 90 / 2 = 45, 45 / 3 = 15, 15 / 3 = 5, 5 / 5 = 1, also 360 = 2³ × 3² × 5. Die Primfaktorzerlegung wird verwendet, um den größten gemeinsamen Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) zu finden und Brüche zu kürzen.
Die Unendlichkeit der Primzahlen
Eines der schönsten Ergebnisse der Mathematik, bewiesen von Euklid um 300 v. Chr., ist, dass es unendlich viele Primzahlen gibt. Der Beweis ist elegant: Nehmen Sie an, es gäbe endlich viele Primzahlen p₁, p₂, ..., pₙ, und betrachten Sie die Zahl N = (p₁ × p₂ × ... × pₙ) + 1. N ist durch keine Primzahl in der Liste teilbar (sie lässt Rest 1 bei Division durch jede), also ist entweder N selbst prim oder hat einen Primfaktor, der nicht in der Liste steht. In beiden Fällen führt die Annahme endlich vieler Primzahlen zum Widerspruch.
Verteilung der Primzahlen
Obwohl Primzahlen mit wachsenden Zahlen seltener werden, „gehen sie nie aus". Der Primzahlsatz, bewiesen 1896, besagt, dass die Anzahl der Primzahlen kleiner oder gleich n ungefähr n / ln(n) beträgt. Das bedeutet zum Beispiel, dass unter den ersten Million ganzen Zahlen ungefähr 1.000.000 / ln(1.000.000) ≈ 72.382 prim sind (die tatsächliche Anzahl ist 78.498). Die Riemannsche Vermutung, eines der größten ungelösten Probleme der Mathematik, betrifft die genaue Verteilung der Primzahlen und ist mit einem Preisgeld von einer Million Dollar des Clay Mathematics Institute dotiert.
Primzahlen in der Kryptografie
Primzahlen sind das Rückgrat moderner kryptografischer Systeme, die Internetkommunikation, Banktransaktionen und digitale Signaturen sichern. Der RSA-Verschlüsselungsalgorithmus beruht auf der Tatsache, dass das Multiplizieren zweier großer Primzahlen einfach ist, aber das Faktorisieren des Produkts zurück in seine Primkomponenten für große Zahlen außerordentlich schwierig ist. Ein typischer RSA-Schlüssel verwendet Primzahlen mit Hunderten von Ziffern, und die Sicherheit des gesamten Systems beruht auf der rechnerischen Unlösbarkeit, ihr Produkt zu faktorisieren.