Primzahl

Primzahlen nennt man alle natürlichen Zahlen, die nur 1 und sich selbst zum Teiler haben. 1 und 0 zählen nicht zu den Primzahlen, da 1 nur durch sich selbst und 0 durch alle natürlichen Zahlen teilbar ist. Die kleinste Primzahl ist demnach 2.

Formale Definition

Eine natürliche Zahl n größer als 1 wird Primzahl genannt, wenn die einzigen natürlichen Teiler von n die Zahlen 1 und n sind. Äquivalent dazu ist folgende Charakterisierung: Eine natürliche Zahl n wird Primzahl genannt, wenn n genau zwei natürliche Teiler hat.

(Alternativ: Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Teilern.)

Eine natürliche Zahl größer als 1, die keine Primzahl ist, nennt man zusammengesetzte Zahl. Die Zahlen 0 und 1 sind weder prim noch zusammengesetzt.

Die ersten Primzahlen

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)

Eine wichtige Rolle spielen sie beispielsweise in der Kryptologie: Einige Verschlüsselungssysteme basieren darauf, dass man zwar relativ schnell große Primzahlen erzeugen und multiplizieren kann, andererseits aber kein effizientes Faktorisierungsverfahren bekannt ist und allem Anschein nach auch nicht existiert. Beispielsweise können mit heutigen Rechnern problemlos zwei 50-stellige Primzahlen erzeugt und multipliziert werden. Die Rückgewinnung der beiden Primfaktoren aus diesem 100-stelligen Produkt ist dagegen im Allgemeinen nur unter erheblichem Aufwand möglich.

Wie bekommt man alle Primzahlen

Um alle Primzahlen zu erhalten nehme man alle natürlichen Zahlen größer 1 und multipliziere sie untereinander. Die Produkte seien die Menge A. Die Differenzemenge zwischen der Menge der natürlichen Zahlen größer 1 und A sind alle Primzahlen.

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 Varianten dieser Verfahren sind unter Primzahltest nachzulesen.

Eigenschaften von Primzahlen

Mit Ausnahme der Zahl 2 sind alle Primzahlen p 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, zum Beispiel 5 und 7 oder 11 und 13.

Es gilt der Fundamentalsatz der Arithmetik: Jede positive ganze Zahl lässt sich bis auf die Reihenfolge 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:

Modulo

Für jede Primzahl p > 2 gilt: $p\equiv 1\mod 4$ beziehungsweise $p\equiv -1\mod 4$
oder einfacher: Jede Primzahl p > 2 hat entweder die Form 4n+1 oder 4n-1

Für jede Primzahl p > 3 gilt: $p\equiv 1\mod 6$ beziehungsweise $p\equiv -1\mod 6$
oder einfacher: Jede Primzahl p > 3 hat entweder die Form 6n+1 oder 6n-1

Euler

Für jede ungerade Primzahl p und jede natürliche Zahl a, die teilerfremd zu p ist, was auf jede Zahl a mit $2\leq a<p$ zutrifft, gilt, dass entweder

a^{\frac {p-1}{2}}\equiv 1\mod p

oder

a^{\frac {p-1}{2}}\equiv -1\mod p

bzw.

a^{\frac {p-1}{2}}\equiv (p-1)\mod p

ist.

Es ist nicht möglich, dass beides gleichzeitig gilt.

Aus den Potenzgesetzen lässt sich $a^{\frac {p-1}{2}}\cdot a^{\frac {p-1}{2}}=(a^{\frac {p-1}{2}})^{2}=a^{2\cdot {\frac {p-1}{2}}}=a^{p-1}$ ableiten, und aus 1 · 1 = (-1) · (-1) = 1 folgt dann

Der kleine Satz von Fermat

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

a^{p-1}\equiv 1\mod p

oder

a^{p-1}-1\equiv 0\mod p

Es gibt auch Zahlen, die keine Primzahlen sind, sich aber dennoch, zu einem Teil der Basen a, wie Primzahlen verhalten. Solche Nichtprimzahlen nennt man fermatsche Pseudoprimzahlen. Pseudoprimzahlen, die pseudoprim zu allen Basen a sind, welche nicht Teiler dieser Pseudoprimzahlen sind, nennt man Carmichael-Zahlen.

Besonders in diesem Zusammenhang zeigt sich die Problematik von Pseudoprimzahlen: sie werden von Algorithmen, die den kleinen Satz von Fermat nutzen, um festzustellen ob eine bestimmte Zahl prim ist, 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 $(p-1)!\equiv -1{\pmod {p}}$ ist) folgt, dass für jede Primzahl p und jede natürliche Zahl n die Kongruenz

