Pseudoprimzahl

Dieser Artikel enthält mathematische Symbole, die in der Tabelle mit mathematischen Symbolen erklärt werden.

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 leitet sich vom Kleinen Fermatschen Satz ab. Die entsprechenden Zahlen werden deshalb Fermatsche Pseudoprimzahlen genannt. Eine echte Teilmenge der Fermatschen Pseudoprimzahlen sind die Carmichael-Zahlen.

Pseudoprimzahl Definition

Eine (Fermatsche) Pseudoprimzahl ist eine natürliche Zahl n, für die bei bestimmten Basen b mit

b\geq 2

gilt:

b^{n-1}-1\equiv 0\mod n

,

die aber keine Primzahl ist. Man sagt zu diesen Zahlen auch: "n ist pseudoprim zur Basis b".

Die kleinste Pseudoprimzahl ist die Zahl 15. Sie ist pseudoprim zur Basis 11. Die kleinste Pseudo-Primzahl zur Basis 2 ist die Zahl 341.
Eine Carmichael-Zahl ist eine solche Pseudoprimzahl n, das für jede zu n teilerfremde Basis b mit $1<b<n$ gilt: $b^{n-1}-1\equiv 0\mod n$ .

Beispiele

kleinste Pseudoprimzahl	zu den Basen
15	11
341	2
2701	2, 3
29341	2, 3, 5, 7, 11
162401	2, 3, 5, 7, 11, 13

Liste aller Pseudoprimzahlen bis 1729¹

Es gibt, absolut gesehen, mehr Pseudoprimzahlen als Primzahlen. Die Mehrheit aller Pseudoprimzahlen ist allerdings nichts besonderes. Die unten stehende Tabelle steht, als Ausschnitt, stellvertretend für die Gesamtheit aller Pseudoprimzahlen. Die interessanteren Pseudoprimzahlen werden weiter unten behandelt.

15	21	25	33	35	45	49	52	57	65	66	69	70	77	85	87	91	93	99
105	111	117	121	123	124	130	133	135	143	145	147	148	153	154	155	159	161	165
169	171	175	176	185	186	187	190	195	205	208	217	221	225	231	237	238	244	245
246	247	249	255	259	261	265	267	268	273	275	276	285	286	287	289	291	292	297
301	305	310	315	316	322	325	329	333	335	339	341	343	344	345	351	357	361	363
364	365	366	369	370	371	375	377	385	388	391	393	396	399	403	405	406	412	415
417	418	425	426	427	429	430	435	436	437	441	445	448	451	455	459	465	469	471
475	477	481	483	485	493	495	496	505	506	507	511	513	519	525	527	529	532	533
537	539	545	549	553	555	556	559	561	565	568	573	581	585	589	592	595	597	598
603	604	605	606	609	615	616	625	627	629	633	635	637	638	645	646	649	651	652
657	663	665	670	671	676	679	682	685	687	688	689	693	697	699	700	703	705	711
715	717	721	724	725	726	730	735	741	742	745	749	753	754	759	763	765	772	775
777	781	782	785	786	790	793	795	801	803	804	805	806	813	817	819	825	826	833
836	837	841	843	844	845	847	855	861	865	867	868	871	873	874	875	879	885	889
891	895	897	901	903	904	905	906	909	910	913	916	921	925	931	945	946	949	952
957	959	961	965	969	970	973	975	976	981	985	987	988	993	994	999	1001	1005	1011
1015	1016	1017	1023	1025	1027	1030	1035	1036	1037	1044	1045	1053	1055	1056	1057	1065	1066	1068
1071	1073	1075	1077	1078	1085	1086	1090	1095	1099	1101	1102	1105	1106	1107	1111	1113	1116	1120
1121	1125	1128	1131	1132	1133	1136	1137	1141	1145	1146	1147	1155	1157	1159	1161	1162	1165	1166
1173	1175	1177	1179	1183	1185	1189	1195	1197	1204	1205	1209	1215	1216	1221	1222	1225	1228	1233
1235	1239	1241	1245	1247	1251	1257	1261	1265	1267	1271	1273	1275	1281	1285	1288	1293	1295	1305
1309	1311	1313	1315	1317	1325	1329	1333	1335	1339	1341	1349	1351	1353	1355	1357	1365	1369	1377
1385	1387	1391	1393	1395	1403	1405	1407	1411	1413	1417	1419	1425	1431	1435	1441	1443	1445	1449
1455	1463	1465	1469	1473	1477	1485	1491	1495	1497	1501	1505	1513	1515	1516	1517	1519	1521	1525
1527	1533	1535	1537	1539	1541	1545	1547	1548	1551	1552	1558	1561	1562	1565	1573	1575	1581	1585
1591	1593	1595	1599	1603	1605	1611	1615	1617	1625	1629	1631	1635	1641	1643	1645	1647	1649	1651
1653	1655	1659	1661	1665	1675	1681	1683	1685	1687	1695	1705	1717	1725	1729
fett	Carmichel-Zahlen
grün	Quadratzahlen
rot	Pseudoprimzahlen der Form p₁p₂p₃

(1) Für alle aufgeführten Pseudoprimzahlen n gilt, das sie mindestens zu einer beliebigen Primzahl p für die 1 < p < n gilt
pseudoprim sind.

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, das auch $n\equiv 1\mod 2p$ ist.
Aus $a^{2p}\equiv 1\mod n$ folgt, daß $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	n₁	n₂	n=n₁*n₂	Faktoren
2	5	31	11	341	11*31
2	7	127	43	5461	43*127
3	5	121	61	7381	111161
3	7	1093	547	597871	547*1093
2	11	2047	683	1398101	2389683
7	5	2801	2101	5884901	111912801
2	13	8191	2731	22369621	2731*8191
5	7	19531	13021	254313151	2944919531
13	5	30941	26521	809977861	11241130941
3	11	88573	44287	3922632451	2367661*3851
2	17	131071	43691	5726623061	43691*131071
17	5	88741	78881	6999978821	1171101*88741
2	19	524287	174763	91625968981	174763*524287
3	13	797161	398581	317733228541	398581*797161
11	7	1948717	1623931	3164581946527	43453191623931
2	23	8388608	2796203	23456248059221	471784812796203

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

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

The New Book of Prime Number Records, Paolo Ribenboim, Springer Verlag 1996, ISBN 0-387-94457-5

Links

Final Answers Modular Arithmetic