Lade Inhalt...

Was ergibt zwei mal sieben? Prima Zahlen!

Die Vorzüge von Primzahlen

von Nicola Hengels (Autor) Marta Kulaszewska (Autor)

Hausarbeit (Hauptseminar) 2010 19 Seiten

Didaktik - Mathematik

Leseprobe

INHALT

1 Einleitung

2 Definitionen und Eigenschaften von Primzahlen
2.1 Bausteine der natürlichen Zahlen
2.2 Wie viele Primzahlen gibt es?
2.3 Goldbach´sche Vermutung

3 Verfahren zur Bestimmung von Primzahlen
3.1 Sieb des Eratosthenes
3.2 Der kleine Satz von Fermat
3.2.1 Pseudoprimzahlen & Carmichael-Zahlen

4 Besondere Primzahlen
4.1 Primzahlzwillinge und -drillinge
4.2 Fermat-Zahlen
4.3 Mersenne-Zahlen
4.4 Vollkommene Zahlen

5 Fazit

LITERATURVERZEICHNIS

1 Einleitung

„Primzahlen

sind die Atome

im Reiche der Zahlen.

Aus ihnen setzen sich

alle anderen zusammen."

Bartholomé et al. 2001 [1]

Schon seit mittlerweile fast 2500 Jahren interessieren sich Menschen für die Primzahlen. Angefangen mit den Griechen Euklid, welcher zeigte, dass unendlich viele Primzahlen existieren, und Eratosthenes, dem es gelang, ein Verfahren zu entwickeln, mit dessen Hilfe man alle Primzahlen bis zu einer vorgegebenen Zahl n bestimmen kann, hin zu Mathematikern der Neuzeit, denen es mit den modernen Verschlüsselungstechniken erstmals gelang, einen wirklichen Nutzen aus der Thematik zu ziehen.[2] „Noch vor nicht langer Zeit hätte wohl niemand so in den Alltag hineinreichende praktische Anwendungen der Zahlentheorie für möglich gehalten.“[3]

Fundamentale Ideen und Methoden der Mathematik wurden im Sommersemester 2010 im Rahmen der gleichnamigen Vorlesung von Klaus-Ulrich Guder an der Leuphana Universität Lüneburg vertieft. All diese Ideen lassen sich in der sogenannten ‚Verordnung über Masterabschlüsse für Lehrämter in Niedersachsen’ nachlesen. Das Thema Primzahlen findet sich dort auf Seite 548 dem Unterpunkt Algebra und hier dem Teilgebiet Grundlagen der elementaren Zahlentheorie zugeordnet. Da heißt es, dass die Absolventen des Masterstudiengangs im Fach Mathematik mit dem Schwerpunkt Grundschule wesentliche „Eigenschaften der Primzahlen [...] , [den] Beweis der Existenz und Eindeutigkeit der Primfaktorzerlegung sowie [das] Aufzeigen der Bedeutung der Primzahlen für Codierungen“[4] beherrschen müssen.

Im zum Modul zugehörigen Seminar war es Aufgabe der Studierenden sich mit ausgewählten Fundamentalen Ideen auseinander zu setzen und ihre Ergebnisse in Form von Referaten dem Plenum zu präsentieren. Darauf aufbauend wurden die Inhalte gemeinsam in Workshops und Diskussionen vertieft. Der Leistungsnachweis im Modul bestand darin, das eigene Thema zu einer fachwissenschaftlichen Abhandlung auszubauen. Dies haben wir mit der vorliegenden schriftlichen Hausarbeit durchgeführt.

Im Folgenden werden wir nun zunächst einmal grundlegende Definitionen und Eigenschaften von Primzahlen erläutern, um daran anschließend einige Primzahltestverfahren näher zu erläutern. Im letzten Kapitel werden wir schließlich noch einige besondere Typen von Primzahlen vorstellen.

2 Definitionen und Eigenschaften von Primzahlen

Alle natürliche Zahlen > 1, die mit sich selbst und der 1 genau zwei Teiler haben, nennt man Primzahlen. Dies erklärt, warum die 1 nicht zu den Primzahlen gezählt wird, da sie nur einen Teiler hat, nämlich sich selbst.[5]

2.1 Bausteine der natürlichen Zahlen

Der Fundamentalsatz der Arithmetik besagt, dass sich jede natürliche Zahl n > 1, abgesehen von der Reihenfolge der Faktoren, in eindeutiger Weise als Produkt von Primzahlen zerlegen lässt. Somit dürfen die Primzahlen als das Fundament der Arithmetik angesehen werden.[6]

