Menu:


Primzahlen

Kundennahe Lösungen für Industrie und Privatpersonen ... [COM2U]

Primzahlen | Primfaktoren | Primzahl-Tests

Primzahlen

Eine Primzahl ist eine Zahl die nur durch eins oder sich selbst geteilt werden kann.

Primzahlen sind die elementaren Bausteine der natürlichen Zahlen, trotzdem gehören sie zu den willkürlichsten Objekten der Mathematik

Faktorisierung natürlicher Zahlen
Die Multiplikation großer Zahlen ist eine Fleißaufgabe. Die Faktorisierung großer Zahlen ist dagegen um einiges komplexer. Es sind derzeit keine effizienten Verfahren zur Primfaktorzerlegung beliebiger Zahlen bekannt. Dazu müssen umständlich alle einzelnen Primzahlen ermittelt werden. Wenn Geheimdienste ein solches Verfahren gefunden hätten würden sie dies wohl nicht veröffentlichen. Es gibt Staaten die es ihren Bürgern im Prinzip verbieten, zwei große Primzahlen miteinander zu multiplizieren und das Ergebnis der Multiplikation zu veröffentlichen, ohne dem Staat die Primfaktoren vorher zu verraten. Mit Primzahlen können Daten verschlüsselt werden. Nur wem es gelingt die Primfaktorzerlegung eines solchen Primzahlproduktes zu ermitteln, kann die Daten rekonstruieren ohne den Schlüssel zu besitzen.

Man sagte, es könne von einer beliebig großen Zahl ohne weiteres feststellen, ob sie eine Primzahl sei oder nicht.
Diese Geschichte wurde lange Zeit in das Reich der Fabel verwiesen. Aber im April 1992 entdeckten italienische Archäologen bei Ausgrabungen die Ruinen der Akademie des Pythagoras - und darin die Überreste einer riesigen Maschine, die einst mit Wasserkraft angetrieben worden war. Sie baten einige Ingenieure um Unterstützung, und im Laufe der nächsten Jahre wurde klar, dass es sich um die Reste eines gewaltigen mechanischen Computers handelte - ähnlich der "Analytical Engine", die Charles Babbage allerdings erst mehr als 2300 Jahre nach Pythagoras entwarf. Mit Hilfe des Orakels und Ihrer Unterstützung sollte es nun möglich sein, ein altes mathematisches Rätsel seiner Lösung näher zu bringen: Nachdem Fermats letzter Satz vor einigen Jahren bewiesen wurde, ist die Goldbach-Vermutung eines der größten verbleibenden Probleme der Mathematik.
Christian Goldbach, ein Lehrer des jungen Zaren Peter II, äußerte 1742 in einem Brief an den großen Mathematiker Leonhard Euler die Annahme, dass sich jede gerade Zahl, die größer als zwei ist, als Summe zweier Primzahlen darstellen lässt, Tatsächlich wurde diese Hypothese inzwischen bis 100 Millionen (108) überprüft und bestätigt. Ein allgemeiner Beweis ist weder dem genialen Euler noch irgendeinem anderen seither gelungen. Ein Gegenbeispiel wurde bisher aber auch noch nicht gefunden.
Dank des Primzahl-Orakels können Sie nun einfach und schnell beliebige gerade Zahlen bis zu 10 Billionen (1013) testen.

Primzahl-Tests
Ein einfacher Primzahltest beruht auf dem kleinen Satz von Fermat:
.
"Wenn p eine Primzahl ist und a und p teilerfremd sind, ist a hoch (p-1) kongruent zu 1 modulo p."
Falls also a hoch (p - 1) modulo p ungleich 1 ist, kann p keine Primzahl sein. Da hier mit Kongruenzen modulo p gerechnet wird, handelt es sich um einen recht effizienten Algorithmus. Die Potenz von a kann mit einem schnellen Verfahren berechnet werden (binäres Potenzieren; beruht auf der Assoziativität der Multiplikation im betrachteten Restklassenring).
Im einfachsten Fall führt man den Test für a = 2 durch. Leider handelt es sich dann um kein hinreichendes Kriterium, denn es gibt zusammengesetzte Zahlen p > 1 für die die Kongruenz erfüllt ist. Zwei Beispiele sind die Carmichael-Zahlen 561 (3 * 11 * 17) und 1729 (7 * 13 * 19).
Definiert man eine partielle Funktion b mit


gilt b(561) > 2. Einige Werte von b(p) gibt die folgende Tabelle wieder:


Im Jahre 1919 stellte sich der Inder Srinivasa Ramanujan folgende Frage: Wie viele Möglichkeiten mag es geben, eine natürliche Zahl, etwa die 6, als Summe von natürlichen Zahlen zu schreiben?


Die Lösung für die 6 ist simpel. Von der Zerlegung in lauter Einsen 1+1+1+1+1 +1=6 über 2+2+2=6 bis zur 6 allein gibt es genau 11 verschiedene Möglichkeiten. Sehr schnell kam Ramanujan, zahlenbesessen wie viele seiner Landsleute, allerdings zu einer Vielzahl von Varianten, als er eine Liste der Zerlegungen der ersten 200 Zahlen berechnete. Die 200 lässt sich, so fand er ohne Computerhilfe heraus, in genau 3972999029388 Additions-Varianten aufspalten.


Intuitiv erkannte der geniale Mathematiker, den viele als den Gauß von Indien bezeichnen, bestimmte Gesetzmäßigkeiten in seiner Liste (siehe Grafik).


Beginnt man bei der Zahl 5 und springt immer um 7 Stellen - die Anzahl der möglichen Summen - weiter nach oben auf der Zahlenleiter, so landet man stets bei Zahlen, deren Zerlegungsanzahlen Vielfache der Sprungzahl 7 sind. Die 12 zum Beispiel hat 77 Zerlegungen, die 19 lässt sich auf 490 verschiedene Arten aufspalten und die 26 bereits auf 2436 Arten.

(Quelle: Geo, Mathematik: Zahlenspalterei, 11/2000)