Primzahl

Eine Primzahl p ist eine natürliche Zahl, die genau zwei natürliche Teiler hat.

Zwar korrekt, aber redundant ist folgende Definition: "Eine Primzahl p ist eine natürliche Zahl, die genau zwei verschiedene positive ganzzahligeTeiler hat." Genau genommen muss das Wort "verschiedene" in der Definition gar nicht auftauchen, da das Wort "genau" - mathematisch korrekt verwandt und verstanden - dies bereits impliziert.

Falsch dagegen ist folgende, oft gehörte "Definition": Eine Primzahl p ist eine natürliche Zahl, die "nur durch 1 und sich selbst teilbar ist". Nach der richtigen Definition ist die 1 nämnlich keine Primzahl (1 ist nur durch 1 teilbar, also nicht durch zwei verschiedene natürliche Zahlen), nach der "falschen" wäre sie es (sie ist ja durch 1 und sich selbst teilbar.)

So sind z.B. die Zahlen 2, 3, 5, 7, 11 Primzahlen, die Zahl 10 jedoch nicht, weil sie 4 positive Teiler besitzt (1, 2, 5, 10). Eine Zahl, die größer als 1 und nicht Primzahl ist, nennt man zusammengesetzte Zahl. Die Zahlen 0 und 1 sind weder prim noch zusammengesetzt.

Eine Verallgemeinerung des Begriffs Primzahl auf beliebige Ringe ist der Begriff des Primelementes. Zum Beispiel sind in den ganzen Zahlen auch die Negativen der Primzahlen Primelemente.

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

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 spielen eine wichtige Rolle unter anderem 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 Verfahren gibt, um große Zahlen in ihre Primfaktoren zu zerlegen (große Zahlen sind Zahlen mit mehr als hundert Stellen).

Größte Primzahl

Da unendlich viele Primzahlen existieren, gibt es keine größte, wie der Satz von Euklid zeigt.

Die derzeit größte bekannte Primzahl ist $2^{20.996.011}-1$ , eine Zahl mit 6.320.430 Dezimalstellen, gefunden im November 2003. 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.

Verfahren zum Nachweis von Primzahlen

Der Fermatsche Primzahltest
Der ARCL-Test ist eine Verbesserung des Fermatschen Primzahltests. Der Name besteht aus den Initialen der Mathematiker Leonard M. Adleman, R.S.Rumely, H.Cohen und H.W.Lenstra Jr.
Der Lucas-Lehmer-Test zum Prüfen von Mersenne-Primzahlen. Dieses Verfahren ist im Artikel Mersenne-Primzahl beschrieben.
Die AKS-Methode ist ein Primzahltest in Polynomialzeit, der im Jahr 2002 von Manindra Agrawal, Neeraj Kayal und Nitin Saxena gefunden und nach ihnen benannt wurde.

Spezielle Primzahlen

Warum ist die 1 keine Primzahl?

Die einzig richtige Antwort lautet: Weil sie nach der Definition schlichtweg keine ist, da sie nicht genau zwei natürliche Teiler besitzt, sondern genau einen natürlichen Teiler (nämlich sich selbst, die 1). Eher humorig sind die bislang hier aufgeführten Antworten zu verstehen:

Antwort 1: Weil 1 eine Einheit ist (siehe Primelement).
Antwort 2: Damit man eine eindeutige Primfaktorenzerlegung bekommt (man hätte sonst beliebig viele 1-Faktoren mit drin).
Antwort 3: Aus der Definition heraus: 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.
Antwort 4: 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.

Siehe auch

Weblinks