Pseudoprimzahl
Dieser Artikel enthält mathematische Symbole. Diese werden in der Tabelle mit mathematischen Symbolen erläutert.Eine Pseudoprimzahl ist eine zusammengesetzte, natürliche Zahl, die gewisse Eigenschaften mit Primzahlen gemeinsam hat, selbst aber keine Primzahl ist. Sie wird Pseudoprimzahl bezüglich dieser Eigenschaft genannt.
Die bedeutendste Klasse von Pseudoprimzahlen, um die sich dieser Artikel hauptsächlich dreht, leitet sich vom kleinen Fermat-Satz ab. Die entsprechenden Zahlen werden deshalb auch Fermatsche Pseudoprimzahlen genannt. Eine echte Teilmenge der Fermatschen Pseudoprimzahlen sind die Carmichael-Zahlen.
Eine (Fermatsche) Pseudoprimzahl ist eine natürliche Zahl n, für die bei bestimmten Basen a mit gilt:
Definition einer Pseudoprimzahl
Vorbemerkung zur Kongruenz und zum Modulo
Definition
die aber keine Primzahl ist. Man sagt zu diesen Zahlen auch: "n ist pseudoprim zur Basis a".
Umgekehrt gaukelt die Basis a vor, das n eine Primzahl sei, obwohl sie es nicht ist. Die Basis lügt also.
Eine Carmichael-Zahl ist eine solche Pseudoprimzahl n, dass für jede zu n teilerfremde Basis b mit gilt: .
kleinste Pseudoprimzahl | zu den Basen |
---|---|
15 | 11 |
91 | 3 |
341 | 2 |
2701 | 2, 3 |
29341 | 2, 3, 5, 7, 11 |
162401 | 2, 3, 5, 7, 11, 13 |
Es gibt, absolut gesehen, mehr Pseudoprimzahlen als Primzahlen. Die Mehrheit aller Pseudoprimzahlen ist allerdings nichts besonderes. Die interessanteren Pseudoprimzahlen folgen jetzt.
Im Gegensatz zu den Pseudoprimzahlen zur Basis a (nach Fermat), mit allen a
Die Zahl 341 als Pseudoprimzahl zur Basis 2 wurde 1819 von P.F.Sarrus entdeckt.
Eine ungerade zusammengesetzte natürliche Zahl n wird Eulersche Pseudoprimzahl zur Basis a genannt, wenn a und n teilerfremd zueinander sind und
Für ein und eine ungerade Primzahl p, die nicht teilt bekommt man mit
Aus und
Pseudoprimzahlen nach Fermat zur Basis 2
Alle Pseudoprimzahlen nach Fermat zur Basis 2 (von 341 bis 275887). Die fett gedruckten Zahlen sind Carmichaelzahlen.
341
561
645
1105
1387
1729
1905
2047
2465
2701
2821
3277
4033
4369
4371
4681
5461
6601
7957
8321
8481
8911
10261
10585
11305
12801
13741
13747
13981
14491
15709
15841
16705
18705
18721
19951
23001
23377
25761
29341
30121
30889
31417
31609
31621
33153
34945
35333
39865
41041
41665
42799
46657
49141
49981
52633
55245
57421
60701
60787
62745
63973
65077
65281
68101
72885
74665
75361
80581
83333
83665
85489
87249
88357
88561
90751
91001
93961
101101
104653
107185
113201
115921
121465
123251
126217
129889
129921
130561
137149
149281
150851
154101
157641
158369
162193
162401
164737
172081
176149
181901
188057
188461
194221
196021
196093
204001
206601
208465
212421
215265
215749
219781
220729
223345
226801
228241
233017
241001
249841
252601
253241
256999
258511
264773
266305
271951
272251
272251
275887
Eulersche Pseudoprimzahl
Pseudoprimzahlen zur Basis a nach M. Cipolla, 1904
drei Zahlen n1, n2 und n, wobei n1 und n2 ungerade sind, und n zusammengesetzt ist.
Aus
so das n eine Pseudoprimzahl zur Basis a sein muß.
Da es unendlich viele Primzahlen gibt, muß es demnach auch unendlich viele Pseudoprimzahlen geben.
a
p
n1
n2
n=n1*n2
Faktoren
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
2
11
2047
683
1398101
23*89*683
7
5
2801
2101
5884901
11*191*2801
2
13
8191
2731
22369621
2731*8191
5
7
19531
13021
254313151
29*449*19531
13
5
30941
26521
809977861
11*2411*30941
3
11
88573
44287
3922632451
23*67*661*3851
2
17
131071
43691
5726623061
43691*131071
17
5
88741
78881
6999978821
11*71*101*88741
2
19
524287
174763
91625968981
174763*524287
3
13
797161
398581
317733228541
398581*797161
11
7
1948717
1623931
3164581946527
43*45319*1623931
2
23
8388608
2796203
23456248059221
47*178481*2796203
* Zahlen die fälschlicherweise den Anschein erwecken, die zu testende Zahl (6n+1)*(12n+1) sei eine Primzahl
n
6n+1
12n+1
(6n+1)*(12n+1)
Anz. aller Primzahlen < (6n+1)*(12n+1)
Anz. der lügenden Primzahlbasen*
1
7
13
91
24
8
3
19
37
703
126
56
5
31
61
1891
290
139
6
37
73
2701
393
191
13
79
157
12403
1480
739
16
97
193
18721
2137
1070
Beweise für die Existenz unendlich vieler Pseudoprimzahlen
Weitere Pseudoprimzahlen
Literatur
Weblinks