Quizás esta ilustración completamente básica ayude a la comprensión. Si no es necesario, puedo eliminar esta respuesta.
El pequeño teorema de Fermat dice que para todos los primos $p$ y bases $b$ donde $\gcd(b,p)=1$ tenemos que $b^{p-1} \equiv 1 \pmod p $ . Así que esto sugiere, que podríamos probar algunos $n$ para la primacía con esta relación muy fácil de calcular. Pero, por desgracia, no sólo los primos $p$ satisfacen esto, pero también algunos compuestos $n$ - al menos esto depende también de la selección de la base $b$ .
He hecho un pequeño programa para mostrar esto para algunos $n$ y algunos $b$ en una visualización similar a la de una hoja de cálculo:
base\ n -->
| \
V \ 2 3 4 5 6 7 8 9 10 11 12
-------+----------------------------------------------------
2 | 0 1 0 1 2 1 0 4 2 1 8
3 1 0 3 1 3 1 3 0 3 1 3
4 0 1 0 1 4 1 0 7 4 1 4
5 1 1 1 0 5 1 5 7 5 1 5
6 0 0 0 1 0 1 0 0 6 1 0
7 1 1 3 1 1 0 7 4 7 1 7
8 0 1 0 1 2 1 0 1 8 1 8
9 1 0 1 1 3 1 1 0 9 1 9
10 0 1 0 0 4 1 0 1 0 1 4
11 1 1 3 1 5 1 3 4 1 0 11
12 0 0 0 1 0 1 0 0 2 1 0
13 1 1 1 1 1 1 5 7 3 1 1
14 0 1 0 1 2 0 0 7 4 1 8
15 1 0 3 0 3 1 7 0 5 1 3
16 0 1 0 1 4 1 0 4 6 1 4
17 1 1 1 1 5 1 1 1 7 1 5
18 0 0 0 1 0 1 0 0 8 1 0
19 1 1 3 1 1 1 3 1 9 1 7
20 0 1 0 0 2 1 0 4 0 1 8
21 1 0 1 1 3 0 5 0 1 1 9
22 0 1 0 1 4 1 0 7 2 0 4
Las entradas son siempre $ b^{n-1} \pmod n$ y vemos por ejemplo en el $n$ que son primos $p=3$ o $p=5$ y así sucesivamente, que efectivamente para todas las bases $b$ que no contengan $p$ el resultado es efectivamente $1$ . En compuesto $n$ no es así; en la mayoría de los casos las entradas son diferentes de $1$ y así el pequeño Fermat funcionaría en estos casos. Por ejemplo, para $n=4,6,8,10,12 $ se producen $1$ - pero sólo en las bases $b=k\cdot n+1$ Significado $(k \cdot n+1)^{n-1} \equiv 1 \pmod n$
Pero se complica un poco más para los grandes $n$ .
base\ n -->
| \
V \ 7 9 11 13 15 17 19 21 23 25 27
------------------------------------------------------------
2 1 4 1 1 4 1 1 4 1 16 13
3 1 0 1 1 9 1 1 9 1 6 0
4 1 7 1 1 1 1 1 16 1 6 7
5 1 7 1 1 10 1 1 4 1 0 16
6 1 0 1 1 6 1 1 15 1 21 0
7 0 4 1 1 4 1 1 7 1 1 4
8 1 1 1 1 4 1 1 1 1 21 10
9 1 0 1 1 6 1 1 18 1 11 0
10 1 1 1 1 10 1 1 16 1 0 19
11 1 4 0 1 1 1 1 16 1 16 22
12 1 0 1 1 9 1 1 18 1 11 0
13 1 7 1 0 4 1 1 1 1 11 25
14 0 7 1 1 1 1 1 7 1 16 25
15 1 0 1 1 0 1 1 15 1 0 0
16 1 4 1 1 1 1 1 4 1 11 22
17 1 1 1 1 4 0 1 16 1 21 19
18 1 0 1 1 9 1 1 9 1 1 0
19 1 1 1 1 1 1 0 4 1 21 10
20 1 4 1 1 10 1 1 1 1 0 4
21 0 0 1 1 6 1 1 0 1 6 0
22 1 7 0 1 4 1 1 1 1 6 16
Vemos, que regularmente números compuestos simples como $n=9,15,21,25$ tienen $1$ en algunas bases pequeñas, por lo que usar esas bases para la pequeña prueba del primo de Fermat firmaría falsos positivos. Sin embargo, la base $b=2$ funciona bien hasta ahora: separa perfectamente entre primos y compuestos. Lo mismo ocurre con $b=3$ .
Pero aún así nos metemos en problemas. Miremos a nuestro alrededor $n=341$
| 337 339 341 343 345 347 349 351 353 355 357
-----|-------------------------------------------------------
2| 1 4 1 162 31 1 1 121 1 229 67
3| 1 9 56 337 96 1 1 243 1 294 30
4| 1 16 1 176 271 1 1 250 1 256 205
5| 1 25 67 141 220 1 1 259 1 270 319
6| 1 36 56 57 216 1 1 270 1 231 225
7| 1 49 56 0 301 1 1 166 1 129 259
8| 1 64 1 43 121 1 1 64 1 49 169
Para los primos alrededor de $n=341$ cosas están bien, y también para los compuestos alrededor de $n$ cuando se utiliza la base $b=2$ . Solo, $n=341$ da un falso positivo. Así que esto se llama un "pseudoprime (a base 2)" Aquí base $b=3$ seguiría detectando correctamente la compostura. Pero veamos más pseudoprimes de base 2:
| 341 561 645 1105 1387 1729 1905 2047 2465 2701 2821
-----|-------------------------------------------------------
2| 1 1 1 1 1 1 1 1 1 1 1
3| 56 375 36 1 875 1 276 1013 1 1 1
4| 1 1 1 1 1 1 1 1 1 1 1
5| 67 1 595 885 1122 1 400 622 1480 2554 1
6| 56 375 36 1 875 1 276 1013 1 1 1
7| 56 1 436 1 1122 742 1561 1013 1 2554 2016
8| 1 1 1 1 1 1 1 1 1 1 1
9| 67 375 6 1 1 1 1881 622 1 1 1
10| 67 1 595 885 1122 1 400 622 1480 2554 1
11| 253 154 1 1 1141 1 226 1 1 2554 1
12| 56 375 36 1 875 1 276 1013 1 1 1
Vemos, que un par de ellos están correctamente señalizados por base-3, algunos todavía no y una bestia realmente dura es $n=1729$ que necesita pruebas hasta $b=7$ para detectar la compostura.
La introducción del concepto de los números de Carmichael es ahora para denotar que los números $n$ que son pseudoprimos de todas las bases $b$ que son coprimos de $n$ por lo que, en cierto sentido, son pseudoprimes "más fuertes" que los de una sola base. Por ejemplo, $n=561$ es un pseudoprimo fuerte para bases $ b=2,4,5,7,8,10,...$ y sólo las bases que tengan un factor común con $n$ indican una composición correcta.
Otras respuestas han indicado algunas propiedades de esos números Carmichael, como la cuadratura, el número de factores primos $\ge 3$ y algunos más - que es lo que realmente ha pedido (y puede encontrar en las otras respuestas).
Observación adicional: los "números de Carmichael" son un concepto interesante: procedimientos de prueba más fuertes que el pequeño Fermat de base. $b=2$ utilizar primero un par de bases para las pseudopruebas antes de introducir procedimientos más complicados y que consumen más tiempo (y de alguna manera es una especie de arte definir el conjunto óptimo de bases para las pseudopruebas que se corrigen mutuamente hasta cierto límite inferior $n \le N$ que cuestan menos y siguen siendo indicadores perfectos)
