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.

Erläuterungen

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).

Definition

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.

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

Tabelle mit Fermatschen Pseudoprimzahlen

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

a	Fermatsche Pseudoprimzahlen n zur Basis a	OEIS-Folge
1	4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, … (jede zusammengesetzte ganze Zahl)	(Folge A002808 in OEIS)
2	341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, …	(Folge A001567 in OEIS)
3	91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, 10585, …	(Folge A005935 in OEIS)
4	15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8481, 8695, 8911, 9061, 9131, 9211, 9605, 9919, 10261, …	(Folge A020136 in OEIS)
5	4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, 11041, …	(Folge A005936 in OEIS)
6	35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713, 6533, 6601, 8029, 8365, 8911, 9331, 9881, 10585, …	(Folge A005937 in OEIS)
7	6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, …	(Folge A005938 in OEIS)
8	9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1105, 1281, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1785, 1905, 2047, 2169, 2465, 2501, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097, 4369, 4371, 4641, 4681, 4921, 5461, 5565, 5963, 6305, 6533, 6601, 6951, 7107, 7161, 7957, 8321, 8481, 8911, 9265, 9709, 9773, 9881, 9945, 10261, …	(Folge A020137 in OEIS)
9	4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, 1541, 1729, 1891, 2465, 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601, 6643, 7081, 7381, 7913, 8401, 8695, 8744, 8866, 8911, 10585, …	(Folge A020138 in OEIS)
10	9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187, 4521, 5461, 6533, 6541, 6601, 7107, 7471, 7777, 8149, 8401, 8911, 10001, 11111, …	(Folge A005939 in OEIS)
11	10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921, 5041, 5185, 6601, 7869, 8113, 8170, 8695, 8911, 9730, 10585, …	(Folge A020139 in OEIS)
…	…

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}

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 ${\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:

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

Einzelnachweise

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

V – D

Primzahl­mengen

formelbasiert	Carol ((2^n − 1)^2 − 2) | Doppelte Mersenne (2^2p − 1 − 1) | Fakultät (n! ± 1) | Fermat (2^2n + 1) | Kubisch (x^3 − y^3)/(x − y) | Kynea ((2^n + 1)^2 − 2) | Leyland (x^y + y^x) | Mersenne (2^p − 1) | Mills (A^3n) | Pierpont (2^u⋅3^v + 1) | Primorial (pn# ± 1) | Proth (k⋅2^n + 1) | Pythagoreisch (4n + 1) | Quartisch (x^4 + y^4) | Thabit (3⋅2^n − 1) | Wagstaff ((2^p + 1)/3) | Williams ((b-1)⋅b^n − 1) | Woodall (n⋅2^n − 1)
Primzahlfolgen	Bell | Fibonacci | Lucas | Motzkin | Pell | Perrin
eigenschaftsbasiert	Elitär | Fortunate | Gut | Glücklich | Higgs | Hochkototient | Isoliert | Pillai | Ramanujan | Regulär | Stark | Stern | Wall–Sun–Sun | Wieferich | Wilson
basis­abhängig	Belphegor | Champernowne | Dihedral | Einzigartig | Fröhlich | Keith | Lange | Minimal | Mirp | Permutierbar | Primeval | Palindrom | Repunit-Primzahl ((10^n − 1)/9) | Schwach | Smarandache–Wellin | Strobogrammatisch | Tetradisch | Trunkierbar | Zirkular
basierend auf Tupel	Ausbalanciert (p − n, p, p + n) | Chen | Cousin (p, p + 4) | Cunningham (p, 2p ± 1, …) | Drilling (p, p + 2 oder p + 4, p + 6) | Konstellation | Sexy (p, p + 6) | Sichere (p, (p − 1)/2) | Sophie Germain (p, 2p + 1) | Vierling (p, p + 2, p + 6, p + 8) | Zwilling (p, p + 2) | Zwillings-Bi-Kette (n ± 1, 2n ± 1, …)
nach Größe	Titanisch (1.000+ Stellen) | Gigantisch (10.000+ Stellen) | Mega (1.000.000+ Stellen) | Beva (1.000.000.000+ Stellen)