Entdecken
Um alle Primzahlen bis 100 zu finden, hatte Eratosthenes (276–194 v. Chr.) einen einfachen Trick. Welchen?
- Die Vielfachen von 2 streichen, dann von 3, 5, 7 …: Was übrig bleibt, ist prim
- Jede Zahl durch alle kleineren Zahlen teilen
Die Grundidee
Primzahlen, Teiler und Vielfache in der Geschichte.
- Schritt 1Euklid um 300 v. Chr.FantasiebildnisUnbekannter Künstler. GemeinfreiUm 300 v. Chr.: Buch VII der Elemente und der euklidische Algorithmus.
- Schritt 2Eratosthenes um 276 – um 194 v. Chr.FantasiebildnisUnbekannter Künstler. GemeinfreiEratosthenes (276–194 v. Chr.): das Primzahlsieb.
Buch VII von Euklids Elementen (um 300 v. Chr.) ist eine Einführung in die Zahlentheorie und enthält den euklidischen Algorithmus für den größten gemeinsamen Teiler. Eratosthenes von Kyrene (276–194 v. Chr.), der auch die Erde vermaß, ist für sein Primzahlsieb bekannt.
Es gibt mehr Primzahlen als jede vorgelegte Anzahl von Primzahlen.
Was behauptet Euklid?
- Es gibt keine größte Primzahl: Sie hören nie auf
- Es gibt genau so viele Primzahlen, wie er aufgezählt hat
Beispiel
Der euklidische Algorithmus für den ggT von 84 und 36.
Üben ★
- Wofür ist Eratosthenes in der Zahlentheorie bekannt?
- Sein Primzahlsieb
- Den Algorithmus für den ggT
- Negative Zahlen
- Erster Schritt des euklidischen Algorithmus: Welcher Rest bleibt bei 42 : 9?
- Erster Schritt des euklidischen Algorithmus: Welcher Rest bleibt bei 271 : 33?
- Sieb des Eratosthenes für die Zahlen 1 bis 42: Nach dem Streichen der Vielfachen von 2 (außer der 2) – wie viele Zahlen bleiben?
Merkkarte
Primzahlen heute
- Online-Zahlungen sind mit Codes aus riesigen Primzahlen geschützt.
- Brüche kürzt man mit dem ggT.
- Kalender und Zahnräder wiederholen sich nach einem kgV.
Quellen: MacTutor-Biografien von Euklid und Eratosthenes (siehe „Quellen und Nachweise“).