Fermatsche Pseudoprimzahl

Eine natürliche Zahl n wird Fermatsche Pseudoprimzahl (zur Basis a) genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu n teilerfremde Basis a wie eine Primzahl verhält: wenn nämlich die Kongruenz

${\displaystyle a^{n-1}\equiv 1\mod n}$

für die zu n teilerfremde Zahl a erfüllt ist.

Anders ausgedrückt muss n die Differenz ${\displaystyle a^{n-1}-1}$ teilen.

Zum Beispiel ist 341 eine Fermatsche Pseudoprimzahl zur Basis 2, da 341 ein Teiler von ${\displaystyle 2^{340}-1}$, aber aufgrund 341=11·31 nicht prim ist.

Eine Fermatsche Pseudoprimzahl ist eine Pseudoprimzahl in Bezug auf das Kriterium des kleinen Fermatschen Satzes, einem Spezialfall des Satzes von Lagrange.

Dieses Kriterium wird beim Fermatschen Primzahltest verwendet. Wie der Name besagt, ist eine „Pseudoprimzahl“ eine Zahl, die gewisse Eigenschaften mit Primzahlen gemeinsam hat, aber selbst sensu stricto keine Primzahl ist. Eine Zahl > 1, gilt als prim, wenn sie nur die Teiler 1 oder sich selbst besitzt, also die nur durch sich selbst und 1, ohne Rest, teilbar ist.

Anders gesagt, bei dem Versuch einen zuverlässigen Algorithmus (einen sogenannten Primzahltest) zu finden, der eine eindeutige Aussage darüber macht, ob eine Zahl eine Primzahl ist oder nicht, zeigte sich aber, dass die Algorithmen nicht zuverlässig sind und Zahlen generiert werden, die keine Primzahlen sind, sich aber dennoch, auf einen speziellen Algorithmus hin bezogen, wie Primzahlen verhielten (Primalität).

Eine Fermatsche Pseudoprimzahl zur Basis a ist eine zusammengesetzte, natürliche Zahl n, für die

${\displaystyle a^{n-1}\equiv 1\mod n}$

gilt. In Bezug auf die Basis a verhält sich n also wie eine Primzahl.

Beispiel: Die Zahl 91 ist eine Fermatsche Pseudoprimzahl bezüglich der Basen 17, 29 und 61, da ${\displaystyle 17^{90}-1}$, ${\displaystyle 29^{90}-1}$ und ${\displaystyle 61^{90}-1}$ durch 91 teilbar sind. Obwohl die Zahl 91 keine Primzahl ist (91 = 7·13), erfüllt sie also für einige a den kleinen Fermatschen Satz.

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

Ist n eine Fermatsche Pseudoprimzahl zur Basis a, so auch zur Basis a^k und zu a + kn (k > 1), sowie - falls n ungerade ist und a < n - zur Basis n - a.

Zu jeder Basis gibt es unendlich viele Fermatsche Pseudoprimzahlen. Es folgt eine Tabelle der kleinsten Fermatschen Pseudoprimzahlen (zumindest kleiner gleich 10000) zur Basis a:

Für Fermatsche Pseudoprimzahlen zu den Basen 12 bis 100 siehe (Folge A020140 in OEIS) bis (Folge A020228 in OEIS). Für alle weiteren Basen bis a = 165 siehe Pseudoprimzahlen: Tabelle Fermatsche Pseudoprimzahlen auf Wikibooks.

Die sieben fett gedruckten Zahlen 561, 1105, 1729, 2465, 2821, 6601, 8911 sind Fermatsche Pseudoprimzahlen zu allen teilerfremden Basen a. Wenn sie bei gewissen Basen a nicht auftauchen, dann deswegen, weil sie zu diesen Basen a nicht teilerfremd sind (zum Beispiel taucht 561 bei der Basis a = 6 nicht auf, weil ${\displaystyle \operatorname {ggT} (6,561)=3\not =1}$ ist).

Zahlen, die Fermatsche Pseudoprimzahlen zu allen teilerfremden Basen a sind, nennt man Carmichael-Zahlen.

Es gilt:

Jede zu a teilerfremde Carmichael-Zahl ist auch gleichzeitig eine Fermatsche Pseudoprimzahl zur Basis a. Die Umkehrung gilt nicht, das heißt, es gibt Fermatsche Pseudoprimzahlen zur Basis a, die nicht gleichzeitig Carmichael-Zahlen sind.

Mathematisch formuliert man den obigen Sachverhalt mittels Mengenschreibweise wie folgt:

{zu a teilerfremde Carmichael-Zahl} ${\displaystyle \subsetneqq }$ {Fermatsche Pseudoprimzahl zur Basis a}

Michele Cipolla konstruierte im Jahr 1904 auf folgende Weise unendlich viele Fermatsche Pseudoprimzahlen zu jeder Basis:

Für jedes a > 1 und jede ungerade Primzahl p, die ${\displaystyle a(a^{2}-1)}$ nicht teilt, ist

${\displaystyle n={\frac {a^{p}-1}{a-1}}\cdot {\frac {a^{p}+1}{a+1}}}$

eine Fermatsche Pseudoprimzahl zur Basis a.^[1] Da es unendlich viele Primzahlen gibt, muss es demnach auch zu jeder Basis unendlich viele Fermatsche Pseudoprimzahlen geben. Beispiele:

• Richard Crandall, Carl Pomerance: Prime Numbers. A Computational Perspective. 2nd Edition. Springer, New York NY u. a. 2005, ISBN 0-387-25282-7.

Wikibooks: Fermatsche Pseudoprimzahlen zu einer bestimmten Basis α – Lern- und Lehrmaterialien

• Eric W. Weisstein: Fermat Pseudoprime. MathWorld
• Final Answers Modular Arithmetic

1. ↑ Zum Beweis siehe G. H. Hardy, E. M. Wright: An introduction to the theory of numbers, Oxford University Press, 2005, Seite 90.