Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMontag, 21. Oktober 2019 

Primzahl


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Eine Primzahl p ist eine natürliche Zahl größer als 1 die nur die 1 und p als positive Teiler hat. Gleichwertig damit ist folgende Definition: Primzahl p ist eine natürliche Zahl die genau zwei natürliche Teiler hat.

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

Die ersten Primzahlen sind

2 3 5 7 11 13 17 23 29 31 37 41 43 47 59 61 67 71 73 79 83 97 101 ...
(Sequenz A000040 in OEIS )

Die Zahl 4 ist die kleinste Zahl; sie hat genau drei positive Teiler 2 4). Die Zahl 6 ist die zusammengesetzte Zahl; sie besitzt vier positive Teiler 2 3 6). Die Liste der zusammengesetzten beginnt mit

4 6 8 9 10 12 14 16 18 20 21 22 24 25
(Sequenz A002808 in OEIS )

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

Es gilt der Fundamentalsatz der Arithmetik : Jede positive natürliche Zahl lässt sich eindeutig als Produkt von Primzahlen darstellen (siehe Primfaktorzerlegung ) die in dieser Darstellung auftretenden Primzahlen man die Primfaktoren der Zahl.

Primzahlen besitzen vor allem aufgrund dieses eine besondere Stellung in der Mathematik. Alexander Dewdney bezeichnet ihre Stellung als ähnlich den der Chemie.

Eine wichtige Rolle spielen sie z.B. der Kryptologie : Einige Verschlüsselungssysteme basieren darauf dass man relativ schnell große Primzahlen erzeugen und mit rechnen kann dass es aber (noch) kein Verfahren gibt um große Zahlen in ihre zu zerlegen (große Zahlen sind hier Zahlen mehr als hundert Stellen).

Inhaltsverzeichnis

Verfahren zur Prüfung der Primalität einer

Wenn man wissen möchte ob eine eine Primzahl ist dann hat man dafür Möglichkeiten zur Verfügung. Die Variationen dieser Verfahren unter Primzahltest nachzulesen.

Eigenschaften von Primzahlen

Abgesehen von der Eigenschaft einer Primzahl nur zwei natürliche Zahlen teilbar zu sein Primzahlen im besonderen in Bezug auf Modulo noch eine Menge Eigenschaften.

Der kleine Fermat-Satz

Für jede Primzahl p und jede natürliche Zahl a mit <math>2 \le a < p</math>

<math>a^{p-1}-1 = 0 \mod p</math>

Dieser Satz gilt für jede Primzahl. gibt aber auch Zahlen die keine Primzahlen sich aber dennoch zu einem Teil der a wie Primzahlen verhalten. Solche Nichtprimzahlen nennt Pseudoprimzahlen . Pseudoprimzahlen die pseudoprim zu allen Basen a sind welche nicht Teiler dieser Pseudoprinzahlen nennt man Carmichael-Zahlen .

Besonders in diesem Zusammenhang zeigt sich Problematik von Pseudoprimzahlen: sie werden von den fälschlicherweise für Primzahlen gehalten. Wenn allerdings ein wie RSA eine zusammengesetzte Zahl statt einer Primzahl ist die Verschlüsselung nicht mehr sicher. Deshalb bei solchen Verfahren Primzahltests verwendet werden die einer sehr hohen Wahrscheinlichkeit Primzahlen von zusammengesetzten unterscheiden können. Diese Wahrscheinlichkeit ist bei Verwendung kleinen Satzes von Fermat als Basis allein hoch genug es gibt aber sicherere Primzahltests.

Binomialkoeffizient

Für jede Primzahl p gilt:

<math>{{2p-1} \choose {p-1}} \equiv 1 \mod p^3</math>

Größte Primzahl

Euklid hat sich mit der Frage beschäftigt es endlich viele oder unendlich viele Primzahlen Mit seinem Euklidschen Satz hat er gezeigt dass die Annahme gebe nur endlich viele Primzahlen zu einem führt und damit bewiesen daß es unendlich Primzahlen geben muß. Nach ihm haben das einige andere gezeigt .

Die derzeit größte bekannte Primzahl ist <math>2^{20.996.011}-1</math> eine Zahl mit Dezimalstellen gefunden im November 2003. Für den Primzahlbeweis einer Zahl mit mehr als 10 Stellen hat die Electronic Frontier Foundation einen Preis von 100.000 US-Dollar ausgeschrieben.

Verteilung der Primzahlen

Man hat sich natürlich auch Gedanken gemacht wie viele Primzahlen es in einem Bereich von 1 bis z.B. 1.000.000 gibt. der Zeit wurden einige Näherungsformeln entwickelt und

Die Funktion für die Verteilung ist wobei die Anzahl der Primzahlen bis zur x zurückgeliefert wird. Beispiel:

<math>\pi(10) = 4\ ;\ \pi(100) = ;\ \pi(1000) = 168 </math>

Verschiedene Mathematiker haben sich nun daran Funktionen zu finden die sich <math>\pi(x)</math> annähern.

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

<math>\pi(x) \approx \frac{x}{\log x}</math>

Spezielle Primzahlen

Warum ist die 1 keine Primzahl?

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

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

Eine Motivation für diese Definition geben diese Antworten:

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

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 als auch irreduzible Elemente. In einigen anderen unterscheiden sich jedoch diese beiden Begriffe.

Siehe auch

Literatur

  • The New Book of Prime Number Records Ribenboim Springer Verlag 1996 ISBN 0-387-94457-5

Weblinks




Bücher zum Thema Primzahl

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Primzahl.html">Primzahl </a>