En teoría de números , un número de Carmichael es un número compuesto que satisface la relación de congruencia aritmética modular :
para todos los enteros que son relativamente mejores para. [1] Llevan el nombre de Robert Carmichael . Los números de Carmichael son el subconjunto K 1 de los números de Knödel .
De manera equivalente, un número de Carmichael es un número compuesto para cual
para todos los enteros . [2]
Descripción general
El pequeño teorema de Fermat establece que si p es un número primo , entonces para cualquier número entero b , el número b p - b es un múltiplo entero de p . Los números de Carmichael son números compuestos que tienen esta propiedad. Los números de Carmichael también se denominan pseudoprimas de Fermat o pseudoprimas absolutas de Fermat . Un número de Carmichael pasará una prueba de primordialidad de Fermat para cada base b relativamente primo con respecto al número, aunque en realidad no sea primo. Esto hace que las pruebas basadas en el pequeño teorema de Fermat sean menos efectivas que las pruebas de primos probables fuertes como la prueba de primalidad de Baillie-PSW y la prueba de primordialidad de Miller-Rabin .
Sin embargo, ningún número de Carmichael es un pseudoprime de Euler-Jacobi o un pseudoprime fuerte para cada base relativamente primo con respecto a él [3] , por lo que, en teoría, una prueba de Euler o una prueba de primo probable fuerte podría demostrar que un número de Carmichael es, de hecho , compuesto.
Arnault [4] da un número de Carmichael de 397 dígitos.que es un pseudoprime fuerte para todas las bases primarias menores de 307:
dónde
- 29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883
es un número primo de 131 dígitos. es el factor primo más pequeño de , por lo que este número de Carmichael es también un pseudoprime (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 en 50 billones (5 · 10 13 ) números). [5]
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 es libre de 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 sea libre de cuadrados (y por lo tanto tenga solo un factor primo de dos) tendrá al menos un factor primo impar, y por lo tantoresulta en una división par de un impar, una contradicción. (La rareza de los números de Carmichael también se deriva del hecho de quees un testigo de Fermat para cualquier número compuesto par.) Del criterio también se sigue que los números de Carmichael son cíclicos . [6] [7] Además, se deduce que no hay números de Carmichael con exactamente dos divisores primos.
Descubrimiento
Korselt fue el primero en observar las propiedades básicas de los números de Carmichael, pero no dio ningún ejemplo. En 1910, Carmichael [8] encontró el primer y más pequeño número de este tipo, 561, que explica el nombre "número de Carmichael".
Que 561 es un número de Carmichael se puede ver con el criterio de Korselt. En efecto, es cuadrado libre y , y .
Los siguientes seis números de Carmichael son (secuencia A002997 en la OEIS ):
Estos primeros siete números de Carmichael, del 561 al 8911, fueron encontrados por el matemático checo Václav Šimerka [9] (por lo tanto, precediendo no solo a Carmichael sino también a Korselt, aunque Šimerka no encontró nada parecido al criterio de Korselt). [10] Su trabajo, sin embargo, pasó desapercibido.
en 1885J. Chernick [11] demostró un teorema en 1939 que puede usarse para construir un subconjunto de números de Carmichael. El númeroes 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 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 mostrar que realmente existen infinitos números de Carmichael. Específicamente, demostraron que para un tamaño suficientemente grande, hay por lo menos Números de Carmichael entre 1 y . [12]
Thomas Wright demostró que si y son relativamente primos, entonces hay infinitos números de Carmichael en la progresión aritmética , dónde . [13]
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, [14] por lo que el número de Carmichael más grande conocido es mucho mayor que el número primo más grande conocido .
Propiedades
Factorizaciones
Los números de Carmichael tienen al menos tres factores primos positivos. Los primeros números de Carmichael conlos factores primos son (secuencia A006931 en la OEIS ):
k | |
---|---|
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 |
Los primeros números de Carmichael con 4 factores primos son (secuencia A074379 en la OEIS ):
I | |
---|---|
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 |
El segundo número de Carmichael (1105) se puede expresar como la suma de dos cuadrados de más formas que cualquier número más pequeño. 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 formas diferentes.
Distribución
Dejar denotar 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 ): [5]
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 17 | 18 | 19 | 20 | 21 | |
0 | 0 | 1 | 7 | dieciséis | 43 | 105 | 255 | 646 | 1547 | 3605 | 8241 | 19279 | 44706 | 105212 | 246683 | 585355 | 1401644 | 3381806 | 8220777 | 20138200 |
En 1953, Knödel demostró el límite superior :
por alguna constante .
En 1956, Erdős mejoró el límite a
por alguna constante . [15] Además, dio un argumento heurístico que sugiere que este límite superior debería estar cerca de la tasa de crecimiento real de.
En la otra dirección, Alford , Granville y Pomerance demostraron en 1994 [12] que para X suficientemente grande ,
En 2005, Harman [16] siguió mejorando este límite para
quien posteriormente mejoró el exponente a . [17]
Con respecto a la distribución asintótica de los números de Carmichael, ha habido varias conjeturas. En 1956, Erdős [15] conjeturó que habíaNúmeros de Carmichael para X suficientemente grandes. En 1981, Pomerance [18] agudizó los argumentos heurísticos de Erdős para conjeturar que existen al menos
Carmichael numera hasta , dónde .
Sin embargo, dentro de los rangos computacionales actuales (como los recuentos de números de Carmichael realizados por Pinch [5] hasta 10 21 ), estos datos aún no confirman estas conjeturas.
Generalizaciones
La noción de número de Carmichael generaliza a una Carmichael ideales en cualquier campo de número K . Para cualquier ideal primo distinto de cero en , tenemos para todos en , dónde es la norma del ideal . (Esto generaliza el pequeño teorema de Fermat, quepara todos los enteros m cuando p es primo.) Llamar a un ideal distinto de cero en Carmichael si no es un ideal primo y para todos , dónde es la norma del ideal . Cuando K es, el ideal es principal , y si dejamos que a sea su generador positivo, entonces el ideales Carmichael exactamente cuando a es un número de Carmichael en el sentido habitual.
Cuando K es mayor que los racionales , es fácil escribir los ideales de Carmichael en: para cualquier número primo p que se divida completamente en K , el ideal principales un ideal de Carmichael. Dado que infinitos números primos se dividen completamente en cualquier campo numérico, hay infinitos ideales de Carmichael en. Por ejemplo, si p es cualquier número primo que sea 1 mod 4, el ideal ( p ) en los enteros gaussianos Z [ i ] 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 es libre de cuadrados y para todos los divisores primos de , es cierto que . 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 la OEIS )
Número cuasi-Carmichael
Los números cuasi-Carmichael son números compuestos n sin cuadrados con la propiedad de que para cada factor primo p de n , p + b divide n + b positivamente, siendo b cualquier número entero además de 0. Si b = −1, estos son números de Carmichael, y si b = 1, estos son números de Lucas-Carmichael. Los primeros números de Quasi-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 la OEIS )
Número de Knödel
Un n - número Knödel para un determinado número entero positivo n es un número compuesto m con la propiedad de que cada i < m primos entre sí a m satisface. El caso n = 1 son números de Carmichael.
Números de Carmichael de orden superior
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 n -ésima de aumento de potencia p n del anillo Z n de números enteros módulo n a sí mismo es la función identidad. La identidad es el único Z n - álgebra endomorphism en Z n para que podamos replantear la definición como pedir que p n ser un endomorfismo álgebra de Z n . Como antes, p n satisface la misma propiedad siempre que n es primo.
El n función th-potencia de fondos p n se define también en cualquier Z n -algebra A . Un teorema establece que n es primo si y solo 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 se puede generar 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 de 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. [19]
Propiedades
El criterio de Korselt se puede generalizar a números de Carmichael de orden superior, como lo muestra Howe.
Un argumento heurístico, dado 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. 126 (segunda ed.). Boston, MA: Birkhäuser. ISBN 978-0-8176-3743-9. Zbl 0821.11001 .
- ^ Crandall, Richard ; Pomerance, Carl (2005). Números primos: una perspectiva computacional (segunda ed.). Nueva York: Springer. pag. 133. ISBN 978-0387-25282-7.
- ^ 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 un pseudoprime de Euler-Jacobi para cada base relativamente primo. Usó el término pseudoprime fuerte , pero la terminología ha cambiado desde entonces. Los pseudoprimes fuertes son un subconjunto de los pseudoprimes de Euler-Jacobi. Por lo tanto, ningún número de Carmichael es un pseudoprime fuerte para cada base relativamente primo para él.
- ^ F. Arnault (agosto de 1995). "Construcción de números de Carmichael que son pseudoprimes fuertes a varias bases". Revista de Computación Simbólica . 20 (2): 151-161. doi : 10.1006 / jsco.1995.1042 .
- ^ a b c Pinch, Richard (diciembre de 2007). Anne-Maria Ernvall-Hytönen (ed.). Los números de Carmichael hasta 10 21 (PDF) . Actas de la conferencia sobre teoría algorítmica de números. 46 . Turku, Finlandia: Centro Turku de Ciencias de la Computación. 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 Carmichael debe ser un número cíclico impar"
- ^ Boceto de prueba: si es libre de cuadrados pero no cíclico, por dos factores primos y de . Pero si satisface a Korselt entonces , entonces por transitividad de la relación "divide" . Pero es también un factor de , una contradicción.
- ^ RD Carmichael (1910). "Nota sobre una nueva función de teoría de números" . Boletín de la American Mathematical Society . 16 (5): 232–238. doi : 10.1090 / s0002-9904-1910-01892-9 .
- ^ V. Šimerka (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 .
- ^ 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 .
- ^ Chernick, J. (1939). "Sobre el teorema simple de Fermat" (PDF) . Toro. Amer. Matemáticas. Soc . 45 (4): 269–274. doi : 10.1090 / S0002-9904-1939-06953-X .
- ^ a b WR Alford ; Andrew Granville ; Carl Pomerance (1994). "Hay infinitos números de Carmichael" (PDF) . Annals of Mathematics . 140 (3): 703–722. doi : 10.2307 / 2118576 . JSTOR 2118576 .
- ^ Thomas Wright (2013). "Infinitamente muchos números de Carmichael en progresiones aritméticas". Toro. London Math. 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 a través de 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 .
- ^ a b Erds, P. (1956). "Sobre pseudoprimes y números de Carmichael" (PDF) . Publ. Matemáticas. Debrecen . 4 : 201–206. Señor 0079031 .
- ^ Glyn Harman (2005). "Sobre el número de números de Carmichael hasta x ". Boletín de la London Mathematical Society . 37 (5): 641–650. doi : 10.1112 / S0024609305004686 .
- ^ 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 .
- ^ Pomerance, C. (1981). "Sobre la distribución de pseudoprimes" . Matemáticas. Comp . 37 (156): 587–593. doi : 10.1090 / s0025-5718-1981-0628717-0 . JSTOR 2007448 .
- ^ Everett W. Howe (octubre de 2000). "Números de Carmichael de orden superior". Matemáticas de la Computación . 69 (232): 1711-1719. arXiv : matemáticas.NT / 9812089 . Código Bibliográfico : 2000MaCom..69.1711H . doi : 10.1090 / s0025-5718-00-01225-4 . JSTOR 2585091 . S2CID 6102830 .
Referencias
- Carmichael, RD (1910). "Nota sobre una nueva función de teoría de números" . Boletín de la American Mathematical Society . 16 (5): 232–238. doi : 10.1090 / s0002-9904-1910-01892-9 .
- Carmichael, RD (1912). "En números compuestos P que satisfacen la congruencia de Fermat." American Mathematical Monthly . 19 (2): 22-27. Doi : 10.2307 / 2972687 . JSTOR 2.972.687 .
- Chernick, J. (1939). "Sobre el teorema simple de Fermat" (PDF) . Toro. Amer. Matemáticas. Soc . 45 (4): 269–274. doi : 10.1090 / S0002-9904-1939-06953-X .
- Korselt, AR (1899). "Problème chinois". L'Intermédiaire des Mathématiciens . 6 : 142-143.
- Löh, G .; Niebuhr, W. (1996). "Un nuevo algoritmo para construir grandes números de Carmichael" (PDF) . Matemáticas. Comp . 65 (214): 823–836. Código Bibliográfico : 1996MaCom..65..823L . doi : 10.1090 / S0025-5718-96-00692-8 .
- Ribenboim, P. (1989). El libro de los registros de números primos . Saltador. 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 .
enlaces externos
- "Número de Carmichael" , Encyclopedia of Mathematics , 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 10 18 {\ Displaystyle 10 ^ {18}}
- "La monotonía de 1729" . MathPages.com .
- Weisstein, Eric W. "Número de Carmichael" . MathWorld .
- Respuestas finales Aritmética modular