Primzahlen, Teiler und ggT

Jede natürliche Zahl größer als 1 ist entweder eine Primzahl oder lässt sich eindeutig aus Primzahlen zusammensetzen. Deshalb nennt man die Primzahlen die „Atome“ der Zahlen. Die Grundbegriffe Teiler, Primzahl, ggT und kgV findest du auf der Seite Zahlen und ihre Eigenschaften. Hier gehst du weiter: zu Rechenverfahren, Beweisen, Rekorden und offenen Fragen.

Die ersten Abschnitte sind für die Klassen 5 bis 8 gedacht, ab Euklids Beweis wird es anspruchsvoller. Zum Ausprobieren gibt es den Primzahlrechner, den Primfaktorzerlegungs-Rechner und den ggT-kgV-Rechner.

Primzahlen erkennen und finden

Schnelle Tests für kleine Teiler liefern die Teilbarkeitsregeln: Endziffer für 2 und 5, Quersumme für 3 und 9. Für alles andere gibt es die Probedivision.

Alle Primzahlen bis zu einer Grenze findest du am schnellsten mit dem Sieb des Eratosthenes. Wegen der Wurzelregel streichst du bis 1.000 nur die Vielfachen der 11 Primzahlen bis 31, denn √1.000 ≈ 31,6.

Das Sechser-Muster

Schreibe die Zahlen in Zeilen nach dem Rest beim Teilen durch 6. Die Zahlen mit Rest 0, 2 oder 4 sind gerade, die mit Rest 3 durch 3 teilbar. Außer 2 und 3 bleiben für Primzahlen nur die Reste 1 und 5, also die Formen 6k + 1 und 6k − 1.

Umgekehrt ist nicht jede Zahl dieser Form prim: 25, 35, 49 und 55 sind es nicht. Das Muster spart aber Arbeit, denn du musst bei der Probedivision nur noch 2, 3 und Zahlen der Form 6k ± 1 als Teiler ausprobieren.

Primfaktorzerlegung: was sie verrät

Jede Zahl größer als 1 ist ein Produkt von Primzahlen, und zwar auf genau eine Weise, wenn du die Reihenfolge nicht beachtest. Das ist der Hauptsatz der Arithmetik. Wie du eine Zahl zerlegst, steht im Abschnitt Primfaktorzerlegung. Hier geht es darum, was du aus der Zerlegung ablesen kannst.

Anzahl und Summe der Teiler

Jeder Teiler von 360 = 2³ · 3² · 5 entsteht, wenn du bei jedem Primfaktor eine Hochzahl wählst: bei der 2 eine von 0, 1, 2, 3 (vier Möglichkeiten), bei der 3 eine von 0, 1, 2 (drei) und bei der 5 eine von 0, 1 (zwei). Das ergibt 4 · 3 · 2 = 24 Teiler.

Aus der Formel folgt: Eine Zahl hat genau dann eine ungerade Zahl von Teilern, wenn alle Hochzahlen gerade sind, also wenn sie eine Quadratzahl ist. So hat 36 = 2² · 3² genau 3 · 3 = 9 Teiler und 100 = 2² · 5² ebenfalls 9.

ggT und kgV: zwei Wege

Die Bedeutung von ggT und kgV kennst du aus dem Abschnitt ggT der Seite Zahlen. Hier siehst du, wie die beiden Wege zusammenpassen.

Mit Primfaktoren

Schreibe beide Zahlen als Potenzen derselben Primzahlen. Für den ggT nimmst du von jedem Primfaktor die kleinere Hochzahl, für das kgV die größere.

Damit ist ggT = 2 · 3² · 5 · 7 = 630 und kgV = 2² · 3² · 5² · 7 = 6.300. Probe: 630 · 6.300 = 3.969.000 = 1.260 · 3.150. Dieser Zusammenhang gilt immer:

Mit dem euklidischen Algorithmus

