Primzahl Bedeutung, Erklärung und Definition.
Eine Primzahl ist eine natürliche Zahl, die selbst größer als 1 ist und von allen ganzen Zahlen größer als Null nur durch die Zahl 1 und sich selbst ganzzahlig (d.h. ohne Rest) teilbar ist.So ist beispielsweise die Zahl 11 eine Primzahl, weil 11 ganzzahlig sowie größer als 1 ist und von allen ganzen Zahlen größer als 0 nur durch die 1 und die 11 selbst ohne Rest ganzzahlig teilbar ist. Dagegen ist die Zahl 12 keine Primzahl, weil sie zwar ganzzahlig und größer als 1 ist, aber von allen ganzen Zahlen größer als 0 außer durch die 1 und sich selbst auch durch die Zahlen 2, 3, 4 und 6 ganzzahlig ohne Rest geteilt werden kann.
Formelle Definition
Eine Primzahl p ist eine natürliche Zahl größer als 1, die nur die Zahlen 1 und p als positive Teiler hat. Gleichwertig damit ist folgende Definition: Eine Primzahl p ist eine natürliche Zahl, die genau zwei natürliche Teiler hat.
Eine natürliche Zahl, die größer als 1 und nicht Primzahl ist, nennt man zusammengesetzte Zahl. Die Zahlen 0 und 1 sind weder prim noch zusammengesetzt.
Die ersten Primzahlen sind
Die ersten Primzahlen
Wenn man wissen möchte, ob eine Zahl eine Primzahl ist, dann hat man dafür verschiedene Möglichkeiten zur Verfügung. Die Varianten dieser Verfahren sind unter Primzahltest nachzulesen.
Es gilt der Fundamentalsatz der Arithmetik: Jede positive natürliche Zahl lässt sich eindeutig als Produkt von Primzahlen darstellen (siehe Primfaktorzerlegung), die in dieser Darstellung auftretenden Primzahlen nennt man die Primfaktoren der Zahl. Die Schwierigkeiten bei der Primfaktorzerlegung bezeichnet man als Faktorisierungsprobleme. Man versucht sie mit geeigneten Faktorisierungsverfahren zu minimieren.
Primzahlen besitzen vor allem aufgrund dieses Satzes eine besondere Stellung in der Mathematik.
Alexander K. Dewdney bezeichnet ihre Stellung als ähnlich den Elementen der Chemie.
Abgesehen von der Eigenschaft einer Primzahl, durch nur zwei natürliche Zahlen teilbar zu sein, haben Primzahlen im Besonderen in Bezug auf die Modulo-Operation noch eine Menge anderer Eigenschaften:
Für jede ungerade Primzahl p und jede natürliche Zahl a, die teilerfremd zu p ist, was auf jede Zahl a mit zutrifft, gilt, dass entweder
dass für jede ungerade Primzahl p und jede natürliche Zahl a mit gilt:
Verfahren zur Prüfung der Primalität einer Zahl
Eigenschaften von Primzahlen
Mit Ausnahme der 2 sind alle Primzahlen ungerade, denn alle größeren geraden Zahlen lassen sich außer durch p und 1 auch noch (mindestens) durch 2 teilen. Zwei aufeinander folgende ungerade Zahlen, die beide Primzahlen sind, heißen Primzahlzwillinge, z.B. 5 und 7 oder 11 und 13.Euler
oder
Es ist nicht möglich, dass beides gleichzeitig gilt.
Aus den Potenzgesetzen läßt sich ableiten, und aus folgt dann,Der kleine Fermat-Satz
|
- oder
|
Besonders in diesem Zusammenhang zeigt sich die Problematik von Pseudoprimzahlen: sie werden von den Algorithmen fälschlicherweise für Primzahlen gehalten. Wenn allerdings ein Verschlüsselungsverfahren wie RSA eine zusammengesetzte Zahl statt einer Primzahl verwendet, ist die Verschlüsselung nicht mehr sicher. Deshalb müssen bei solchen Verfahren Primzahltests verwendet werden, die mit einer sehr hohen Wahrscheinlichkeit Primzahlen von zusammengesetzten Zahlen unterscheiden können. Diese Wahrscheinlichkeit ist bei Verwendung des kleinen Satzes von Fermat als Basis allein nicht hoch genug, es gibt aber sicherere Primzahltests.
Aus dem Satz von Wilson (p ist genau dann eine Primzahl, wenn
Charles Babbage bewies 1819, dass für jede Primzahl p>2 diese Kongruenz gilt:
Binomialkoeffizient
ist) folgt, dass für jede Primzahl p und jede natürliche Zahl n die Kongruenz
erfüllt ist.
Der Mathematiker Joseph Wolstenholme (1829-1891) bewies dann 1862, dass für jede Primzahl p>3 die folgende Kongruenz gilt:
Giuga
Für eine Primzahl p gilt:
|
Beispiel:
- 'p' = 5
Perrin-Folge
Für jede Primzahl p gilt, dass sie das Glied P(p) der Perrin-Folge teilt.
Einen ähnliche Eigenschaft, wie die zur Perrin-Folge existiert auch zur Lucas-Folge. Wenn p eine Primzahl ist, dann gilt:
Lucas-Folge
oder einfacher ausgedrückt:
| n: | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 |
| Ln: | 3 | 4 | 11 | 29 | 199 | 521 | 3571 | 9349 | 64079 | 1149851 | 3010349 | 54018521 |
Zwei natürliche Zahlen, deren Summe eine Primzahl ergeben, sind immer teilerfremd. Insbesondere ist jede Kombination zweier natürlicher Zahlen, in die sich eine Primzahl zerlegen lässt, teilerfremd.
Euklid hat sich mit der Frage beschäftigt, ob es endlich viele oder unendlich viele Primzahlen gibt. Sein Satz von Euklid besagt, dass es unendlich viele Primzahlen gibt. Zum Beweis zeigt er, dass die Annahme, es gebe nur endlich viele Primzahlen, zu einem Widerspruch führt. Nach ihm haben das noch einige andere gezeigt .
Die derzeit größte bekannte Primzahl ist , eine Zahl mit 7.235.733 Dezimalstellen [1], gefunden im Mai 2004 von dem US-Wissenschaftler Josh Findley im Rahmen von George Woltmans GIMPS-Projekt. Für den ersten Primzahlbeweis einer Zahl mit mehr als 10 Millionen Stellen hat die Electronic Frontier Foundation einen Preis von 100.000 US-Dollar ausgeschrieben.
Man hat sich natürlich auch Gedanken darüber gemacht, wie viele Primzahlen es in einem begrenzten Bereich von 1 bis z.B. 1.000.000 gibt. Mit der Zeit wurden einige Näherungsformeln entwickelt und verbessert.
Die Funktion für die Verteilung ist , wobei die Anzahl der Primzahlen bis zur Grenze x zurückgeliefert wird. Beispiel:
Die Näherung von Carl Friedrich Gauß 1792 lautet:
Die einfachste (und von Mathematikern gern gegebene) Antwort zitiert die Definition:
Weiteres
Größte Primzahl
Verteilung der Primzahlen
Verschiedene Mathematiker haben sich nun daran gemacht, Funktionen zu finden, die sich annähern.
Siehe auch: PrimzahlsatzSpezielle Primzahlen
Warum ist die 1 keine Primzahl?
Eine Motivation für diese Definition geben dagegen diese Antworten:
Siehe hierzu auch:
|
|
|
|
Die Lücken können beliebig groß werden. Eine Möglichkeit, solche Primzahllücken zu konstruieren, baut auf die Eigenschaften der Fakultät, kurz n! geschrieben. Für alle n enthält die Folge n!+2...n!+n sicher keine Primzahlen, da in n! alle natürlichen Zahlen von 2 bis n als Faktoren enthalten sind und sich somit jede Zahl n!+a mit in die Form ab+a bringen lässt. Auf diese Weise lässt sich stets eine Primzahllücke beliebiger Mindestgröße konstruieren. Das Verfahren ergibt aber nicht notwendigerweise das erste Auftreten einer solchen Lücke.
| theoretische Lücke | praktische Lücke | |||||||
| n | n!+2 | n!+n | ||||||
| 2 | 2!+2 | 2!+2 | 1 | 4 | 4 | 1 | 4 | 4 |
| 3 | 3!+2 | 3!+3 | 2 | 8 | 9 | 3 | 8 | 10 |
| 4 | 4!+2 | 4!+4 | 3 | 26 | 28 | 5 | 24 | 28 |
| 5 | 5!+2 | 5!+5 | 4 | 122 | 125 | 13 | 114 | 126 |
| 6 | 6!+2 | 6!+6 | 5 | 722 | 726 | 7 | 720 | 726 |
| 7 | 7!+2 | 7!+7 | 6 | 5042 | 5047 | 11 | 5040 | 5050 |
Alternativ zu n! läßt sich auch das kgv(2,3,..,n) (kleinstes gemeinsames Vielfaches) benutzen.
| theoretische Lücke | praktische Lücke | |||||||
| n | kgv(2,3,..,n)+2 | kgv(2,3,..,n)+n | ||||||
| 2 | kgv(2)+2 | kgv(2)+2 | 1 | 4 | 4 | 1 | 4 | 4 |
| 3 | kgv(2,3)+2 | kgv(2,3)+3 | 2 | 8 | 9 | 3 | 8 | 10 |
| 4 | kgv(2,3,4)+2 | kgv(2,3,4)+4 | 3 | 14 | 16 | 3 | 14 | 16 |
| 6 | kgv(2,3,4,5,6)+2 | kgv(2,3,4,5)+6 | 5 | 62 | 66 | 5 | 62 | 66 |
| 7 | kgv(2,3,4,5,6,7)+2 | kgv(2,3,4,5,6,7)+7 | 6 | 422 | 427 | 9 | 422 | 430 |
| 8 | kgv(2,3,4,5,6,7,8)+2 | kgv(2,3,4,5,6,7,8)+8 | 7 | 842 | 848 | 13 | 840 | 852 |
Verallgemeinerungen des Begriffs Primzahl auf beliebige Ringee sind die Begriffe Primelement und irreduzibles Element.
Zum Beispiel sind in den ganzen Zahlen auch die Negativen der Primzahlen sowohl Primelemente als auch irreduzible Elemente. In einigen anderen Ringen unterscheiden sich jedoch diese beiden Begriffe.
Eine ähnliche Definition wie die Primzahlen haben die Sekundzahlen: Dies sind natürliche Zahlen mit genau drei natürlichen Teilern.
Diese Seite ist ein Artikel über Primzahl. Seite Versuche, zum von von Beschreibung über bereitzustellen Primzahl. Sie konnten Tatsachen über auch finden Primzahl. Erklärung von Primzahl.Verallgemeinerung
Tabellen von Primzahlen
Literatur
Siehe auch
Weblinks