„Pseudoprimzahl“ – Versionsunterschied

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

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 50.000

15	21	25	45	91	124	341	561	645	671	703	781	793	817	949	1099
1105	1111	1228	1305	1330	1387	1541	1729	1785	1825	1885	1891	1905	2047	2101	2149
2257	2353	2465	2665	2701	2806	2821	3277	3281	3367	3605	3751	3991	4005	4033	4123
4187	4369	4371	4525	4577	4681	4825	4912	4921	4961	5028	5041	5149	5185	5365	5461
5551	5565	5611	5662	5731	5833	6601	6697	7107	7171	7381	7449	7813	7869	7957	8029
8113	8170	8321	8401	8481	8695	8841	8911	9577	9637	9730	9881	10225	10261	10308	10585
10621	11011	11041	11305	11476	11521	12025	12403	12621	12673	12801	13019	13021	13333	13345	13461
13665	13685	13741	13747	13833	13981	14089	14383	14491	14521	14981	15051	15203	15457	15505	15709
15751	15805	15841	16297	16471	16531	16705	16725	16806	17711	17767	17803	18705	18721	19345	19729
19757	19909	19951	20197	20417	20425	20591	20881	21361	21781	22177	22765	22791	22945	23001	23377
23521	23653	24046	24130	24211	24641	24661	24727	25327	25351	25681	25761	25829	26245	26281	26335
26361	26419	26467	26521	27037	27937	28009	28462	28645	29161	29234	29341	29539	29857	29891	30025
30073	30121	30673	30811	30857	30889	31417	31609	31621	31697	32021	32791	33001	33153	33227	34441
34669	34945	35333	35371	35425	36661	36991	37701	38081	38503	38963	39331	39865	40132	40501	41041
41329	41665	42127	42799	43213	43739	44173	44287	44801	45141	45629	45991	46657	46999	47197	47611
47641	48133	48283	49051	49105	49141	49241	49321	49601	49771	49981

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