Primzahlen

Definition: Eine Zahl p (Element der natürlichen Zahlen) heißt prim, wenn sie nur 1 und sich selbst als Teiler hat. Inbesondere folgt also für eine Primzahl p aus der Gleichung a*b = p, dass entweder a oder b mit p identisch sein muss. Alle Primzahlen außer 2 sind naturgemäß ungerade Zahlen.

Beispiele für Primzahlen:
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, ...

Bereits früh erkannte man, dass es unendlich viele Primzahlen gibt. Der Beweis erfolgte durch Euklid.

Die Dichte der Primzahlen nimmt langsam ab. Carl Friedrich Gauss fand eine Formel, die die Größenordnung der Anzahl der Primzahlen angibt - diese wird mit der Funktion π(x) beschrieben.

Primzahlen bilden die Grundbausteine aller natürlichen Zahlen:

Satz: (Hauptsatz der Elementaren Zahlentheorie) Jede natürliche Zahl n (> 1) kann als Produkt von Primzahlen - den Primfaktoren - dargestellt werden. Die Zerlegung existiert für alle Zahlen > 1 und ist bis auf die Anordnung eindeutig.

Eine Besonderheit der Primzahlen ist die Tatsache, dass es keine "Erzeugungsformel" gibt. Um mit vollständiger Sicherheit zu zeigen, ob ein Zahl p eine Primzahl ist, müssen alle möglichen Teiler (bis zur Wurzel aus p) duchprobiert werden - für genügend hohe Zahlen eine recht rechenintensive, aufwändige Tätigkeit. Ab einer bestimmten Höhe der Zahl ist diese Methode selbst mit den schnellsten Computern nicht mehr in akzeptablen Zeiträumen lösbar!

Seit der Antike versuchten sich viele Mathematiker an Formeln, wie man dem Geheimnis der Primzahlen auf die Spur kommen könnte oder ihre Ermittlung erleichtern kann. Heute verlässt man sich auf stochastische Testverfahren, die mit hoher Wahrscheinlichkeit und akzeptablem Rechenaufwand überprüfen, ob eine Zahl eine Primzahl ist oder nicht. Schlagworte sind:

Sieb des Eratosthenes (Erläuterung mit Hilfe eines Javascripts von H.B.Meyer, Faust Gymn. Staufen)
Mersennsche Zahlen / Mersennsche Primzahlen
"Kleiner" Fermat - Carmichaelzahlen, Pseudoprimzahlen
Miller-Rabin-Test (praxisgerechter Primzahltest)

Die meisten Computeralgebrasysteme bieten Funktionen zur Überprüfung von Primzahlen (zum Finden von Primzahlen) an.
Z.B. DERIVE:

PRIME?(m) / PRIME(m) - Überprüfung, ob m eine Primzahl ist
NEXT_PRIME(m), PREVIOUS_PRIME(m) - nächstliegende Primzahlen zur Zahl m

Beispiel:

Überprüfe, ob 1105 eine Primzahl ist! Bestimme die nächsthöhere Primzahl.
Überprüfe, ob die Mersennesche Zahl m = 2^17-1 eine Primzahl ist! Bestimme die nächstgelegene Primzahl kleiner als m.

Primzahlen Derive

Ein echter (allerdings wie alle vollständig sicheren Primzahltests in der Praxis unbrauchbarer) Primzahltest ist der

Satz von Wilson

Satz: p ist genau dann eine Primzahl, wenn gilt.

Übung:

Überprüfe mit Hilfe des Satzes von Wilson die folgenden Zahlen, ob es sich dabei um Primzahlen handelt:
11, 47, 239, 733, 1013

Die vorgestellte Lösung wurde mit DERIVE erstellt.

Das Problem beim Satz von Wilson liegt darin, dass die Faktorielle einer Zahl n (n! = n * (n - 1)! = n * (n-1) * (n-2) * ... * 3 * 2 * 1) bei großen n sehr schnell anwächst und damit ebenfalls gewaltigen Rechenaufwand verursacht.