Fermatsche Pseudoprimzahl

Eine fermatsche Pseudoprimzahl ist eine zusammengesetze, natürliche Zahl q zu der es wenigstens eine natürliche Zahl a mit a > 1 gibt, so das $a^{q-1}\equiv 1(modq)$ gilt.

Einschränkung

Es ist von Vorteil, wenn man den Bereich der Basen a so einschränkt, das $2\le a\le q-2$ gilt, da für jede ungerade Zahl q Fehler beim Parsen (Unbekannte Funktion „\eqiv“): {\displaystyle (q-1)^{q-1} \eqiv 1 (\mod q)} gilt.

Eigenschaften

Wenn eine natürliche Zahl a eine Basis zu einer ungeraden fermatschen Pseudoprimzahl q ist, so ist $a^{\prime }=q-a$ ebenfalls eine Basis zu der fermatschen Pseudoprimzahl q.

Beispiel:

15 ist eine fermatsche Pseudoprimzahl Zur Basis 4. Also ist 15 auch eine fermatsche Pseudoprimzahl zur Basis (15-4) = 11

Wenn eine natürliche Zahl a eine Basis zu einer fermatschen Pseudoprimzahl q ist, so sind alle natürlichen Zahlen der Form n*q+a mit $n\ge 0$ Basen zu der fermatschen Pseudoprimzahl q

Beispiel:

15 ist eine fermatsche Pseudoprimzahl zu den Basen 4 und 11. Demnach ist 15 eine fermatsche Pseudoprimzahl zu den Basen 15n+4 {4, 19, 34, 49, 64, 79, ...} und 15n+11 {11, 26, 41, 56, 71, ...}

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
• Prime Numbers - A Computational Cerspective, Second Edition, Richard Crandall & Carl Pomerance, Springer Verlag 2005, ISBN 0-387-25282-7

Weblinks

• Final Answers Modular Arithmetic
• http://web.archive.org/web/20050315104907/http://www.utm.edu/research/primes/notes/errata/index.html Ergänzungen und Irrtümer] zu dem Buch "The new Book of Prime Number Records" von Paolo Ribenboim
• Wikipedia-Artikel