WEB LEXIKON: Ein Blick zurück
Hauptseite | Aktueller Wikipedia-Artikel

Primzahl



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

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,...
(Sequenz A000040 in OEIS)

Die Zahl 4 ist die kleinste zusammengesetzte Zahl; sie hat genau drei positive Teiler (1, 2, 4). Die Zahl 6 ist die nächstgrößere zusammengesetzte Zahl; sie besitzt vier positive Teiler (1, 2, 3, 6). Die Liste der zusammengesetzten Zahlen beginnt mit
4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, ...
(Sequenz A002808 in OEIS)

Mit Ausnahme der 2 sind alle Primzahlen ungerade, denn alle geraden Zahlen lassen sich ja durch 2 teilen. Zwei aufeinander folgende ungerade Zahlen, die beide Primzahlen sind, heißen Primzahlzwillinge, z.B. 11 und 13.

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.

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.

Eine wichtige Rolle spielen sie z.B. in der Kryptologie: Einige Verschlüsselungssysteme basieren darauf, dass man zwar relativ schnell große Primzahlen erzeugen und mit ihnen rechnen kann, dass es aber (noch) kein schnelles Faktorisierungsverfahren gibt, um große Zahlen in ihre Primfaktoren zu zerlegen (große Zahlen sind hier Zahlen mit mehr als hundert Stellen).

Table of contents
1 Verfahren zur Prüfung der Primalität einer Zahl
2 Eigenschaften von Primzahlen
3 Größte Primzahl
4 Verteilung der Primzahlen
5 Spezielle Primzahlen
6 Warum ist die 1 keine Primzahl?
7 Verallgemeinerung
8 Siehe auch
9 Literatur
10 Weblinks

Verfahren zur Prüfung der Primalität einer Zahl

Wenn man wissen möchte, ob eine Zahl eine Primzahl ist, dann hat man dafür verschiedene Möglichkeiten zur Verfügung. Die Variationen dieser Verfahren sind unter Primzahltest nachzulesen.

Eigenschaften von Primzahlen

Abgesehen von der Eigenschaft einer Primzahl, durch nur zwei natürliche Zahlen teilbar zu sein, haben Primzahlen im Besonderen in Bezug auf Modulo noch eine Menge anderer Eigenschaften.

Euler

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 entweder:

oder
bzw.

Aus
und
folgt dann,

Der kleine Fermat-Satz

dass für jede ungerade Primzahl p und jede natürliche Zahl a mit gilt:

bzw.
gilt.

Dieser Satz gilt für jede Primzahl. Es gibt aber auch Zahlen, die keine Primzahlen sind, sich aber dennoch, zu einem Teil der Basen a, wie Primzahlen verhalten. Solche Nichtprimzahlen nennt man Pseudoprimzahlen. Pseudoprimzahlen, die pseudoprim zu allen Basen a sind, welche nicht Teiler dieser Pseudoprinzahlen sind, nennt man Carmichael-Zahlen.

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.

Binomialkoeffizient

Aus dem Satz von Wilson (p ist genau dann eine Primzahl, wenn

ist) folgt, dass für jede Primzahl p und jede natürliche Zahl n die Kongruenz
erfüllt ist.

Charles Babbage bewies 1819, dass für jede Primzahl p>2 diese Kongruenz gilt:

Der Mathematiker Joseph Wolstenholme (1829-1891) bewies dann 1862, dass für jede Primzahl p>3 die folgende Kongruenz gilt:

Größte Primzahl

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, gefunden im Mai 2004 von den US-Wissenschafter Josh Findley. 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.

Verteilung der Primzahlen

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:

Verschiedene Mathematiker haben sich nun daran gemacht, Funktionen zu finden, die sich annähern.

Die Näherung von Carl Friedrich Gauß 1792 lautet:

Siehe auch: Primzahlsatz

Spezielle Primzahlen

Warum ist die 1 keine Primzahl?

Die einfachste (und von Mathematikern gern gegebene) Antwort zitiert die Definition:

Eine Motivation für diese Definition geben dagegen diese Antworten:
Siehe hierzu auch:

Verallgemeinerung

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.

Siehe auch

Literatur

Weblinks




     
Das Web Lexikon "Ein Blick zurück" bietet die Moeglichkeit auf einfache Art und Weise in den "alten" Wikipedia-Beiträgen zu blättern. Das Lexikon spiegelt den Stand der freien Wikipedia-Enzyklopädie vom August 2004 wider. Sie finden hier in rund 120.000 Artikel aus dieser Zeit Informationen, Erklärungen, Definitionen, Empfehlungen, Beschreibungen, Auskünfte und Bilder. Ebenso kommen Begriffserklärung, Zusammenfassung, Theorie, Information, Beschreibung, Erklärung, Definition und Geschichte nicht zu kurz. Ein Lexikon das Auskunft, Bericht, Hinweis, Bedeutung, Bild, Aufklärung, Darstellung und Schilderung zu unterschiedlichsten Themen kompakt auf einer Seite bietet.
Impressum ^ nach oben ^