Pseudoprimzahl

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 bezogen, wie Primzahlen verhalten. Um die Algorithmen zur Primzahlensuche zu optimieren, wurden auch die Pseudoprimzahlen genauer untersucht.

Die bedeutendste Klasse von Pseudoprimzahlen, um die sich dieser Artikel hauptsächlich dreht, 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 n, für die zu bestimmten Basen a mit $2\leq a\leq n-2$ und $\operatorname {ggT} (a,n)=1$ gilt, dass $a^{n-1}\equiv 1\mod n$ ist.

Zu den Fermatschen Pseudoprimzahlen gehören die Eulerschen Pseudoprimzahlen, die Carmichael-Zahlen und die starken Pseudoprimzahlen.

• Eulersche Pseudoprimzahl

Eine ungerade zusammengesetzte natürliche Zahl n wird Eulersche Pseudoprimzahl zur Basis a genannt, wenn a und n teilerfremd zueinander sind und

$\left({\frac {a}{n}}\right)=a^{\frac {n-1}{2}}\equiv 1\mod n$ beziehungsweise $\left({\frac {a}{n}}\right)=a^{\frac {n-1}{2}}\equiv -1\mod n$ gilt.

• Carmichael-Zahl

Eine Carmichael-Zahl ist eine solche Pseudoprimzahl n, so dass für jede zu n teilerfremde Basis b mit $1<b<n$ gilt: $b^{n-1}-1\equiv 0\mod n$.

Perrinsche Pseudoprimzahlen

Perrinsche Pseudoprimzahlen sind zusammengesetzte Zahlen n, deren Glied P_n durch n teilbar ist, ohne das n 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

Beweise für die Existenz unendlich vieler Pseudoprimzahlen

• Beweis von E. Malo 1903
• Beweis von Michele Cipolla 1904

Literatur

• Carl Pomerance: The Search for Prime Numbers in: Scientific American, December 1982
• Carl Pomerance: Primzahlen im Schnelltest in: Spektrum der Wissenschaft, Februar 1983 S. 80-92. (Es handelt sich um die Übersetzung des vorerwähnten Artikels) mit Foto eines Nachbaus von Lehmers Fahrradkettencomputers von 1926!
• The New Book of Prime Number Records, Paolo Ribenboim, Springer Verlag 1996, ISBN 0-387-94457-5

Weblinks

• wikisource:Pseudoprime numbers
• Final Answers Modular Arithmetic
• Ergänzungen und Irrtümer zu dem Buch "The new Book of Prime Number Records" von Paolo Ribenboim