Pseudoprimzahl

Eine Pseudoprimzahl ist eine 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.

Die Carmichael-Zahlen sind eine spezielle Art von Pseudoprimzahlen.

Definition

Eine Pseudoprimzahl ist eine natürliche Zahl n, für die bei bestimmten Basen $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.

Beispiele

Pseudoprimzahl	Basis
15	11
341	2
2701	2, 3
29341	2, 3, 5, 7, 11
162401	2, 3, 5, 7, 11, 13

Liste aller Pseudoprimzahlen bis 3.000¹

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	1240	1241
1245	1246	1247	1251	1252	1257	1258	1261	1265	1267	1270	1271	1273	1275	1276	1281
1285	1288	1293	1295	1300	1305	1309	1311	1313	1315	1317	1325	1329	1330	1333	1335
1339	1341	1349	1351	1353	1355	1357	1365	1369	1377	1378	1385	1386	1387	1390	1391
1393	1395	1403	1405	1407	1411	1413	1414	1417	1419	1425	1426	1431	1435	1441	1443
1444	1445	1446	1449	1450	1455	1456	1462	1463	1465	1469	1473	1476	1477	1480	1485
1491	1492	1495	1496	1497	1501	1505	1506	1510	1513	1515	1516	1517	1519	1521	1525
1527	1533	1535	1537	1539	1541	1545	1547	1548	1551	1552	1558	1561	1562	1565	1573
1575	1576	1581	1585	1586	1588	1591	1593	1595	1599	1603	1605	1606	1611	1612	1615
1617	1624	1625	1626	1629	1630	1631	1635	1636	1641	1643	1645	1647	1648	1649	1651
1653	1655	1659	1661	1665	1672	1675	1681	1683	1684	1685	1686	1687	1688	1690	1695
1702	1705	1708	1716	1717	1725	1729	1731	1736	1737	1738	1743	1744	1745	1749	1750
1755	1756	1757	1763	1765	1767	1768	1769	1770	1771	1773	1779	1781	1785	1786	1791
1794	1795	1798	1803	1807	1809	1810	1813	1815	1821	1825	1826	1827	1828	1833	1834
1841	1843	1845	1846	1849	1853	1854	1855	1856	1859	1865	1869	1875	1876	1881	1885
1886	1887	1891	1897	1900	1905
2047	2101	2149
2257	2353	2465	2665	2701	2806	2821	3277	3281	3367	3605	3751	3991	4005	4033	4123

(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.
Die Carmichael-Zahlen sind fett hervorgehoben

Weitere Pseudoprimzahlen

• Eulersche Pseudoprimzahlen
• Eulersche Pseudoprimzahlen zur Basis 2
• 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