Jede natürliche Zahl n > 1 ist entweder eine Primzahl oder nicht. Für Primzahlen gilt:

Hilfssatz „Fundamental-Lemma über Primzahlen“

„Wenn eine Primzahl ein Produkt teilt, dann teilt sie mindestens einen Faktor.“ [7]

Abbildung in dieser Leseprobe nicht enthalten

für alle anderen Zahlen gilt dies nicht.

Beweis:

Setzt man voraus, dass p weder a teilt noch b, so teilt sie auch nicht das Produkt a Ÿ b. Zwei Zahlen sind genau dann teilerfremd, wenn ihr größter gemeinsamer Teiler (ggT) 1 entspricht.

a) Es gilt in diesem Falle also ggT(p,a) = 1 und ggT(p,b) ist ebenfalls 1. Die Folge hieraus ist, dass dann auch der ggT(p, a Ÿ b) = 1 sein muss. Es ist also gezeigt worden, dass p weder a noch b, noch deren Produkt teilt, somit gilt als bewiesen, dass p | a Ÿ b, wenn p Teiler von a oder b ist.[8]

b) In diesem Falle existieren s,t Abbildung in dieser Leseprobe nicht enthalten Z für die als Linearkombination nach dem erweiterten Euklidischen Algorithmus gilt, dass 1 = s Ÿ p + t Ÿ a ist. Erweitert man nun beide Seiten der Gleichung mit b, so ergibt sich

Abbildung in dieser Leseprobe nicht enthalten

Wenn p ein Teiler von a Ÿ b ist, so existiert ein k, für das gilt p Ÿ k = a Ÿ b. Eingesetzt in obige Gleichung ergibt sich

Abbildung in dieser Leseprobe nicht enthalten

Hieraus wird ersichtlich, dass p ein Teiler von b sein muss. Dies wiederum beweist, dass p | b immer dann gilt, wenn p | a Ÿ b aber nicht p | a ist.[9]

Beweis der Existenz

Eine natürliche Zahl m Abbildung in dieser Leseprobe nicht enthalten T⁄ {1}, die nicht prim ist, muss aus mindestens zwei natürlichen Faktoren a und b zusammengesetzt sein:

Abbildung in dieser Leseprobe nicht enthalten

Geht man davon aus, dass a und b je eine eindeutige Primfaktorzerlegung besitzen:

Abbildung in dieser Leseprobe nicht enthalten

so folgt daraus, dass auch m eine eindeutige Primfaktorzerlegung besitzen muss, nämlich das Produkt der beiden Primfaktorzerlegungen von a und b:

Abbildung in dieser Leseprobe nicht enthalten

Beweis der Eindeutigkeit

Nimmt man nun an, dass zwei verschiedene Primfaktorzerlegungen einer natürlichen Zahl m existieren:

Abbildung in dieser Leseprobe nicht enthalten

Da p1 Teiler von m ist, muss es folglich nach oben bewiesenem Lemma auch Teiler einer der Faktoren aus q1 Ÿ q2 Ÿ ... Ÿ qr sein, p1 teilt also qk. Aufgrund der Tatsache, dass es sich bei qk um eine Primzahl handelt, kann geschlussfolgert werden, dass qk identisch mit p1 sein muss. Auf die gleiche Weise kann gezeigt werden, dass auch die übrigen Faktoren der obigen vermeintlich unterschiedlichen Zerlegungen paarweise identisch sind. Über einen Beweis durch Widerspruch wurde gezeigt, dass es keine uneindeutige Primfaktorzerlegung geben kann.[10]

2.2 Wie viele Primzahlen gibt es?

Die Frage, ob die Menge der Primzahlen endlich ist, mag trivial klingen und nicht unbedingt ein echtes Beweisbedürfnis hervorrufen, dennoch haben bereits viele berühmte, aber auch in Vergessenheit geratene Mathematiker diese Aussage untersucht und Beweise dafür geliefert, dass das Gegenteil der Fall ist. Der älteste dieser Beweise, auf den im Folgenden näher eingegangen wird, wurde bereits im antiken Griechenland von Euklid geführt.[11]

Beweis

Euklid führte zum Belegen seiner Aussage, dass es mehr Primzahlen gäbe, als jede vorgelegte Anzahl von Primzahlen, einen Beweis durch Widerspruch. Er nahm daher an, es gäbe genau k Primzahlen. Das Produkt all dieser Primzahlen ergibt also die Zahl n:

Abbildung in dieser Leseprobe nicht enthalten

Betrachtet man nun den Nachfolger m von n, so erhält man

Abbildung in dieser Leseprobe nicht enthalten

