Pseudoprimzahlen

Eine Pseudoprimzahl ist eine zusammengesetzte, natürliche Zahl, die gewisse Eigenschaften mit Primzahlen gemeinsam hat, selbst aber keine Primzahl ist. Sie wird Pseudoprimzahl bezüglich dieser Eigenschaft genannt.

Hintergrund

Die Pseudoprimzahlen sind aus dem Bedürfnis entstanden, Algorithmen zu finden, die zuverlässig sagen können, ob eine Zahl eine Primzahl ist oder nicht. Da diese Algorithmen nicht perfekt waren, bekam man auch Zahlen, die keine Primzahlen sind, sich aber dennoch, auf diesen speziellen Algorithmus, wie Primzahlen verhalten. Um die Algorithmen zur Primzahlensuche zu optimieren, wurden auch die Pseudoprimzahlen genauer untersucht.
Die bedeutendste Klasse von Pseudoprimzahlen leitet sich vom kleinen Fermat-Satz ab. Die entsprechenden Zahlen werden deshalb auch Fermatsche Pseudoprimzahlen genannt. Eine echte Teilmenge der Fermatschen Pseudoprimzahlen sind die Carmichael-Zahlen.

Arten von Pseudoprimzahlen

Fermatsche Pseudoprimzahlen

Das sind zusammengesetze Zahlen nn, für die zu bestimmten Basen aa mit a>1a > 1 und a≠na \neq n gilt, dass an−1−1≡0mod  na^{n-1} - 1 \equiv 0 \mod n ist.
Zu den Fermatschen Pseudoprimzahlen gehören die Eulerschen Pseudoprimzahlen, die Carmichael-Zahlen und die starken Pseudoprimzahlen.
Eine ungerade zusammengesetzte natürliche Zahl n wird Eulersche Pseudoprimzahl zur Basis a genannt, wenn a und n teilerfremd zueinander sind und
(an)=an−12≡1mod  n \braceNT{\frac{a}{n}} = a^{\frac{n-1}{2}} \equiv 1 \mod n
beziehungsweise
(an)=an−12≡−1mod  n\braceNT{\frac{a}{n}} = a^{\frac{n-1}{2}} \equiv -1 \mod n gilt.
Eine Carmichael-Zahl ist eine solche Pseudoprimzahl nn, so dass für jede zu nn teilerfremde Basis bb mit 1<b<n1 < b < n gilt: bn−1−1≡0mod  nb^{n-1}-1 \equiv 0 \mod n.

Perrinsche Pseudoprimzahlen

Perrinsche Pseudoprimzahlen sind zusammengesetzte Zahlen nn, deren Glied Pn_{n} durch nn teilbar ist, ohne das nn eine Primzahl ist.

Weitere Pseudoprimzahlen

  • Euler-Jacobische Pseudoprimzahlen
    • Euler-Jacobi-Pseudoprimzahlen zur Basis 2
    • Euler-Jacobi-Pseudoprimzahlen zur Basis 3
  • Extrastarke Lucassche Pseudoprimzahlen
  • Fibonaccische Pseudoprimzahlen
  • Frobeniussche Pseudoprimzahlen
  • Lucassche Pseudoprimzahlen
  • Somer-Lucassche Pseudoprimzahlen
  • Starke Frobeniussche Pseudoprimzahlen
  • Starke Lucassche Pseudoprimzahlen
 
 

Es ist unglaublich, wie unwissend die studirende Jugend auf Universitäten kommt, wenn ich nur 10 Minuten rechne oder geometrisire, so schläft 1/4 derselben sanft ein.

Georg Christoph Lichtenberg

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Pseudoprimzahl aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Elementare Zahlentheorie