Pseudoprimzahl

Eine Pseudo-Primzahl ist eine natürliche Zahl n, für die bei bestimmten Basen $b>=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 Pseudo-Primzahl ist die Zahl 15. Sie ist pseudoprim zur Basis 11. Die kleinste Pseudo-Primzahl zur Basis 2 ist die Zahl 341.

341	2
2701	2, 3
29341	2, 3, 5, 7

Die Carmichael-Zahl, benannt nach dem Mathematiker Robert Daniel Carmichael, ist eine spezielle Form der Pseudo-Primzahl, für die gilt: Die Carmichael-Zahl ist pseudoprim zu allen Basen, die keine Teiler der Carmichael-Zahlen ist. Die kleinste Carmichael-Zahl ist die 561. Für die 561 gilt also: 561 ist nicht pseudoprim zu 3, 11, 17, 33, 51 und 187.

Carmichael-Zahlen
561	=	3 * 11 * 17
1105	=	5 * 13 * 17
1729	=	7 * 13 * 19
2465	=	5 * 17 * 29
2821	=	7 * 13 * 31
6601	=	7 * 23 * 41
8911	=	7 * 19 * 67
10585	=	5 * 29 * 73
15841	=	7 * 31 * 73
29341	=	13 * 37 * 61
41041	=	7 * 11 *13 * 41
46657	=	13 * 37 * 97
52633	=	7 * 73 * 103
62745	=	3 * 5 * 47 * 89
63973	=	7 * 13 * 19 * 37
75361	=	11 * 17 * 31
101101	=	7 * 11 * 13 *101
115921	=	13 * 37 * 241
126217	=	7 * 13 * 19 * 73
162401	=	17 * 41 * 233