Da pk die größte Primzahl sein sollte, kann m keine neue Primzahl sein, sodass m nach dem oben bereits bewiesenen Fundamentalsatz der Arithmetik wiederum in Primfaktoren zerlegbar sein muss. Daraus folgt, dass ein Teiler pi ungleich 1 existiert, der selbst eine Primzahl ist. Es gilt also aufgrund des Fundamental-Lemmas über Primzahlen:

Abbildung in dieser Leseprobe nicht enthalten

Hierin besteht jedoch ein Widerspruch dazu, dass pi eine Primzahl ist. Somit ist die Annahme, dass es nur k Primzahlen gibt, falsch und ihre Menge muss unendlich sein.[12]

2.3 Goldbach´sche Vermutung

„Es gibt viele alte und trotzdem noch offene Fragen, die eines gemeinsam haben: Sie sind ganz leicht zu formulieren, aber schwer zu entscheiden.“[13] Ein berühmter Vertreter dieser Spezies ist die sogenannte ‚Goldbach´sche Vermutung’, welche sich in einem Brief aus dem 18. Jahrhundert von Christian Goldbach an Leonhard Euler findet. Sie besagt, dass sich jede gerade Zahl > 2 auf mindestens eine Weise als Summe von zwei Primzahlen darstellen lässt.[14] Genaugenommen formulierte Goldabach in seinem Brief lediglich, dass dies mit einer Summe von drei Primzahlen möglich sei und Euler schränkte die Vermutung in seiner Antwort so ein, wie sie heute bekannt ist. Obwohl es sich bei dieser Annahme um einen doch vermeintlich sehr einfachen und leicht zu verstehenden Sachverhalt handelt, ist es bis heute nicht gelungen einen Beweis hierfür zu finden. Daran konnte auch ein im Jahre 2000 ausgesetztes Preisgeld von 1.000.000 Dollar nichts ändern. Wahrscheinlich handelt es sich um eine unbeweisbare Vermutung, denn auch wenn sie bereits vor zehn Jahren für alle geraden Zahlen bis hin zu vier Billionen belegt war, kann niemand mit Sicherheit sagen, ob sich nicht doch eines Tages eine gerade Zahl findet, die sich nicht als Summe zweier Primzahlen darstellen lässt.[15]

3 Verfahren zur Bestimmung von Primzahlen

Verfahren, welche beweisen, ob eine Zahl n eine Primzahl ist, nennt man ‚Primzahltests’. Hierbei existieren solche, die mit hundertprozentiger Sicherheit belegen, ob es sich bei einer Zahl um eine Primzahl handelt, und jene, bei denen dies nur mit hoher Wahrscheinlich behauptete werden kann.

3.1 Sieb des Eratosthenes

Vor mehr als 2200 Jahren entwickelte der griechische Mathematiker Eratosthenes von Kyrene einen einfachen Algorithmus zur systematischen Erzeugung aller Primzahlen in einem festgelegten Intervall natürlicher Zahlen von 1 bis n. Nach ihm benannt, kennt man dieses Verfahren heute als das ‚Sieb des Eratosthenes’, mit welchem eine aufwändige Testung jeder einzelnen Zahl mittels Divisionen nicht erforderlich ist.[16]

[...]


[1] Bartolomé et al. 2001, S. 74

[2] Vgl. Ziegenbalg 2002, S. 49f.

[3] Reiss & Schmieder 2007, S. 102

[4] Niedersächsische Staatskanzlei 2007, S. 548

[5] Vgl. Litters 2005a, S. 18

[6] Ribenboim 2009, S. 66

[7] Haftendorn 2008, S. 7

[8] Vgl. Rempe & Waldecker 2009, S. 22

[9] Vgl. Courant & Robbins 2000, S. 38

[10] Vgl. ebd. und Haftendorn 2008, S. 7

[11] Vgl. Ribenboim & Keller 2006, S. 3 und Reiss & Schmieder 2007, S. 104

[12] Vgl. Fritzlar 2007, S. 24

[13] Reiss & Schmieder 2007, S. 32

[14] Vgl. ebd.

[15] Vgl. Litters 2005b, S. 45

[16] Vgl. Litters 2005a, S. 18

Details

Seiten
19
Jahr
2010
ISBN (eBook)
9783656315261
Dateigröße
717 KB
Sprache
Deutsch
Katalognummer
v204417
Institution / Hochschule
Leuphana Universität Lüneburg – Institut für Mathematik und ihre Didaktik
Note
1,0
Schlagworte
Primzahlen Mathematik

Autoren

Zurück

Titel: Was ergibt zwei mal sieben? Prima Zahlen!