Número de Carmichael

En teoría de números , un número de Carmichael es un número compuesto .${\displaystyle n}$que en aritmética modular satisface la relación de congruencia :

${\displaystyle b^{n}\equiv b{\pmod {n}}}$

para todos los números enteros${\displaystyle b}$⁠ . ^{[ 1 ]} La relación también puede expresarse ^{[ 2 ]} de la forma:

${\displaystyle b^{n-1}\equiv 1{\pmod {n}}}$

para todos los números enteros${\displaystyle b}$que son relativamente primos para${\displaystyle n}$Son infinitos en número ^. [ ^{3 ]}

Constituyen los casos relativamente raros en los que no se cumple el recíproco estricto del Pequeño Teorema de Fermat . Este hecho impide el uso de dicho teorema como prueba absoluta de primalidad . ^{[ 4 ]}

Los números de Carmichael forman el subconjunto K ₁ de los números de Knödel .

Los números de Carmichael fueron nombrados en honor al matemático estadounidense Robert Carmichael por Nicolaas Beeger en 1950. Øystein Ore se había referido a ellos en 1948 como números con la "propiedad de Fermat" o, simplemente, "números F ". ^{[ 5 ]}

El pequeño teorema de Fermat establece que si${\displaystyle p}$es un número primo , entonces para cualquier entero${\displaystyle b}$⁠ , el número${\displaystyle b^{p}-b}$es un múltiplo entero de ⁠${\displaystyle p}$Los números de Carmichael son números compuestos que tienen la misma propiedad. Los números de Carmichael también se llaman pseudoprimos de Fermat o pseudoprimos absolutos de Fermat . Un número de Carmichael pasará una prueba de primalidad de Fermat a cada base .${\displaystyle b}$es relativamente primo al número, aunque en realidad no lo sea. Esto hace que las pruebas basadas en el Pequeño Teorema de Fermat sean menos efectivas que las pruebas de primalidad probable fuertes, como la prueba de primalidad de Baillie-PSW y la prueba de primalidad de Miller-Rabin .

Sin embargo, ningún número de Carmichael es un pseudoprimo de Euler-Jacobi o un pseudoprimo fuerte para cada base relativamente prima con él ^{[ 6 ]} por lo que, en teoría, una prueba de Euler o una prueba de primalidad probable fuerte podrían probar que un número de Carmichael es, de hecho, compuesto.

Arnault ^{[ 7 ]} proporciona un número de Carmichael de 397 dígitos.${\displaystyle N}$que es un pseudoprimo fuerte para todas las bases primas menores que 307:

${\displaystyle N=p\cdot (313(p-1)+1)\cdot (353(p-1)+1)}$

dónde

${\displaystyle p=}$2​ ‍ 9674495668​ ‍ 6855105501​ ‍ 5417464290​ ‍ 5332730771​ ‍ 9917998530​ ‍ 4335099507​ ‍ 5531276838​ ‍ 7531717701​ ‍ 9959423859​ ‍ 6428121188 ‍ 0336647542​ ‍ 1834556249​ ‍ 3168782883

es un número primo de 131 dígitos.${\displaystyle p}$es el factor primo más pequeño de${\displaystyle N}$⁠ , por lo que este número de Carmichael es también un pseudoprimo (no necesariamente fuerte) para todas las bases menores que ⁠${\displaystyle p}$.​

A medida que los números aumentan, los números de Carmichael se vuelven cada vez más raros. Por ejemplo, hay20 138 200 Números de Carmichael entre 1 y 10 ²¹ (aproximadamente uno en 50 billones (5 × 10 ¹³ ) números). ^{[ 8 ]}

Los primeros siete números de Carmichael, del 561 al 8911, fueron hallados por el matemático checo Václav Šimerka en 1885 ^{[ 11 ]} (precediendo así no solo a Carmichael sino también a Korselt, aunque Šimerka no halló nada parecido al criterio de Korselt). ^{[ 12 ]} Sin embargo , su trabajo, publicado en la revista científica checa Časopis pro pěstování matematiky a fysiky , pasó desapercibido.

Korselt fue el primero en observar las propiedades básicas de los números de Carmichael, pero no dio ningún ejemplo.

Que 561 sea un número de Carmichael se puede comprobar con el criterio de Korselt. Los primeros siete números de Carmichael son (secuencia A002997 en la OEIS ) :

${\displaystyle ~~561=3\cdot 11\cdot 17\qquad (2\mid ~~560;\quad 10\mid ~~560;\quad 16\mid ~~560)}$

${\displaystyle 1105=5\cdot 13\cdot 17\qquad (4\mid 1104;\quad 12\mid 1104;\quad 16\mid 1104)}$

${\displaystyle 1729=7\cdot 13\cdot 19\qquad (6\mid 1728;\quad 12\mid 1728;\quad 18\mid 1728)}$

${\displaystyle 2465=5\cdot 17\cdot 29\qquad (4\mid 2464;\quad 16\mid 2464;\quad 28\mid 2464)}$

