Fermatsche Pseudoprimzahl

Eine natürliche Zahl n wird Fermatsche Pseudoprimzahl 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

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

erfüllt ist.

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

Zum Beispiel ist 341 eine Fermatsche Pseudoprimzahl zur Basis 2, da 341 ein Teiler von $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. Dieses Kriterium wird beim Fermatschen Primzahltest verwendet.

Definition

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

$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 $17^{90}-1$, $29^{90}-1$ und $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.

Unterklassen und Eigenschaften

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 (mit a < n) so auch zur Basis n - a, sowie zu a^k und zu a + kn (k > 1).

Die Folgen der Fermatschen Pseudoprimzahlen zu den Basen 2, 3 und 5

Zu jeder Basis gibt es unendlich viele Fermatsche Pseudoprimzahlen. Diese lauten beispielsweise

Basis 2

341, 561, 645, 1105, 1387, 1729, 1905, … (Folge A001567 in OEIS).

Basis 3

91, 121, 286, 671, 703, 949, 1105, 1541, 1729, … (Folge A005935 in OEIS).

Basis 5

4, 124, 217, 561, 781, 1541, 1729, 1891, … (Folge A005936 in OEIS).

Konstruktion unendlich vieler Fermatscher Pseudoprimzahlen zu jeder Basis

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 $a(a^2-1)$ nicht teilt, ist

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

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

a	p	1. Faktor	2. Faktor	n	Primfaktorzerlegung
2	5	31	11	341	11·31
2	7	127	43	5461	43·127
3	5	121	61	7381	11·11·61
3	7	1093	547	597871	547·1093
7	5	2801	2101	5884901	11·191·2801

Literatur

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

Weblinks

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