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 <math>a^{q-1} \equiv 1 (\mod q)</math> gilt.

Übrigens: Die PlusPedia ist NICHT die Wikipedia. Wir sind ein gemeinnütziger Verein, PlusPedia ist werbefrei. Wir freuen uns daher über eine kleine Spende!

1 Einschränkung

Es ist von Vorteil, wenn man den Bereich der Basen a so einschränkt, das <math> 2 \le a \le q-2</math> gilt, da für jede ungerade Zahl q <math>(q-1)^{q-1} \eqiv 1 (\mod q)</math> gilt.

2 Eigenschaften

Wenn eine natürliche Zahl a eine Basis zu einer ungeraden fermatschen Pseudoprimzahl q ist, so ist <math>a' = q-a</math> 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 <math> n \ge 0</math> 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, ...}.

3 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

4 Weblinks

• Final Answers Modular Arithmetic
• Ergänzungen und Irrtümer zu dem Buch "The new Book of Prime Number Records" von Paolo Ribenboim
• Wikipedia-Artikel