Pseudoprimzahl

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.

Definition einer Pseudoprimzahl

Vorbemerkung zur Kongruenz und zum Modulo

$a\equiv b\mod c$ wird "a ist kongruent zu b in Bezug auf modulo von c" gesprochen.

Definition

Eine (Fermatsche) Pseudoprimzahl ist eine natürliche Zahl n, für die bei bestimmten Basen a mit $2\leq a<n$ gilt:

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

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 $1<b<n$ gilt: $b^{n-1}-1\equiv 0\mod n$.

Die kleinsten Pseudoprimzahlen zu bestimmten Primbasen

Die kleinste Pseudoprimzahl

• ist die Zahl 15. Sie ist pseudoprim zur Basis 11.
  
• zur Basis 3 ist die Zahl 91. Sie ist zu insgesamt 8 Primbasen pseudoprim.
  
• zur Basis 2 ist die Zahl 341.
  
• die sowohl zur Basis 2, als auch zur Basis 3 pseudoprim ist,ist die Zahl 2701.
  

Beispiele für kleinste Pseudoprimzahlen

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.

Pseudoprimzahlen nach Fermat zur Basis 2

Im Gegensatz zu den Pseudoprimzahlen zur Basis a (nach Fermat), mit allen a<n (selbst mit der Einschränkung, das die Basis a eine Primzahl sein muß), sind die Pseudoprimzahlen nach Fermat zur Basis 2 rar gesät:

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

Alle Pseudoprimzahlen nach Fermat zur Basis 2 (von 341 bis 275887). Die fett gedruckten Zahlen sind Carmichaelzahlen.

Die Zahl 341 als Pseudoprimzahl zur Basis 2 wurde 1819 von P.F.Sarrus entdeckt.

Eulersche Pseudoprimzahl

Eine ungerade zusammengesetzte natürliche Zahl n wird Eulersche Pseudoprimzahl zur Basis a genannt, wenn a und n teilerfremd zueinander sind und

$\left({\frac {a}{n}}\right)=a^{\frac {n-1}{2}}\equiv 1\mod n$ beziehungsweise $\left({\frac {a}{n}}\right)=a^{\frac {n-1}{2}}\equiv -1\mod n$ gilt.

Pseudoprimzahlen zur Basis a nach M. Cipolla, 1904

Für ein $a\geq 2$ und eine ungerade Primzahl p, die $a(a^{2}-1)$ nicht teilt bekommt man mit

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

drei Zahlen n₁, n₂ und n, wobei n₁ und n₂ ungerade sind, und n zusammengesetzt ist.

Aus $n_{1}\equiv 1\mod 2p$ und $n_{2}\equiv 1\mod 2p$

folgt, dass auch $n\equiv 1\mod 2p$ ist.

Aus $a^{2p}\equiv 1\mod n$

folgt, dass $a^{n-1}\equiv 1\mod n$ ist,

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

Zeisel-Zahlen

Unter den Zeisel -Zahlen finden sich Pseudoprimzahlen:

a	b	zn
1	2	105	3*5*7
1	6	1729	7*13*19
2	3	1885	5*13*29
3	2	4505	5*17*53
2	5	5719	7*19*43
2	9	24211	11*31*71

Pseudoprimzahlen der Form (6n+1)*(12n+1)

Ähnlich den Carmichael-Zahlen nach Chernick, die der Form (6n+1)*(12n+1)*(18n+1) entsprechen, scheinen die Pseudoprimzahlen der Form (6n+1)*(12n+1) eine besondere Bedeutung zu haben. Abgesehen von den Carmichael-Zahlen, haben sie die meisten Primbasen:

n	6n+1	12n+1	(6n+1)*(12n+1)	AaP	AalP	Ratio
1	7	13	91	24	8	33,33%
3	19	37	703	126	56	44,44%
5	31	61	1891	290	139	47,93%
6	37	73	2701	393	191	48,60%
13	79	157	12403	1480	739	49,93%
16	97	193	18721	2137	1070	50,07%

ApP = Anzahl aller Primzahlen kleiner als (6n+1)*(12n+1)

AalP = Anzahl der lügenden Primzahlbasen*

^* Primzahlen, die fälschlicherweise den Anschein erwecken, die zu testende Zahl (6n+1)*(12n+1) sei eine Primzahl

Beweise für die Existenz unendlich vieler Pseudoprimzahlen

• Beweis von E. Malo 1903
• Beweis von M. Cipolla 1904

Weitere Pseudoprimzahlen

• Euler-Jacobische Pseudoprimzahlen
  • Euler-Jacobi Pseudoprimzahlen zur Basis 2
  • Euler-Jacobi Pseudoprimzahlen zur Basis 3
• Extrastarke Lucas'sche Pseudoprimzahlen
• Fibonaccische Pseudoprimzahlen
• Frobenius'sche Pseudoprimzahlen
• Lucas'sche Pseudoprimzahlen
• Perrinsche Pseudoprimzahlen
• Somer-Lucas'sche Pseudoprimzahlen
• Starke Frobenius'sche Pseudoprimzahlen
• Starke Lucas'sche Pseudoprimzahlen
• Starke Pseudoprimzahlen

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

Weblinks

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