Primzahl

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.

Formale Definition

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

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 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).

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 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.

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:

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äßt sich $a^{\frac {p-1}{2}}*a^{\frac {p-1}{2}}=(a^{\frac {p-1}{2}})^{2}=a^{2*{\frac {p-1}{2}}}=a^{p-1}$ ableiten, und aus $1*1=(-1)*(-1)=1$ folgt dann,

Der kleine Fermat-Satz

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

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

oder

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

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 Pseudoprimzahlen 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 $(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 sein muss. 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.

n:	2	3	5	7	11	13	17	19	23	29	31	37
L_n:	3	4	11	29	199	521	3571	9349	64079	1149851	3010349	54018521

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 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 $2^{24.036.583}-1$ , 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.

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 $\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ß 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
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 1 keine Primzahl?

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

Die Zahl 1 hat nur einen natürlichen Teiler (die 1). Eine natürliche Zahl ist genau dann Primzahl, wenn sie genau 2 natürliche Teiler hat.

Eine Motivation für diese Definition geben dagegen diese Antworten:

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, daß das erste System sehr langweilig ist, und das zweite (in dem die 1 keine Primzahl ist) so interessant ist, daß 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

Primzahl-Lücken

Die Anzahl der zusammengesetzten Zahlen zwischen zwei beliebig gewählten aufeinanderfolgenden Primzahlen schwankt. Dabei finden sich Maxima. Die nachfolgende Tabelle vermerkt das erste Auftreten der jeweils größten Lücke, und die begrenzenden Primzahlen, zwischen denen diese Lücke zum ersten Mal auftritt:

Lücke	von		bis
0	2	...	3
1	3	...	5
3	7	...	11
5	23	...	29
7	89	...	97
13	113	...	127
17	523	...	541
19	887	...	907
21	1129	...	1151

Lücke	von		bis
33	1327	...	1361
35	9551	...	9587
43	15683	...	15727
51	19609	...	19661
71	31397	...	31469
85	155921	...	156007
95	360653	...	360749
111	370261	...	370373
113	492113	...	492227

Lücke	von		bis
117	1349533	...	1349651
131	1357201	...	1357333
147	2010733	...	2010881
153	4652353	...	4652507
179	17051707	...	17051887
209	20831323	...	20831533
219	47326693	...	47326913
221	122164747	...	122164969
233	189695659	...	189695893

Lücke	von		bis
247	191912783	...	191913031
249	387096133	...	387096383
281	436273009	...	436273009
287	1294268491	-	1294268779
291	1453168141	...	1453168433
319	2300942549	...	2300942896
335	3842610773	...	3842611109
353	4302407359	...	4302407713
381	10726904659	...	10726905041

Lücke	von		bis
383	20678048297	...	20678048681
393	22367084959	...	22367085353
455	25056082087	...	25056082543
__	__	...	__
__	__	...	__
__	__	...	__
__	__	...	__
__	__	...	__
__	__	...	__

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 $2\leq a\leq n$ 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	$l_{th}$	$u_{th}$	$o_{th}$	$l_{pr}$	$u_{pr}$	$o_{pr}$
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
8	8!+2	8!+8	7	40322	40328	53	40290	40342
9	9!+2	9!+9	8	362882	362889	31	362868	362896

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	$l_{th}$	$u_{th}$	$o_{th}$	$l_{pr}$	$u_{pr}$	$o_{pr}$
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
10	kgv(2,3,4,5,6,7,8,9,10)+2	kgv(2,3,4,5,6,7,8,9,10)+10	9	2522	2530	9	2522	2530
12	kgv(2,3,4,5,6,7,8,9,10,11,12)+2	kgv(2,3,4,5,6,7,8,9,10,11,12)+12	11	27722	27732	33	27702	27732

Verallgemeinerung

Verallgemeinerungen des Begriffs Primzahl auf beliebige Ringe 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.

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

http://www.primzahlen.de
http://www.primzahlen.org
http://www.utm.edu/research/primes/
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