${\displaystyle 2821=7\cdot 13\cdot 31\qquad (6\mid 2820;\quad 12\mid 2820;\quad 30\mid 2820)}$

${\displaystyle 6601=7\cdot 23\cdot 41\qquad (6\mid 6600;\quad 22\mid 6600;\quad 40\mid 6600)}$

${\displaystyle 8911=7\cdot 19\cdot 67\qquad (6\mid 8910;\quad 18\mid 8910;\quad 66\mid 8910).}$

En 1910, el propio Carmichael ^{[ 13 ]} también publicó el número más pequeño de este tipo, 561, y los números posteriormente recibieron su nombre.

Jack Chernick ^{[ 14 ]} demostró en 1939 un teorema que puede utilizarse para construir un subconjunto de los números de Carmichael. El número${\displaystyle (6k+1)(12k+1)(18k+1)}$Un número es un número de Carmichael si sus tres factores son todos primos. Si esta fórmula produce una cantidad infinita de números de Carmichael es una cuestión abierta (aunque la conjetura de Dickson lo sugiere ).

Paul Erdős argumentó heurísticamente que debería haber infinitos números de Carmichael. En 1994, WR (Red) Alford , Andrew Granville y Carl Pomerance utilizaron una cota para la constante de Olson para demostrar que realmente existen infinitos números de Carmichael. Específicamente, demostraron que para suficientemente grande${\displaystyle n}$⁠ , hay al menos${\displaystyle n^{2/7}}$Números de Carmichael entre 1 y ⁠${\displaystyle n}$⁠ . ^{[ 3 ]}

Thomas Wright demostró que si${\displaystyle a}$y${\displaystyle m}$Si son relativamente primos, entonces hay infinitos números de Carmichael en la progresión aritmética .${\displaystyle a+k\cdot m}$, donde​${\displaystyle k=1,2,\ldots }$⁠ . ^{[ 15 ]}

Löh y Niebuhr en 1992 encontraron algunos números de Carmichael muy grandes, incluyendo uno con1 101 518 factores y más de 16 millones de dígitos. Esto se ha mejorado a10 333 229 505 factores primos y295 486 761 787 dígitos, ^{[ 16 ]} por lo que el mayor número de Carmichael conocido es mucho mayor que el mayor primo conocido .

La noción de número de Carmichael se generaliza a un ideal de Carmichael en cualquier cuerpo numérico .${\displaystyle K}$Para cualquier ideal primo distinto de cero${\displaystyle {\mathfrak {p}}}$en​${\displaystyle {\mathcal {O}}_{K}}$⁠ , tenemos${\displaystyle \alpha ^{{\rm {N}}({\mathfrak {p}})}\equiv \alpha {\bmod {\mathfrak {p}}}}$a pesar de${\displaystyle \alpha }$en​${\displaystyle {\mathcal {O}}_{K}}$, donde${\displaystyle {\rm {N}}({\mathfrak {p}})}$es la norma del ideal${\displaystyle {\mathfrak {p}}}$⁠ . (Esto generaliza el pequeño teorema de Fermat, que${\displaystyle m^{p}\equiv m{\bmod {p}}}$para todos los números enteros${\displaystyle m}$cuando​​${\displaystyle p}$( es primo.) Llamamos ideal distinto de cero${\displaystyle {\mathfrak {a}}}$en${\displaystyle {\mathcal {O}}_{K}}$Carmichael si no es un ideal primordial y${\displaystyle \alpha ^{{\rm {N}}({\mathfrak {a}})}\equiv \alpha {\bmod {\mathfrak {a}}}}$para todos${\displaystyle \alpha \in {\mathcal {O}}_{K}}$, donde${\displaystyle {\rm {N}}({\mathfrak {a}})}$es la norma del ideal${\displaystyle {\mathfrak {a}}}$⁠ . Cuando ⁠${\displaystyle K}$es​​${\displaystyle \mathbf {Q} }$⁠ , el ideal${\displaystyle {\mathfrak {a}}}$es principal , y si dejamos ⁠${\displaystyle a}$Si es su generador positivo, entonces el ideal${\displaystyle {\mathfrak {a}}=(a)}$¿Es Carmichael exactamente cuándo ?${\displaystyle a}$⁠ es un número de Carmichael en el sentido habitual.

Cuando​${\displaystyle K}$⁠ es mayor que los racionales es fácil escribir los ideales de Carmichael en ⁠${\displaystyle {\mathcal {O}}_{K}}$: para cualquier número primo${\displaystyle p}$que se divide completamente en${\displaystyle K}$⁠ , el ideal principal${\displaystyle p{\mathcal {O}}_{K}}$es un ideal de Carmichael. Dado que infinitos números primos se dividen completamente en cualquier cuerpo numérico, hay infinitos ideales de Carmichael en${\displaystyle {\mathcal {O}}_{K}}$⁠ . Por ejemplo, si ⁠${\displaystyle p}$⁠ es cualquier número primo que sea 1 mod 4, el ideal ⁠${\displaystyle (p)}$en los enteros gaussianos${\displaystyle \mathbb {Z} [i]}$es un ideal de Carmichael.

Tanto los números primos como los números de Carmichael satisfacen la siguiente igualdad:

${\displaystyle \gcd \left(\sum _{x=1}^{n-1}x^{n-1},n\right)=1.}$

Un número entero compuesto positivo${\displaystyle n}$es un número de Lucas-Carmichael si y solo si${\displaystyle n}$es libre de cuadrados y para todos los divisores primos${\displaystyle p}$de​${\displaystyle n}$⁠ , es cierto que ⁠${\displaystyle p+1\mid n+1}$Los primeros números de Lucas-Carmichael son :

399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90287, ... (secuencia A006972 en el OEIS )

Los números cuasi-Carmichael son números compuestos libres de cuadrados .${\displaystyle n}$con la propiedad de que para cada factor primo${\displaystyle p}$de​​${\displaystyle n}$,​​${\displaystyle p+b}$divide​​${\displaystyle n+b}$positivamente con​${\displaystyle b}$siendo cualquier número entero distinto de 0. Si${\displaystyle b=-1}$⁠ , estos son números de Carmichael, y si ⁠${\displaystyle b=1}$Estos son los números de Lucas-Carmichael. Los primeros números cuasi-Carmichael son:

35, 77, 143, 165, 187, 209, 221, 231, 247, 273, 299, 323, 357, 391, 399, 437, 493, 527, 561, 589, 598, 713, 715, 899, 935, 943, 989, 1015, 1073, 1105, 1147, 1189, 1247, 1271, 1295, 1333, 1517, 1537, 1547, 1591, 1595, 1705, 1729, ... (secuencia A257750 en el OEIS) )