Bei großen Zahlen ist das Zerlegen mühsam. Der Algorithmus kommt ohne Primfaktoren aus. Du teilst die größere Zahl durch die kleinere, dann die kleinere durch den Rest, und so weiter, bis der Rest 0 ist. Der letzte Rest vor der Null ist der ggT. Er beruht auf dem Satz: Jeder gemeinsame Teiler von a und b teilt auch den Rest r = a − q · b, und umgekehrt. Also gilt ggT(a, b) = ggT(b, r).

Der Algorithmus ist sehr schnell. Am längsten rechnet man mit aufeinanderfolgenden Fibonacci-Zahlen: Für 89 und 55 sind es 9 Divisionen. Selbst bei Zahlen mit hundert Stellen sind es höchstens ein paar hundert Schritte. Mit Rückwärtsrechnen erhält man zusätzlich Zahlen x und y mit ggT = a · x + b · y. Das ist der erweiterte euklidische Algorithmus, der beim Verschlüsseln und beim Rechnen mit Resten gebraucht wird.

Euklids Beweis: unendlich viele Primzahlen

Die Primzahlen werden immer seltener, aber sie hören nie auf. Der Beweis steht als Satz 20 im neunten Buch der Elemente des Euklid (um 300 v. Chr.) und gilt bis heute als Muster eines Beweises durch Widerspruch.

1. Angenommen, es gäbe nur endlich viele Primzahlen p₁, p₂, …, p_k.
2. Bilde N = p₁ · p₂ · … · p_k + 1.
3. Teilst du N durch eine der Primzahlen p_i, bleibt der Rest 1. Keine der Primzahlen teilt also N.
4. N ist größer als 1 und hat daher einen Primteiler. Dieser kann keines der p_i sein. Das ist ein Widerspruch, also gibt es unendlich viele Primzahlen.

Wie verteilen sich die Primzahlen?

Bis 10 gibt es 4 Primzahlen, bis 100 sind es 25, also jede vierte Zahl. Bis 1.000.000 sind es 78.498, nur noch etwa jede dreizehnte. Die Primzahlen werden dünner, aber nach einer überraschend genauen Regel.

Das Verhältnis nähert sich 1. Das besagt der Primzahlsatz: Die Anzahl π(x) der Primzahlen bis x ist ungefähr x : ln x. Gauß und Legendre vermuteten das um 1800 aus Zahlentafeln. Bewiesen wurde es erst 1896, unabhängig voneinander von Jacques Hadamard und Charles de la Vallée Poussin, mit Hilfe der Funktionentheorie.

Lücken zwischen Primzahlen

Primzahlen können beliebig weit auseinanderliegen. Für jede Länge n gibt es n aufeinanderfolgende zusammengesetzte Zahlen: (n + 1)! + 2, (n + 1)! + 3, …, (n + 1)! + (n + 1). Die erste ist durch 2 teilbar, die zweite durch 3, und so weiter. Für n = 6 ist 7! = 5.040 und die Zahlen 5.042 bis 5.047 sind zusammengesetzt (5.042 = 2 · 2.521, 5.043 = 3 · 1.681, 5.044 = 4 · 1.261, 5.045 = 5 · 1.009, 5.046 = 6 · 841 und 5.047 = 7 · 721).

Offene Fragen

Trotz der Fortschritte sind einfache Fragen über Primzahlen noch ungelöst. Einen Überblick gibt die Seite Ungelöste Probleme einfach erklärt.

• Goldbachsche Vermutung: Christian Goldbach schrieb 1742 an Leonhard Euler, jede gerade Zahl größer als 2 sei die Summe zweier Primzahlen. So ist 100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53. Computer haben sie bis 4 · 10¹⁸ bestätigt, ein Beweis fehlt. Für die schwächere Variante, jede ungerade Zahl ab 7 sei Summe dreier Primzahlen, legte Harald Helfgott 2013 einen Beweis vor.
• Primzahlzwillinge: Das sind Paare wie (11, 13) oder (59, 61) mit dem Abstand 2. Ob es unendlich viele gibt, weiß niemand. 2013 bewies Yitang Zhang, dass es unendlich viele Primzahlpaare mit einem Abstand von höchstens 70 Millionen gibt. Diese Schranke wurde seither auf 246 gesenkt.
• Riemannsche Vermutung: Bernhard Riemann stellte 1859 eine Vermutung über die Nullstellen der Zetafunktion auf. Sie würde den Fehler im Primzahlsatz stark eingrenzen. Sie gehört zu den Millennium-Problemen.

