Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und durch sich selbst teilbar ist. So sind z.B. die Zahlen 2, 3, 5, 7, 11 Primzahlen, die Zahl 10 jedoch nicht, weil sie außer durch 1 und durch 10 auch noch durch 2 und 5 teilbar ist.
Eine Verallgemeinerung des Begriffs Primzahl auf beliebige Ringe ist der Begriff des Primelementes.
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 ganze Zahl lässts sich eindeutig als Produkt von Primzahlen darstellen (eindeutige Primfaktorzerlegung). So besteht z.B. die Zahl 1050 aus den Primfaktoren 2 · 3 · 5 · 5 · 7.
Es gibt keine größte Primzahl, sondern unendlich viele Primzahlen. Dies lässt sich mathematisch beweisen (Euklids Primzahlbeweis).
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 auf ihre Primfaktoren zu prüfen (große Zahlen sind Zahlen mit mehreren hundert Stellen!).
Sieb des Eratosthenes
- Ein Weg, alle Primzahlen bis zu einer Zahl n zu finden, ist das Sieb des Eratosthenes.
- Dies gilt vor allem für alle "kleinen" Primzahlen bis zu einer Größe von 10 Millionen.
- Man listet alle ganzen Zahlen von 2 bis n auf.
- Man streicht alle Vielfachen der Primzahlen aus, die kleiner als oder gleich groß wie die Quadratwurzel von n sind (oder einfach alle, bis es nicht mehr weiter geht - das ist das gleiche).
- Die Zahlen, die übrig bleiben, sind Primzahlen.
In der Praxis wird man nur die ungeraden Zahlen ab 3 auflisten. Das kann man aber nur machen, wenn man schon weiß, dass 2 eine Primzahl ist und alle geraden Zahlen durch 2 teilbar sind. Beides ist aber allgemein bekannt.
Weitere 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 L.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.
- Im Jahr 2002 fanden Manindra Agrawal, Neeraj Kayal und Nitin Saxena einen Algorithmus, nach ihnen AKS-Methode genannt, durch den sich der Nachweis, ob eine Zahl eine Primzahl ist, in Polynomialzeit durchführen lässt.
Fragen
- Warum ist die 1 keine Primzahl?
- 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).
Ungelöste Fragen rund um Primzahlen
- Algorithmus zur Primfaktorzerlegung: Gibt es einen schnellen Algorithmus für die Faktorisierung. Dies ist vor allem für viele Kryptographieverfahren von Bedeutung.
- Primzahlzwillinge: Ob es unendlich viele Primzahlzwillinge gibt, ist nicht bekannt.
- Goldbachsche Vermutung: Kann jede ungerade Zahl größer als 5 als Summe dreier Primzahlen geschrieben werden? bzw. Kann jede gerade Zahl größer als 2 als Summe zweier Primzahlen geschrieben werden?
Spezielle Primzahlen
Für die Entdeckung der ersten Primzahl mit mehr als einer Million Stellen ist ein Preis von 50 000 Dollar ausgeschrieben.
Weblinks
- http://www.primzahlen.de
- http://www.utm.edu/research/primes/
- http://www.utm.edu/research/primes/howmany.shtml
- http://www.mersenne.org/freesoft.htm - Mit GIMPS Primzahlen finden
- http://www.informatik.uni-frankfurt.de/~fp/Tools/Sieve.html
- http://home.t-online.de/home/0926161717-0002/prgsieb.htm - Visual Basic-Programm zur Berechnung von Primzahlen