Un número de Knödel n para un entero positivo n dado es un número compuesto m con la propiedad de que cada${\displaystyle i<m}$⁠ coprimo con m satisface ⁠${\displaystyle i^{m-n}\equiv 1{\pmod {m}}}$⁠ . El ⁠${\displaystyle n=1}$⁠ caso son números de Carmichael.

Los números de Carmichael se pueden generalizar utilizando conceptos de álgebra abstracta .

La definición anterior establece que un entero compuesto n es Carmichael precisamente cuando la función de elevación a la n -ésima potencia p _n del anillo Z _n de enteros módulo n es la función identidad. La identidad es el único endomorfismo de álgebra Z _n en Z _n, por lo que podemos reformular la definición pidiendo que p _n sea un endomorfismo de álgebra de Z _n . Como se indicó anteriormente, p _n satisface la misma propiedad siempre que n sea primo.

La función de elevación a la enésima potencia p n _también está definida en cualquier álgebra Z _n A . Un teorema establece que n es primo si y solo si todas esas funciones p _n son endomorfismos de álgebras.

Entre estas dos condiciones se encuentra la definición de número de Carmichael de orden m para cualquier entero positivo m como cualquier número compuesto n tal que p _n es un endomorfismo en toda Z _n -álgebra que puede generarse como Z _n -módulo por m elementos. Los números de Carmichael de orden 1 son simplemente los números de Carmichael ordinarios .

• Carmichael, RD (1910). "Nota sobre una nueva función de teoría de números" . Boletín de la Sociedad Matemática Americana . 16 (5): 232– 238. doi : 10.1090/s0002-9904-1910-01892-9 .
• Carmichael, RD (1912). "Sobre los números compuestos P que satisfacen la congruencia de Fermat${\displaystyle a^{P-1}\equiv 1{\bmod {P}}}$". American Mathematical Monthly . 19 (2): 22– 27. doi : 10.2307/2972687 . JSTOR 2972687 . 
• Chernick, J. (1939). "Sobre el teorema simple de Fermat" (PDF) . Bull. Amer. Math. Soc . 45 (4): 269– 274. doi : 10.1090/S0002-9904-1939-06953-X .
• Korselt, AR (1899). "Problema chino". L'Intermédiaire des Mathématiciens . 6 : 142-143 .
• Löh, G.; Niebuhr, W. (1996). "Un nuevo algoritmo para construir números de Carmichael grandes" (PDF) . Math. Comp . 65 (214): 823– 836. Bibcode : 1996MaCom..65..823L . doi : 10.1090/S0025-5718-96-00692-8 . Archivado (PDF) del original el 25 de abril de 2003.
• Ribenboim, P. (1989). El libro de los registros de números primos . Springer. ISBN 978-0-387-97042-4.
• Šimerka, V. (1885). "Zbytky z arithmetické posloupnosti (Sobre los restos de una progresión aritmética)" . Časopis Pro Pěstování Matematiky a Fysiky . 14 (5): 221– 225. doi : 10.21136/CPMF.1885.122245 .

• "Número de Carmichael" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Enciclopedia de Matemáticas
• Tabla de números de Carmichael
• Tablas de números de Carmichael con muchos factores primos
• Tablas de números de Carmichael a continuación${\displaystyle 10^{18}}$
• "El tedio de 1729" . MathPages.com .
• Weisstein, Eric W. "Número de Carmichael" . MathWorld .
• Respuestas finales Aritmética modular