Mersenne-Primzahlen und die größte bekannte Primzahl

Zahlen der Form 2^p − 1 heißen nach Marin Mersenne Mersenne-Zahlen. Ist 2^p − 1 prim, muss p prim sein, umgekehrt reicht das aber nicht.

Mersenne-Primzahlen sind aus zwei Gründen berühmt. Erstens gibt es für sie einen schnellen Test, den Lucas-Lehmer-Test (Édouard Lucas 1876, Derrick Lehmer 1930). Deshalb stammen fast alle Rekordprimzahlen seit Jahrzehnten aus dieser Familie. Zweitens liefern sie vollkommene Zahlen, das sind Zahlen, die gleich der Summe ihrer echten Teiler sind: 6 = 1 + 2 + 3 und 28 = 1 + 2 + 4 + 7 + 14.

Mersenne nannte 1644 eine Liste von Exponenten, die nicht ganz stimmte: 2⁶⁷ − 1 ist nicht prim (Lucas 1876, die Faktoren fand 1903 Frank Cole), und 2⁶¹ − 1 fehlt in seiner Liste. Seit 1996 sucht das Gemeinschaftsprojekt GIMPS mit freiwilligen Computern nach neuen Mersenne-Primzahlen.

Ausblick: Primzahlen und Verschlüsselung

Zwei große Primzahlen zu multiplizieren ist einfach, das Produkt wieder zu zerlegen sehr schwer. Darauf baut das 1977 entwickelte RSA-Verfahren auf. Mit 61 · 53 = 3.233 siehst du das Prinzip im Kleinen. Echte Schlüssel arbeiten mit Zahlen von 2.048 Bit, also etwa 617 Dezimalstellen, die sich aus zwei Primzahlen von je rund 300 Stellen zusammensetzen. Wie das genau funktioniert, steht bei Modulare Arithmetik und im Magazinartikel Primzahlen und Verschlüsselung.

Typische Fehler

Übungen

Weitere Aufgaben gibt es im Arbeitsblatt Teiler und Primzahlen.

Geschichte: von Euklid bis GIMPS

Euklid ordnete das Wissen der Antike in den Büchern 7 bis 9 der Elemente: die Teilbarkeit, den Algorithmus für den ggT und den Beweis, dass es unendlich viele Primzahlen gibt. Im dritten Jahrhundert v. Chr. beschrieb Eratosthenes sein Sieb. Carl Friedrich Gauß formulierte den Hauptsatz der Arithmetik in den Disquisitiones Arithmeticae (1801) und bewies ihn.

Leonhard Euler wies 1772 nach, dass 2³¹ − 1 = 2.147.483.647 prim ist. Mit dem Lucas-Lehmer-Test kamen im 20. Jahrhundert große Mersenne-Primzahlen dazu, seit 1996 verteilt GIMPS die Suche auf Computer in aller Welt. Die Frage nach der Verteilung beantwortete 1896 der Primzahlsatz.

Häufige Fragen

Quellen und weiterführende Literatur

• Thomas L. Heath (Hrsg.): The Thirteen Books of Euclid’s Elements, 3 Bände, 2. Auflage, Cambridge University Press, Cambridge 1926.
• Carl Friedrich Gauß: Disquisitiones Arithmeticae, Leipzig 1801.
• Wikipedia: Primzahl
• Wikipedia: Primzahlsatz
• Wikipedia: Euklidischer Algorithmus
• Wikipedia: Mersenne-Zahl