{{np-1} \choose {p-1}}\equiv 1{\pmod {p}}

erfüllt ist.

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

{{2p-1} \choose {p-1}}\equiv 1{\pmod {p^{2}}}

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

{{2p-1} \choose {p-1}}\equiv 1{\pmod {p^{3}}}

Giuga

Aus dem kleinen Satz von Fermat folgt, dass für eine Primzahl p gilt:

1^{p-1}+2^{p-1}+...+(p-1)^{p-1}\equiv -1{\pmod {p}}

Beispiel p = 5:

1^{4}+2^{4}+3^{4}+4^{4}=1+16+81+256=354=71\cdot 5-1\equiv -1{\pmod {5}}

Giuga vermutete, dass auch die umgekehrte Schlussrichtung gilt, dass also eine Zahl mit dieser Eigenschaft stets prim ist. Es ist nicht geklärt, ob diese Vermutung richtig ist. Bekannt ist aber, dass ein Gegenbeispiel mehr als 10.000 Dezimalstellen haben müsste. Im Zusammenhang mit Giugas Vermutung werden die Giuga-Zahlen untersucht.

Perrin-Folge

Für jede Primzahl p gilt, dass sie das Glied P(p) der Perrin-Folge teilt.

Lucas-Folge

Einen ähnliche Eigenschaft, wie die zur Perrin-Folge existiert auch zur Lucas-Folge. Wenn p eine Primzahl ist, dann gilt:

L_{p}\equiv 1\mod p

oder einfacher ausgedrückt:

(L_p - 1) läßt sich durch p teilen, wenn p eine Primzahl ist.

p:	2	3	5	7	11	13	17	19	23	29	31	37
L_p:	3	4	11	29	199	521	3.571	9.349	64.079	1.149.851	3.010.349	54.018.521

Weiteres

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.

Größte bekannte Primzahl

Euklid hat sich mit der Frage beschäftigt, wie viele Primzahlen es gibt. Der nach ihm benannte Satz von Euklid besagt, dass es unendlich viele Primzahlen gibt. Er führte einen Widerspruchsbeweis für die Richtigkeit dieses Satzes: Geht man von der Annahme aus, dass nur endlich viele Primzahlen existieren, folgt daraus die Existenz einer weiteren, größeren Primzahl, was einen logischen Widerspruch zur Annahme darstellt. Folglich ist die Annahme falsch und es gibt keine größte Primzahl. Heute kennt man eine ganze Reihe von Beweisen für den Satz von Euklid.

Es gibt aber stets eine größte bekannte Primzahl. Die derzeit größte bekannte Primzahl ist $2^{25.964.951}-1$ , eine Zahl mit 7.816.230 Dezimalstellen, gefunden im Februar 2005 von Dr. Martin Nowak im Rahmen des George Woltmans GIMPS-Projekts zur Suche von Mersenne-Primzahlen. 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 beachte jedoch, dass diese Primzahlrekorde entscheidend von der speziellen Form $2^{n}-1$ abhängen. Beispielsweise ist die nächstkleinere bekannte Primzahl $2^{24.036.583}-1$ , dazwischen liegen mehr als $10^{7.500.000}$ Zahlen, also Kandidaten für weitere Primzahlen.

Verteilung der Primzahlen

Man hat sich natürlich auch Gedanken darüber gemacht, wie viele Primzahlen es in einem begrenzten Bereich von 1 bis beispielsweise 1.000.000 gibt. Mit der Zeit wurden einige Näherungsformeln entwickelt und verbessert.

Die Funktion für die Verteilung ist $\pi (x)$ , wobei die Anzahl der Primzahlen bis zur Grenze x zurückgeliefert wird. Beispiel:

\pi (10)=4\ ;\ \pi (100)=25\ ;\ \pi (1000)=168

Verschiedene Mathematiker haben sich nun daran gemacht, Funktionen zu finden, die sich $\pi (x)$ annähern.

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

\pi (x)\sim {\frac {x}{\ln x}}

Siehe auch: Primzahlsatz

Spezielle Primzahlen

