Wikipedia

Primzahl

natürliche Zahl, die nur die 1 und sich selbst als Teiler hat
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 12. Dezember 2003 um 15:37 Uhr durch Berni~dewiki (Diskussion | Beiträge) (Details zur Faktorisierung dorthin verschoben.). Sie kann sich erheblich von der aktuellen Version unterscheiden.


Eine Primzahl p ist eine natürliche Zahl, die genau zwei verschiedene positive Teiler hat, nämlich 1 und die Zahl p selbst. 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 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 als Produkt von Primzahlen darstellen (Primfaktorzerlegung).

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 Euklids Primzahlbeweis zeigt.

Die derzeit größte bekannte Primzahl ist  , 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.

Eine weitere große Primzahl:   mit 2.098.960 Stellen

Sieb des Eratosthenes

Ein Weg, alle Primzahlen bis zu einer Zahl n zu finden, ist das Sieb des Eratosthenes:

  • Man listet alle ganzen Zahlen von 2 bis n auf.
  • Man beginnt mit der ersten Zahl p=2.
  • Alle Vielfachen von p streicht man.
  • Nun setzt man p auf die nächste Zahl, die nicht gestrichen ist, und fährt beim dritten Schritt fort.
  • Die Zahlen, die übrig bleiben, sind Primzahlen.

Dieses Verfahren liefert zwar das korrekte Ergebnis, lässt sich aber noch beschleunigen:

  • Sobald p größer als die Wurzel von n ist, kann man abbrechen, denn k-fache von p wurden für k<p bereits früher mit dem p-fachen von k gestrichen, und alle größeren Vielfachen von p sind größer als n.
  • 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.

Bei Zahlen größer als 10 Millionen sind andere Primzahlentests schneller.

Weitere Verfahren zum Nachweis von Primzahlen

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).
    • Antwort 3: Aus der Definition heraus: 1 hat nur einen positiven Teiler (die 1). Eine natürliche Zahl ist genau dann Primzahl, wenn sie genau 2 positive 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.

Ungelöste Fragen rund um Primzahlen

Spezielle Primzahlen

siehe auch: Primzahlsatz

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Primzahl&oldid=451927“