Constituyen los casos comparativamente raros en los que no se cumple lo estrictamente contrario del pequeño teorema de Fermat . Este hecho impide el uso de ese teorema como prueba absoluta de primalidad . [4]
Los números de Carmichael forman el subconjunto K 1 de los números de Knödel .
Los números de Carmichael recibieron el nombre del matemático estadounidense Robert Carmichael por Nicolaas Beeger en 1950. Øystein Ore se refirió a ellos en 1948 como números con la "propiedad de Fermat", o " números F " para abreviar. [5]
Sin embargo, ningún número de Carmichael es un pseudoprimo de Euler-Jacobi o un pseudoprimo fuerte para cada base relativamente prima con respecto a él [6]
por lo que, en teoría, una prueba de Euler o una de primo probable fuerte podría demostrar que un número de Carmichael es, de hecho , compuesto.
Arnault [7]
proporciona un número de Carmichael de 397 dígitos que es un pseudoprimo fuerte para todas las bases primas menores que 307:
es un primo de 131 dígitos. es el factor primo más pequeño de , por lo que este número de Carmichael también es un pseudoprimo (no necesariamente fuerte) para todas las bases menores que .
A medida que los números aumentan, los números de Carmichael se vuelven cada vez más raros. Por ejemplo, hay 20.138.200 números de Carmichael entre 1 y 10 21 (aproximadamente uno entre 50 billones (5·10 13 ) de números). [8]
criterio de korselt
El criterio de Korselt da una definición alternativa y equivalente de los números de Carmichael .
Teorema ( A. Korselt 1899): Un entero compuesto positivo es un número de Carmichael si y solo si no tiene cuadrados , y para todos los divisores primos de , es cierto que .
De este teorema se deduce que todos los números de Carmichael son impares , ya que cualquier número compuesto par que no tenga cuadrados (y por lo tanto tenga solo un factor primo de dos) tendrá al menos un factor primo impar y, por lo tanto, resultará en una división par de un extraño, una contradicción. (La imparidad de los números de Carmichael también se deriva del hecho de que es un testigo de Fermat para cualquier número compuesto par). Del criterio también se deduce que los números de Carmichael son cíclicos . [9] [10] Además, se deduce que no hay números de Carmichael con exactamente dos divisores primos.
Descubrimiento
Los primeros siete números de Carmichael, del 561 al 8911, fueron encontrados por el matemático checo Václav Šimerka en 1885 [11] (precediendo así no sólo a Carmichael sino también a Korselt, aunque Šimerka no encontró 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.
Václav Šimerka enumeró los primeros siete números de Carmichael
Korselt fue el primero en observar las propiedades básicas de los números de Carmichael, pero no dio ningún ejemplo.
Que 561 es un número de Carmichael se puede comprobar con el criterio de Korselt. De hecho, no tiene cuadrados y , y . Los siguientes seis números de Carmichael son (secuencia A002997 en OEIS ):
En 1910, el propio Carmichael [13] también publicó el número más pequeño, 561, y más tarde los números recibieron su nombre.
Jack Chernick [14] demostró un teorema en 1939 que puede utilizarse para construir un subconjunto de números de Carmichael. El 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 está implícita en la conjetura de Dickson ).
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 un límite en la constante de Olson para demostrar que realmente existen infinitos números de Carmichael. Específicamente, demostraron que para suficientemente grandes , hay al menos números de Carmichael entre 1 y . [3]
Thomas Wright demostró que si y son primos relativos, entonces hay infinitos números de Carmichael en la progresión aritmética , donde . [15]
Löh y Niebuhr en 1992 encontraron algunos números de Carmichael muy grandes, incluido uno con 1.101.518 factores y más de 16 millones de dígitos. Esto se ha mejorado a 10.333.229.505 factores primos y 295.486.761.787 dígitos, [16] por lo que el mayor número de Carmichael conocido es mucho mayor que el mayor número primo conocido .
Propiedades
Factorizaciones
Los números de Carmichael tienen al menos tres factores primos positivos. Los primeros números de Carmichael con factores primos son (secuencia A006931 en la OEIS ):
Los primeros números de Carmichael con 4 factores primos son (secuencia A074379 en la OEIS ):
El segundo número de Carmichael (1105) se puede expresar como la suma de dos cuadrados de más formas que cualquier número menor. El tercer número de Carmichael (1729) es el número de Hardy-Ramanujan : el número más pequeño que se puede expresar como la suma de dos cubos (de números positivos) de dos maneras diferentes.
Distribución
Denotemos el número de números de Carmichael menores o iguales a . La distribución de los números de Carmichael por potencias de 10 (secuencia A055553 en la OEIS ): [8]
para alguna constante . [17] Además, dio un argumento heurístico que sugiere que este límite superior debería estar cerca de la verdadera tasa de crecimiento de .
En la otra dirección, Alford , Granville y Pomerance demostraron en 1994 [3] que para X suficientemente grande ,
quien posteriormente mejoró el exponente a . [19]
Respecto a la distribución asintótica de los números de Carmichael, ha habido varias conjeturas. En 1956, Erdős [17] conjeturó que había números de Carmichael para X suficientemente grandes. En 1981, Pomerance [20] agudizó los argumentos heurísticos de Erdős para conjeturar que existen al menos
Carmichael numera hasta , donde .
Sin embargo, dentro de los rangos computacionales actuales (como los recuentos de números de Carmichael realizados por Pinch [8] hasta 10 21 ), los datos aún no confirman estas conjeturas.
En 2021, Daniel Larsen demostró un análogo del postulado de Bertrand para los números de Carmichael conjeturado por primera vez por Alford, Granville y Pomerance en 1994. [4] [21] Utilizando técnicas desarrolladas por Yitang Zhang y James Maynard para establecer resultados relacionados con pequeñas brechas entre números primos , su trabajo arrojó la afirmación mucho más contundente de que, para cualquier tamaño suficientemente grande en términos de , siempre habrá al menos
Números de Carmichael entre y
Generalizaciones
La noción de número de Carmichael se generaliza a un ideal de Carmichael en cualquier campo numérico . Para cualquier ideal primo distinto de cero en , tenemos para todos en , donde está la norma del ideal . (Esto generaliza el pequeño teorema de Fermat, que para todos los números enteros cuando es primo). Llame a un ideal distinto de cero en Carmichael si no es un ideal primo y para todos , donde está la norma del ideal . Cuando es , el ideal es principal y si dejamos que sea su generador positivo, entonces el ideal es Carmichael exactamente cuando es un número de Carmichael en el sentido habitual.
Cuando es mayor que los racionales, es fácil escribir los ideales de Carmichael en : para cualquier número primo que se divida completamente en , el ideal principal es un ideal de Carmichael. Dado que una infinidad de números primos se dividen completamente en cualquier campo numérico, hay infinitos ideales de Carmichael en . Por ejemplo, si es cualquier número primo que sea 1 mod 4, el ideal en los enteros gaussianos es un ideal de Carmichael.
Tanto los números primos como los de Carmichael satisfacen la siguiente igualdad:
Número de Lucas-Carmichael
Un entero compuesto positivo es un número de Lucas-Carmichael si y solo si no tiene cuadrados , y para todos los divisores primos de , es cierto que . Los primeros números de Lucas-Carmichael son:
Los números cuasi-Carmichael son números compuestos sin cuadrados con la propiedad de que para cada factor primo de , se divide positivamente siendo cualquier número entero además de 0. Si , estos son números de Carmichael, y si , estos son números de Lucas-Carmichael. Los primeros números Quasi-Carmichael son:
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 n -ésima función elevadora de potencia p n del anillo Z n de enteros módulo n consigo mismo 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 arriba, p n satisface la misma propiedad siempre que n sea primo.
La n -ésima función de aumento de potencia p n también se define en cualquier Z n -álgebra A. Un teorema establece que n es primo si y sólo si todas esas funciones p n son endomorfismos del álgebra.
Entre estas dos condiciones se encuentra la definición del 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 cada 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.
Un número Carmichael de orden 2
Según Howe, 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 es un número de Carmichael de orden 2. Este producto es igual a 443.372.888.629.441. [22]
Propiedades
El criterio de Korselt se puede generalizar a números de Carmichael de orden superior, como lo muestra Howe.
Un argumento heurístico, presentado en el mismo artículo, parece sugerir que hay infinitos números de Carmichael de orden m , para cualquier m . Sin embargo, no se conoce ni un solo número de Carmichael de orden 3 o superior.
Notas
^ Riesel, Hans (1994). Números primos y métodos informáticos de factorización . Progreso en Matemáticas. vol. 126 (segunda ed.). Boston, MA: Birkhäuser. ISBN 978-0-8176-3743-9. Zbl 0821.11001.
^ ab Cepelewicz, Jordana (13 de octubre de 2022). "Un adolescente resuelve un obstinado acertijo sobre los dobles de números primos". Revista Quanta . Consultado el 13 de octubre de 2022 .
^ Mineral, Øystein (1948). Teoría de números y su historia . Nueva York: McGraw-Hill. págs. 331–332 - a través de Internet Archive .
^ DH Lehmer (1976). "Números fuertes de Carmichael". J.Austral. Matemáticas. Soc . 21 (4): 508–510. doi : 10.1017/s1446788700019364 .Lehmer demostró que ningún número de Carmichael es pseudoprimo de Euler-Jacobi para toda base relativamente prima con respecto a él. Usó el término pseudoprime fuerte , pero la terminología ha cambiado desde entonces. Los pseudoprimos fuertes son un subconjunto de los pseudoprimos de Euler-Jacobi. Por lo tanto, ningún número de Carmichael es pseudoprimo fuerte para cada base relativamente prima de él.
^ F. Arnault (agosto de 1995). "Construcción de números de Carmichael que son pseudoprimos fuertes para varias bases". Revista de Computación Simbólica . 20 (2): 151–161. doi : 10.1006/jsco.1995.1042 .
^ abc Pinch, Richard (diciembre de 2007). Anne-Maria Ernvall-Hytönen (ed.). Los números de Carmichael hasta 1021 (PDF) . Actas de la conferencia sobre teoría algorítmica de números. vol. 46. Turku, Finlandia: Centro de Ciencias de la Computación de Turku. págs. 129-131 . Consultado el 26 de junio de 2017 .
^ Carmichael Múltiplos de números cíclicos impares "Cualquier divisor de un número de Carmichael debe ser un número cíclico impar"
^ Bosquejo de prueba: si no tiene cuadrados pero no es cíclico, para dos factores primos y de . Pero si satisface a Korselt entonces , entonces por transitividad de la relación "divide" . Pero también es un factor de , una contradicción.
^ Šimerka, Václav (1885). "Zbytky z arithmetické posloupnosti" [Sobre los restos de una progresión aritmética]. Časopis pro pěstování mathematiky a fysiky . 14 (5): 221–225. doi : 10.21136/CPMF.1885.122245 .
^ Lemmermeyer, F. (2013). "Václav Šimerka: formas cuadráticas y factorización". Revista LMS de Computación y Matemáticas . 16 : 118-129. doi : 10.1112/S1461157013000065 .
^ RD Carmichael (1910). "Nota sobre una nueva función de teoría de números". Boletín de la Sociedad Matemática Estadounidense . 16 (5): 232–238. doi : 10.1090/s0002-9904-1910-01892-9 .
^ Chernick, J. (1939). "Sobre el teorema simple de Fermat" (PDF) . Toro. América. Matemáticas. Soc . 45 (4): 269–274. doi : 10.1090/S0002-9904-1939-06953-X .
^ Thomas Wright (2013). "Infinitos números de Carmichael en progresiones aritméticas". Toro. Matemáticas de Londres. Soc. 45 (5): 943–952. arXiv : 1212.5850 . doi :10.1112/blms/bdt013. S2CID 119126065.
^ WR Alford ; et al. (2014). "Construcción de números de Carmichael mediante algoritmos mejorados de subconjuntos de productos". Matemáticas. comp . 83 (286): 899–915. arXiv : 1203.6664 . doi :10.1090/S0025-5718-2013-02737-8. S2CID 35535110.
^ ab Erdős, P. (2022). "Sobre pseudoprimos y números de Carmichael" (PDF) . Publ. Matemáticas. Debrecen . 4 (3–4): 201–206. doi :10.5486/PMD.1956.4.3-4.16. SEÑOR 0079031. S2CID 253789521. Archivado (PDF) desde el original el 11 de junio de 2011.
^ Glyn Harman (2005). "Sobre el número de números de Carmichael hasta x ". Boletín de la Sociedad Matemática de Londres . 37 (5): 641–650. doi :10.1112/S0024609305004686. S2CID 124405969.
^ Harman, Glyn (2008). "Teorema del valor medio de Watt y números de Carmichael". Revista Internacional de Teoría de Números . 4 (2): 241–248. doi :10.1142/S1793042108001316. SEÑOR 2404800.
^ Pomerancia, C. (1981). "Sobre la distribución de pseudoprimos". Matemáticas. comp . 37 (156): 587–593. doi : 10.1090/s0025-5718-1981-0628717-0 . JSTOR 2007448.
^ Larsen, Daniel (20 de julio de 2022). "Postulado de Bertrand para los números de Carmichael". Avisos internacionales de investigación en matemáticas . 2023 (15): 13072–13098. arXiv : 2111.06963 . doi :10.1093/imrn/rnac203.
^ Everett W. Howe (octubre de 2000). "Números de Carmichael de orden superior". Matemáticas de la Computación . 69 (232): 1711-1719. arXiv : math.NT/9812089 . Código Bib : 2000MaCom..69.1711H. doi :10.1090/s0025-5718-00-01225-4. JSTOR 2585091. S2CID 6102830.
Carmichael, RD (1912). "Sobre números compuestos P que satisfacen la congruencia de Fermat ". Mensual Matemático Estadounidense . 19 (2): 22-27. doi :10.2307/2972687. JSTOR 2972687.
Chernick, J. (1939). "Sobre el teorema simple de Fermat" (PDF) . Toro. América. Matemáticas. Soc . 45 (4): 269–274. doi : 10.1090/S0002-9904-1939-06953-X .
Loh, G.; Niebuhr, W. (1996). "Un nuevo algoritmo para construir números de Carmichael grandes" (PDF) . Matemáticas. comp . 65 (214): 823–836. Código Bib : 1996MaCom..65..823L. doi : 10.1090/S0025-5718-96-00692-8 . Archivado (PDF) desde el original el 25 de abril de 2003.
Š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 .