n! − 1 ist prim für n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, ... (Sequenz A002982 in OEIS)
$n!+1$ ist prim für n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154 ... (Sequenz A002981 in OEIS)
Primzahlen der Form kgv(1,...,n)+1 sind: 2, 3, 7, 13, 61, 421, 2521, 232792561, ... (Sequenz A049536 in OEIS)
Primzahlzwillinge
Primzahlquadruplet
Primzahlsextuplet
Mersenne-Primzahlen
Fermatsche Primzahlen
Wall-Sun-Sun Primzahlen
Wilson-Primzahlen
Wolstenholme-Primzahlen
Wieferich-Primzahlen
Cullen- und Woodall-Zahlen
Sophie-Germain-Primzahlen
Cunningham-Ketten
Illegale Primzahlen
Mirpzahlen
Primzahlpalindrome
Smarandache-Wellin-Primzahlen
Prothsche Primzahlen
glückliche Primzahlen
fröhliche Primzahlen

Warum ist die Zahl 1 keine Primzahl?

Die einfachste Antwort auf die Frage, warum die 1 keine Primzahl ist, zitiert die Definition:

Eine natürliche Zahl wird dann Primzahl genannt, wenn sie genau zwei natürliche Teiler hat.
Die Zahl 1 hat nur einen natürlichen Teiler (die 1). Deshalb ist sie per Definition keine Primzahl.

Die folgenden Antworten gehen auf den Zweck dieser Definition ein:

Damit man eine eindeutige Primfaktorzerlegung bekommt (man hätte sonst beliebig viele 1-Faktoren mit drin).
Weil 1 eine Einheit ist (siehe den Artikel Primelement).
Weil man ansonsten bei nahezu allen Aussagen über Primzahlen schreiben müsste: „Für alle Primzahlen mit Ausnahme der 1 gilt...“. Beispielsweise in der Theorie der endlichen Körper.

Ein mathematisches System ist letztendlich willkürlich aus einer unendlichen Anzahl von möglichen Systemen ausgewählt. Seine Relevanz erhält es dadurch, ob es nicht-triviale Eigenschaften hat. Man erzeugt zwei verschiedene Systeme, wobei im ersten 1 eine Primzahl ist, und im zweiten nicht, und stellt dabei fest, dass das erste System sehr langweilig ist, und das zweite (in dem die 1 keine Primzahl ist) so interessant ist, dass es heute einen der wichtigsten Grundbausteine der globalen Wirtschaft bildet (siehe RSA). Man könnte nun natürlich auch ein System definieren, in dem die 2 keine Primzahl ist (oder die 3 oder die 5 ...), doch solange man das herkömmliche System noch nicht völlig verstanden hat, sind diese Systeme nur für Mathematiker interessant.

Siehe hierzu auch: Warum 1 keine Primzahl ist

Primzahllücken

Die Differenz p₂ - p₁ zwischen benachbarten Primzahlen p₁ < p₂ wird Primzahllücke genannt. Die Anzahl der zusammengesetzten Zahlen zwischen zwei beliebigen aufeinanderfolgenden Primzahlen schwankt. Dabei finden sich Maxima. Näheres findet sich unter Primzahllücke.

Verallgemeinerung

In der Ringtheorie wird das Konzept der Primzahl auf die Elemente eines beliebigen kommutativen unitären Rings verallgemeinert. Die entsprechenden Begriffe sind Primelement und irreduzibles Element.

Die Primzahlen und deren Negative sind dann genau die Primelemente und auch genau die irreduziblen Elemente des Rings der ganzen Zahlen. In faktoriellen Ringen, das sind Ringe mit eindeutiger Primfaktorisierung, fallen die Begriffe Primelement und irreduzibles Element zusammen; im Allemeinen ist die Menge der Primelemente jedoch nur eine Teilmenge der Menge der irreduziblen Elemente.

Tabellen von Primzahlen

Literatur

Paolo Ribenboim: The New Book of Prime Number Records. 3. Aufl., Springer Verlag, New York, 1996, ISBN 0-387-94457-5
Marcus du Sautoy: Die Musik der Primzahlen. Auf den Spuren des größten Rätsels der Mathematik. Verlag C.H.Beck, München, 2004, ISBN 3-406-52320-X

Siehe auch

Weblinks

Vorlage:Wikibooks2

http://www.primzahlen.de
http://www.primzahlen.org
The Prime Pages
http://www.mersenne.org/freesoft.htm - Mit GIMPS Primzahlen finden
Ergänzungen und Irrtümer zu dem Buch "The new Book of Prime Number Records" von Paolo Ribenboim
Liste von Primzahl-Lücken
http://wikisource.org/wiki/Maximum_Number_of_Dividers: Zahlen mit extrem vielen Teilern