Primzahlen – Sieb des Eratosthenes – Lösungen

Deine Aufträge:

Begründe, dass die Zahl 1 keine Primzahl ist.

Die Zahl 1 hat nur einen Teiler, also nicht „genau zwei unterschiedliche“.
Um Primzahlen zu finden, kann man das folgende Verfahren durchführen, das sogenannte Sieb des Eratosthenes. Zuerst wird die Zahl 1 gestrichen. Die Zahl 2 wird umkreist und dann alle Vielfachen von ihr gestrichen. Dann wird die nach der 2 nächste nicht gestrichene Zahl, die 3, umkreist und alle Vielfachen von ihr gestrichen. Jetzt wird die nach der 3 nächste freie Zahl umkreist (die 5) und ihre Vielfachen gestrichen, usw. Den Anfang siehst du im folgenden Beispiel. Fertige eine Tabelle der Zahlen bis 100 an und führe das Schema vollständig durch – umkreist bleiben nur die Primzahlen übrig.
„Wenn man eine beliebige natürliche Zahl k wählt und dann 2^k - 1 berechnet, so erhält man stets eine Primzahl, z.B. 2² - 1 = 3“. Ist diese Aussage richtig? Begründe.

Nein, es klappt zwar des öfteren, aber nicht immer:

2⁰ - 1 = 0 und 2¹ – 1 = 1 sind bereits keine Primzahlen,

2² – 1 = 3 und 2³ – 1 = 7 sind Primzahlen,

2⁴ – 1 = 15 ist keine Primzahl, 2⁵ – 1 = 31 ist Primzahl, usw. Ein Gegenbeispiel genügt schon, um die Aussage eines Satzes zu falsifizieren.
a.) Berechne für k = 1 bis 5 fünf verschiedenen Zahlen auf die folgende Art: Multipliziere die ersten k Primzahlen miteinander und addiere 1. Beispiel: Für k = 2 ist dies 2 * 3 + 1 = 7.

2 + 1= 3

2 · 3 + 1 = 7

2 · 3 · 5 + 1 = 31

2 · 3 · 5 · 7 + 1 = 211

2 · 3 · 5 · 7 · 11 + 1 = 2311

b.) Betrachte die Ergebnisse aus a.). Was fällt dir an der Einerstelle auf? Prüfe an ein paar Beispielen, ob deine Idee auch für k > 5 gilt. Versuche die Beobachtung zu erklären.

Ab k = 3 enden diese Zahlen stets auf die Ziffer 1, da dann der erste Summand als Teiler die 2 und die 5 enthält. Somit endet er auf die Ziffer 0. Die Endziffer 1 ergibt sich aus der 1 als zweitem Summanden. Nachdem nicht jede Primzahl auf 1 endet, ist jetzt spätestens klar, dass man mit dieser Methode nicht alle Primzahlen erzeugen kann.

c.)* Teile die fünf Zahlen aus a.) nacheinander durch jede einzelne Primzahl, die zu ihrer Berechnung verwendet wurde. Verwende „Teilen mit Rest“. Was fällt dir auf? Begründe.

Jede dieser Zahlen erzeugt bei der Division durch eine der erzeugenden Primzahlen den „Rest 1“. Dies ergibt sich daraus, dass der erste Summand durch jede der erzeugenden Primzahlen restlos teilbar ist und der zweite Summand die Zahl 1 ist.
a.)* Programmiere das Sieb des Erathostenes wahlweise für eine fest vorgegebene Zahl n (z.B. 1000), oder bis zu einer Zahl, die das Programm vom Nutzer zunächst abfragt.

Beispiel mit Scratch: Lösungsdatei „SiebDesErathostenes.sb2“ (Autor: Tom Schaller)

Beispiel mit dem App Inventor: Hier befindet sich die bereits programmierte App (Autorin: Monika Eisenmann)

b.)* Erkläre das Prinzip, nach dem das Sieb des Eratosthenes funktioniert.

Da man aufsteigend arbeitet, werden die Vielfachen der verwendeten Zahlen gestrichen. Jede kleinste Zahl, die nach der „aktuelle“ Vielfachenstreichung stehenbleibt, ist also kein Vielfaches der Zahlen zwischen 1 und ihr selbst, hat also keinen Teiler außer der 1 und sich selbst in diesem Bereich. Da ein Teiler nicht größer als die Zahl sein kann, gibt es nur die 1 und die Zahl selbst als Teiler, also genau zwei (ausgenommen die 1). Somit ist die kleinste stehengebliebene Zahl stets eine Primzahl.

c.)** Wiederhole Aufgabe 4 mit weiteren Werten für k. Stelle dann eine begründete Vermutung auf: Kann es eine größte Primzahl geben?

z.B. 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031, 2 · 3 · 5 · 7 · 11 · 13 ·17 + 1 = 510511

Prüfe mithilfe von Primzahltabellen, welche Zahlen davon Primzahlen sind.

Die ersten fünf so erzeugten Zahlen sind Primzahlen, die Zahlen 30031 und 510511 sind dagegen keine Primzahlen.

Die Nicht-Primzahlen darunter lassen sich in ein Produkt aus Primzahlen zerlegen ¹. Vergleiche diese Primzahlen mit denen zur Erzeugung verwendeten Primzahlen aus Aufgabe 4.

Stelle dann eine begründete Vermutung auf: Kann es eine größte Primzahl geben?

Es gilt: 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59* 509 und

2 · 3 · 5 · 7 · 11 · 13 ·17 + 1 = 510511 = 19 * 97 * 277

Jede dieser Zahlen ist nicht durch die sie nach der Regel aus Aufgabe 4 erzeugenden Primzahlen teilbar (also nicht durch die zugehörigen k ersten Primzahlen). Die Primzahlen, die als Primfaktoren dienen (z.B. 59 und 509) sind also stets größer als die verwendeten k kleinsten Primzahlen.

Die nach der Regel aus Aufgabe 4 gebildete Zahl ist somit entweder eine größere Primzahl als die zu ihrer Erzeugung verwendeten, oder wenigstens das Produkt aus größeren Primzahlen. Somit kann es keine höchste Primzahl geben.

¹ Auch hierbei hilft dir das Internet: Suche nach „Rechner für Primfaktorzerlegung“ und gib die Zahlen in so einen Rechner ein.

Primzahlen – Sieb des Eratosthenes – Lösungen: Herunterladen [odt][84 KB]

Primzahlen – Sieb des Eratosthenes – Lösungen: Herunterladen [pdf][115 KB]

Weiter zu Teilbarkeit und Teilbarkeitsregeln

Prim­zah­len – Sieb des Era­tosthe­nes – Lö­sun­gen

Deine Auf­trä­ge:

Primzahlen – Sieb des Eratosthenes – Lösungen

Deine Aufträge: