Das Sieb des Eratosthenes
Einstieg
Bowser hat an Marios letztem Abendessen teilgenommen und es hat ihm nicht geschmeckt. Mario wurde von Bowser gefangen genommen und sitzt nun im Gefängnis des Dunkelkönigreichs fest. Das Gefängnis hat genau 100 Zellen, und jede Zelle ist bereits besetzt. Um Platz für neue Gefangene zu schaffen, führen die Koopawachen eine merkwürdige Prozedur durch, bei der sie Zellen markieren.
Die Prozedur:
- Die erste Koopawache geht an jede Zelle und markiert jede einzelne Zelle mit einem Kreuz.
- Die zweite Koopawache markiert jede zweite Zelle, beginnend bei Zelle 2.
- Die dritte Koopawache markiert jede dritte Zelle, beginnend bei Zelle 3.
- So geht es weiter, bis die letzte, 100. Koopawache jede hundertste Zelle markiert.
Die Freilassung:
Nach dieser Markierungsrunde dürfen die Gefangenen aus den Zellen entkommen, die genau zwei Kreuze aufweisen.
Marios Aufgabe:
Nachdem die Gefangenen entlassen wurden, dürfen sich alle verbliebenen Gefangenen eine neue Zelle aussuchen. Mario muss sich jetzt entscheiden, in welcher Zelle er bleiben möchte, um die besten Chancen auf eine Freilassung zu haben.
Welche Zellennummern würdest du Mario empfehlen, damit er die besten Chancen hat, von Bowser und den Koopawachen freigelassen zu werden?
Sieb des Erathostenes - Koopagefängnis
Sieb / Koopa-Markierungen (✕)
Merksatz [TIMER:240]
Aufgabe 1: Übertrage den Merkkasten und die Ergänzung in dein Heft.
Definition: Primzahl
Eine natürliche Zahl heißt Primzahl, wenn sie genau zwei Teiler besitzt. Eine Primzahl ist somit nur durch 1 und durch sich selbst teilbar.
Ergänzung
Die 1 ist keine Primzahl, weil sie nur einen Teiler besitzt.
Aufgaben / Übung [TIMER:720]
Aufgabe 2: Nimm begründet Stellung!
a) Es gibt nur eine gerade Primzahl.
b) Zwischen 30 und 40 gibt es drei Primzahlen.
c) Es gibt fünf zweistellige Primzahlen, deren letzte Ziffer eine 9 ist.
d) Es gibt nur eine Primzahl, deren letzte Ziffer eine 5 ist.
Wahr. Die einzige gerade Primzahl ist 2, da alle anderen geraden Zahlen durch 2 teilbar sind und somit keine Primzahlen sein können. Eine Primzahl ist definiert als eine Zahl, die genau zwei positive Teiler hat: 1 und sich selbst. Da die Zahl 2 diese Bedingung erfüllt und keine andere gerade Zahl dies tut, ist diese Aussage korrekt.
Falsch. Zwischen 30 und 40 liegen die folgenden Zahlen:
| \(31\) | \(32 = 4 \cdot 8\) | \(33 = 3 \cdot 11\) |
| \(34 = 2 \cdot 17\) | \(35 = 5 \cdot 7\) | \(36 = 6 \cdot 6\) |
| \(37\) | \(38 = 2 \cdot 19\) | \(39 = 3 \cdot 13\) |
Von diesen Zahlen sind nur 31 und 37 Primzahlen.
Wahr. Die zweistelligen Primzahlen, deren letzte Ziffer eine 9 ist, sind: 19, 29, 59, 79, 89. Das sind genau fünf Primzahlen, die mit einer 9 enden.
| \(19\) | \(29\) | \(39 = 3 \cdot 13\) |
| \(49 = 7 \cdot 7\) | \(59\) | \(69 = 3 \cdot 23\) |
| \(79\) | \(89\) | \(99 = 9 \cdot 11\) |
Wahr. Die einzige Primzahl, die auf 5 endet, ist 5 selbst. Alle anderen Zahlen, die auf 5 enden, sind durch 5 teilbar und somit keine Primzahlen.
Aufgabe 3: Begründe!
a ) Es gibt keine zweistellige Primzahl, deren letzte Ziffer eine 2 (eine 8 , eine 5) ist ?
b ) Gib alle Endziffern an, die bei zwei- oder mehrstelligen Primzahlen auftreten können. Begründe deine Entscheidung.
Endziffer 2: Jede Zahl, die auf 2 endet, ist eine gerade Zahl. Abgesehen von der Zahl 2 selbst, sind alle anderen geraden Zahlen durch 2 teilbar und damit keine Primzahlen.
Endziffer 8 (4, 6. 0): Ähnlich wie bei der Endziffer 2 ist jede Zahl, die auf 8 (4, 6, 0) endet, gerade. Alle geraden Zahlen außer der 2 sind durch 2 teilbar, wodurch sie keine Primzahlen sein können.
Endziffer 5: Jede Zahl, die auf 5 endet, ist durch 5 teilbar. Die einzige Ausnahme ist die Zahl 5 selbst, die eine Primzahl ist. Jede andere Zahl, die auf 5 endet, ist also keine Primzahl.
Die Endziffern, die bei zweistelligen Primzahlen auftreten können, müssen so gewählt sein, dass die Zahl nicht durch 2, 5 oder eine andere kleinere Zahl teilbar ist. Die möglichen Endziffern, die Primzahlen nicht automatisch ausschließen, sind:
- 1: Eine Zahl, die auf 1 endet, ist keine gerade Zahl und nicht durch 5 teilbar, daher kann sie eine Primzahl sein (z. B. 11, 31, 41).
- 3: Eine Zahl, die auf 3 endet, ist keine gerade Zahl und nicht durch 5 teilbar. Einige Primzahlen enden auf 3 (z. B. 13, 23, 43).
- 7: Eine Zahl, die auf 7 endet, ist keine gerade Zahl und nicht durch 5 teilbar, daher können solche Zahlen Primzahlen sein (z. B. 17, 37, 47).
- 9: Obwohl viele Zahlen, die auf 9 enden, durch 3 teilbar sind, gibt es dennoch einige Primzahlen mit der Endziffer 9 (z. B. 19, 29, 59).
Diese Endziffern sind möglich, weil Zahlen, die auf diese Ziffern enden, nicht notwendigerweise durch kleinere Primzahlen teilbar sind, und daher in manchen Fällen Primzahlen sein können.
Aufgaben / Übung [TIMER:1200]
Aufgabe 4: Im Jahr 1742 schrieb der deutsche Gelehrte Christian Goldbach (1690-1746) an seinen Freund, den berühmten Mathematiker Leonhard Euler (1707-1783), er vermute, jede ganze Zahl größer als 5 lasse sich als Summe von drei Primzahlen schreiben. Prüfe für die nachfolgenden Zahlen, ob das stimmt.
Beispiel: \[17 = \text{ _____ } + \text{ _____ } + \text{ _____ }\] |
| a) | \(6\) | \(8\) | \(9\) |
| b) | \(17\) | \(24\) | \(41\) |
| c) | \(50\) | \(63\) | \(77\) |
| d) | \(101\) | \(105\) | \(112\) |
| 6 = 2 + 2 + 2 | 8 = 3 + 3 + 2 | 9 = 3 + 3 + 3 |
| 17 = 3 + 7 + 7 | 24 = 19 + 3 + 2 | 41 = 11 + 13 + 17 |
| 50 = 43 + 5 + 2 | 63 = 19 + 23 + 7 | 77 = 19 + 29 + 29 |
| 101 = 29 + 31 + 41 | 105 = 31 + 31 + 43 | 112 = 31 + 41 + 53 |
Aufgabe 5: Die starke goldbachsche Vermutung besagt, dass jede gerade Zahl, die größer als 2 ist, als Summe zweier Primzahlen geschrieben werden kann. Überprüfe für die angegebenen Zahlen.
Beispiel: \[12 = \text{ _____ } + \text{ _____ }\] |
| a) | \(4\) | \(6\) | \(8\) |
| b) | \(12\) | \(16\) | \(44\) |
| c) | \(52\) | \(66\) | \(78\) |
| d) | \(102\) | \(116\) | \(128\) |
a)
| \(4 = 2 + 2\) | \(6 = 3 + 3\) | \(8 = 3 + 5\) |
b)
| \(12 = 5 + 7\) | \(16 = 3 + 13\) | \(44 = 3 + 41\) |
c)
| \(52 = 5 + 47\) | \(66 = 5 + 61\) | \(78 = 19 + 59\) | \(88 = 41 + 47\) |
d)
| \(102 = 5 + 97\) | \(116 = 19 + 97\) | \(128 = 19 + 109\) | \(140 = 67 + 73\) |
Aufgaben / Übung [TIMER:900]
Aufgabe 5:
Grundlagen / Verständnis (⭐)
a) Primzahlen bis 50: Liste alle Primzahlen auf, die kleiner oder gleich 50 sind.
b) Gerade oder ungerade Primzahlen: Sind Primzahlen immer ungerade? Begründe deine Antwort.
c) Ist die Zahl 1 eine Primzahl? Erkläre deine Antwort.
Vertiefung (⭐⭐)
d) Primzahlen in der Umgebung: Finde die Primzahlen, die am nächsten an der Zahl 50 liegen.
e) Primzahl-Addition: Finde zwei Primzahlen, deren Summe 20 ergibt. Gibt es mehr als eine Kombination?
f) Primzahlenmultiplikation: Finde zwei Primzahlen, deren Produkt 49 ist. Gibt es mehr als eine Kombination?
Erweitert (⭐⭐⭐)
g) Primzahlen zwischen 100 und 200: Finde alle Primzahlen, die im Bereich von 100 bis 200 liegen.
h) Primzahlzwillinge: Finde und notiere alle Primzahlpaare bis 100, deren Differenz genau zwei beträgt.
Aufgabe 6: Markus betrachtet alle zweistelligen natürlichen Zahlen.
\[\Large \text{zweistellige Zahlen} = \left\{10, 11, 12, \ldots, 97, 98, 99\right\}\]
Er sucht die zweistelligen Zahlen, die die folgenden zwei Eigenschaften haben:
| (1) Beide Ziffern der Zahl sind jeweils eine einstellige Primzahl. | (2) Wenn die Zahl durch 7 geteilt wird, bleibt ein Rest von 3. |
a) Bestimme die Menge \(P\), die genau diese Zahlen enthält.
\[\Large P = \left\{\quad \quad\ldots \quad \quad\right\}\]
b) Gib die Anzahl der Zahlen in \(P\) an.
\[\Large \text{Zahlen mit dieser Eigenschaft} = \square\]
c) Ermittle rechnerisch die Anzahl der zweistelligen natürlichen Zahlen.
\[\Large \text{Anzahl der zweistelligen Zahlen} = \square\]
d) Berechne den Anteil \(q\) der beschriebenen Zahlen an allen zweistelligen natürlichen Zahlen. Kürze falls möglich.
\[\Large q = \frac{\text{Zahlen mit dieser Eigenschaft}}{\text{Anzahl der zweistelligen Zahlen}} = \frac{\square}{\square}\]
Hilfe:
| Zahl | Division durch 7 | Rest | Rest = 3? ( / ) |
|---|---|---|---|
| \(22\) | \(22 = 7 \cdot 3 + 1\) | \(1\) | |
| \(\ldots\) | \(\ldots\) | \(\ldots\) | \(\ldots\) |
| \(\ldots\) | \(\ldots\) | \(\ldots\) | \(\ldots\) |
Hinweis: Verwende nur Zahlen, deren Ziffern aus \(2\), \(3\), \(5\) oder \(7\) bestehen.
Größte bekannte Primzahl (Oktober 2024)
\[\Huge2^{136279841}-1\]
Die Great Internet Mersenne Prime Search (GIMPS) hat am 21.10.2024 die bisher größte bekannte Primzahl entdeckt. Diese neue Primzahl gehört zu den Mersenne-Primzahlen und hat über 41 Millionen Stellen. Sie wurde durch verteiltes Rechnen gefunden, bei dem Freiwillige weltweit Rechenleistung zur Verfügung stellen. Die Entdeckung solcher Primzahlen ist wichtig für die Zahlentheorie und hat auch Anwendungen in der Kryptographie. GIMPS hat bereits mehrere Rekord-Primzahlen entdeckt, und jeder neue Fund bringt potenziell ein Preisgeld ($ 3000) mit sich.
Diese Primzahl ist zudem die erste, die mithilfe einer Grafikkarte entdeckt wurde, was einen technologischen Fortschritt in der Methode der Primzahlensuche darstellt.
GIMPS konzentriert sich auf die Suche nach Mersenne-Primzahlen, da diese durch die Form \[\Large 2^p-1\] definiert sind, wobei \(p\) eine Primzahl ist. Diese spezifische Form ermöglicht eine effizientere Überprüfung ihrer Primzahleigenschaften, was den Prozess beschleunigt und praktikabler macht.
Seit 1992 ist die größte bekannte Primzahl immer eine Mersenne-Primzahl gewesen.
Primzahlentdeckungen seit 2000
| Zahl | Anzahl der Dezimalziffern | Jahr | Entdecker (genutzter Computer) |
|---|---|---|---|
| \(2^{13466917}-1\) | 4,053,946 | 2001 | Cameron, Woltman, Kurowski (GIMPS, Athlon 800 MHz) |
| \(2^{20996011}-1\) | 6,320,430 | 2003 | Shafer (GIMPS, Pentium 4 2 GHz) |
| \(2^{24036583}-1\) | 7,235,733 | 2004 | Findley (GIMPS, Pentium 4 2.4 GHz) |
| \(2^{25964951}-1\) | 7,816,230 | 2005 | Nowak (GIMPS, Pentium 4 2.4 GHz) |
| \(2^{30402457}-1\) | 9,152,052 | 2005 | Cooper, Boone (GIMPS, Pentium 4 3 GHz) |
| \(2^{32582657}-1\) | 9,808,358 | 2006 | Cooper, Boone (GIMPS, Pentium 4 3 GHz) |
| \(2^{43112609}-1\) | 12,978,189 | 2008 | Smith, Woltman, Kurowski et al. (GIMPS, Core 2 Duo 2.4 GHz) |
| \(2^{57885161}-1\) | 17,425,170 | 2013 | Cooper, Woltman, Kurowski et al. (GIMPS, Core2 Duo E8400 @ 3.00 GHz) |
| \(2^{74207281}-1\) | 22,338,618 | 2016 | Cooper, Woltman, Kurowski et al. (GIMPS, Intel i7-4790 @ 3.60 GHz) [Video] |
| \(2^{77232917}-1\) | 23,249,425 | 2017 | Jonathan Pace et al. (GIMPS, Intel i5-6600 @ 3.30 GHz) |
| \(2^{82589933}-1\) | 24,862,048 | 2018 | Patrick Laroche et al. (GIMPS, Intel i5-4590T @ 2.0 GHz) |
| \(2^{136279841}-1\) | 41,024,320 | 2024 | Luke Durant (GIMPS, NVIDIA A100 GPU) [Video] |