En teoría de números , una rama de las matemáticas , la función Carmichael λ ( n ) de un entero positivo n es el miembro más pequeño del conjunto de enteros positivos m que tienen la propiedad de que
La función Carmichael lleva el nombre del matemático estadounidense Robert Carmichael , quien la definió en 1910. [1] También se la conoce como función λ de Carmichael , función totiente reducida y función de mínimo exponente universal .
La siguiente tabla compara los primeros 36 valores de λ ( n ) (secuencia A002322 en la OEIS ) con la función totiente de Euler φ (en negrita si son diferentes; los ns tales que son diferentes se listan en OEIS : A033949 ).
Ejemplos numéricos
La función de Carmichael en 5 es 4, λ (5) = 4 , porque para cualquier número coprimo con 5, es decir , hay con , a saber, 1 1⋅4 = 1 4 ≡ 1 (mod 5) , 2 4 = 16 ≡ 1 (mod 5) , 3 4 = 81 ≡ 1 (mod 5) y 4 2⋅2 = 16 2 ≡ 1 2 (mod 5) . Y este m = 4 es el exponente más pequeño con esta propiedad, porque (y también). Además, la función totiente de Euler en 5 es 4, φ (5) = 4 , porque hay exactamente 4 números menores que y coprimos con 5 ( 1, 2, 3 y 4). El teorema de Euler asegura que a 4 ≡ 1 (mod 5) para todo coprimo a 5, y 4 es el exponente más pequeño. Tanto 2 como 3 son raíces λ primitivas módulo 5 y también raíces primitivas módulo 5.
La función de Carmichael en 8 es 2, λ (8) = 2 , porque para cualquier número un coprimo de 8, es decir, se cumple que a 2 ≡ 1 (mod 8) . Es decir, 1 1⋅2 = 1 2 ≡ 1 (mod 8) , 3 2 = 9 ≡ 1 (mod 8) , 5 2 = 25 ≡ 1 (mod 8) y 7 2 = 49 ≡ 1 (mod 8) . La función totiente de Euler en 8 es 4, φ (8) = 4 , porque hay exactamente 4 números menores que y coprimos con 8 (1, 3, 5 y 7). Además, el teorema de Euler asegura que a 4 ≡ 1 (mod 8) para todo coprimo a 8, pero 4 no es el exponente más pequeño. Las raíces primitivas λ módulo 8 son 3, 5 y 7. No hay raíces primitivas módulo 8.
Recurrencia para λ ( norte )
La función lambda de Carmichael de una potencia prima se puede expresar en términos del totiente de Euler. Cualquier número que no sea 1 o una potencia prima puede escribirse únicamente como producto de potencias primas distintas, en cuyo caso λ del producto es el mínimo común múltiplo de λ de los factores de potencia primos. Específicamente, λ ( n ) viene dada por la recurrencia
El totiente de Euler para una potencia prima, es decir, un número p r con p primo y r ≥ 1 , está dado por
teoremas de carmichael
Carmichael demostró dos teoremas que, en conjunto, establecen que si λ ( n ) se considera definido por la recurrencia de la sección anterior, entonces satisface la propiedad establecida en la introducción, es decir, que es el menor entero positivo m tal que para todos un primo relativo a n .
Teorema 1 : si a es primo relativo con respecto a n , entonces . [2]
Esto implica que el orden de cada elemento del grupo multiplicativo de números enteros módulo n divide a λ ( n ) . Carmichael llama a un elemento a para el cual es la potencia mínima de un congruente con 1 (mod n ) un módulo primitivo de raíz λ n . [3] (Esto no debe confundirse con un módulo raíz primitivo n , al que Carmichael a veces se refiere como módulo raíz primitivo n ).
Teorema 2 : Para cada entero positivo n existe un módulo raíz λ primitivo n . Además, si g es una de esas raíces, entonces hay raíces λ primitivas que son congruentes con potencias de g . [4]
Si g es una de las raíces λ primitivas garantizadas por el teorema, entonces no tiene soluciones enteras positivas m menores que λ ( n ) , lo que demuestra que no hay m < λ ( n ) positivo tal que para todos sea un primo relativo a n. .
El segundo enunciado del teorema 2 no implica que todas las raíces λ primitivas módulo n sean congruentes con potencias de una única raíz g . [5] Por ejemplo, si n = 15 , entonces λ ( n ) = 4 mientras que y . Hay cuatro raíces λ primitivas módulo 15, a saber, 2, 7, 8 y 13 como . Las raíces 2 y 8 son congruentes con potencias entre sí y las raíces 7 y 13 son congruentes con potencias entre sí, pero ni 7 ni 13 son congruentes con una potencia de 2 u 8 y viceversa. Los otros cuatro elementos del grupo multiplicativo módulo 15, a saber, 1, 4 (que satisface ), 11 y 14, no son raíces λ primitivas módulo 15.
Para un ejemplo contrastante, si n = 9 , entonces y . Hay dos raíces λ primitivas módulo 9, a saber, 2 y 5, cada una de las cuales es congruente a la quinta potencia de la otra. También son ambos primitivos : raíces módulo 9.
Propiedades de la función Carmichael
En esta sección, un número entero es divisible por un número entero distinto de cero si existe un número entero tal que . Esto está escrito como
Una consecuencia de la minimalidad de λ ( norte )
Supongamos que m ≡ 1 (mod n ) para todos los números es coprimo con n . Entonces λ ( n ) | m .
Prueba: Si m = kλ ( n ) + r con 0 ≤ r < λ ( n ) , entonces
para todos los números un coprimo con n . Se deduce que r = 0 ya que r < λ ( n ) y λ ( n ) es el exponente positivo mínimo para el cual la congruencia se cumple para todo coprimo con n .
λ ( norte )divide φ ( norte )
Esto se desprende de la teoría elemental de grupos , porque el exponente de cualquier grupo finito debe dividir el orden del grupo. λ ( n ) es el exponente del grupo multiplicativo de números enteros módulo n mientras que φ ( n ) es el orden de ese grupo. En particular, los dos deben ser iguales en los casos en que el grupo multiplicativo es cíclico debido a la existencia de una raíz primitiva , que es el caso de las potencias primas impares.
Por tanto, podemos ver el teorema de Carmichael como una mejora del teorema de Euler .
Divisibilidad
Prueba.
Por definición, para cualquier número entero con (y por tanto también ), tenemos que , y por tanto . Esto establece que para todo k es primo relativo a a . Por la consecuencia de la minimalidad demostrada anteriormente, tenemos .
Composición
Para todos los números enteros positivos a y b se cumple que
.
Esta es una consecuencia inmediata de la recurrencia de la función Carmichael.
Longitud del ciclo exponencial
Si es el mayor exponente en la factorización prima de n , entonces para todos a (incluidos aquellos que no son coprimos de n ) y todos r ≥ r max ,
En particular, para n libre de cuadrados ( r max = 1 ), para todo a tenemos
Valor promedio
Para cualquier n ≥ 16 : [6] [7]
(llamada aproximación de Erdős en lo sucesivo) con la constante
La siguiente tabla ofrece una descripción general de los primeros 2 26 – 1 =67 108 863 valores de la función λ , tanto para el promedio exacto como para su aproximación de Erdős.
Además, se proporciona una descripción general de los valores de “logaritmo sobre logaritmo” más fácilmente accesibles LoL( n ) := en λ ( norte )/en norte con
Jajaja( n ) > 4/5 ⇔ λ ( norte ) > norte 4/5 .
Allí, la entrada de la tabla en la fila número 26 en la columna
% jajaja > 4/5 → 60,49
indica que el 60,49% (≈40 000 000 ) de los números enteros 1 ≤ n ≤67 108 863 tienen λ ( n ) > n 4/5 lo que significa que la mayoría de losde λson exponenciales en la longitud l := log 2 ( n )de la entradan, es decir
Intervalo predominante
Para todos los números N y todos menos o ( N ) [8] enteros positivos n ≤ N (una mayoría "prevaleciente"):
con la constante [7]
límites inferiores
Para cualquier número suficientemente grande N y para cualquier Δ ≥ (ln ln N ) 3 , hay como máximo
enteros positivos n ≤ N tales que λ ( n ) ≤ ne −Δ . [9]
Orden mínima
Para cualquier secuencia n 1 < n 2 < n 3 < ⋯ de enteros positivos, cualquier constante 0 < c < 1/en 2 , y cualquier i suficientemente grande: [10] [11]
Valores pequeños
Para una constante c y cualquier A positiva suficientemente grande , existe un número entero n > A tal que [11]
Además, n es de la forma
para algún entero libre de cuadrados m < (ln A ) c ln ln ln A . [10]
Imagen de la función
El conjunto de valores de la función Carmichael tiene función de conteo [12]
Para n = p , un primo, el teorema 1 es equivalente al pequeño teorema de Fermat:
Para potencias primas p r , r > 1 , si
se cumple para algún número entero h , luego elevando ambos lados a la potencia p se obtiene
para algún otro número entero . Por inducción se deduce que para todo un primo relativo con p y por tanto con p r . Esto establece el teorema para n = 4 o cualquier potencia prima impar.
Afinando el resultado para potencias superiores de dos
Para un coprimo a (potencias de) 2 tenemos a = 1 + 2 h 2 para algún número entero h 2 . Entonces,
,
donde es un número entero. Con r = 3 , esto se escribe
Al elevar ambos lados al cuadrado se obtiene
donde es un número entero. Se deduce por inducción que
donde p 1 < p 2 < ... < p k son números primos y r 1 , r 2 , ... , rk son números enteros positivos. Los resultados para potencias primarias establecen que, para ,
^ Carmichael, Robert Daniel (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 .
^ Carmichaael (1914) p.40
^ Carmichael (1914) p.54
^ Carmichael (1914) p.55
^ Carmichael (1914) p.56
^ Teorema 3 en Erdős (1991)
^ ab Sándor y Crstici (2004) p.194
^ Teorema 2 en Erdős (1991) 3. Orden normal. (pág.365)
^ Teorema 5 en Friedlander (2001)
^ ab Teorema 1 en Erdős (1991)
^ ab Sándor y Crstici (2004) p.193
^ Vado, Kevin; Luca, Florián; Pomerance, Carl (27 de agosto de 2014). "La imagen de la función λ de Carmichael ". Álgebra y teoría de números . 8 (8): 2009-2026. arXiv : 1408.6506 . doi :10.2140/ant.2014.8.2009. S2CID 50397623.
^ Carmichael (1914) págs. 38-39
Referencias
Erdős, Paul ; Pomerancia, Carl ; Schmutz, Eric (1991). "Función lambda de Carmichael". Acta Aritmética . 58 (4): 363–385. doi : 10.4064/aa-58-4-363-385 . ISSN 0065-1036. SEÑOR 1121092. Zbl 0734.11047.
Friedlander, John B .; Pomerancia, Carl; Shparlinski, Igor E. (2001). "Periodo del generador de energía y pequeños valores de la función Carmichael". Matemáticas de la Computación . 70 (236): 1591–1605, 1803–1806. doi : 10.1090/s0025-5718-00-01282-5 . ISSN 0025-5718. SEÑOR 1836921. Zbl 1029.11043.
Sándor, Jozsef; Crstici, Borislav (2004). Manual de teoría de números II . Dordrecht: Académico Kluwer. págs. 32–36, 193–195. ISBN 978-1-4020-2546-4. Zbl 1079.11001.
Carmichael, Robert D. [1914]. La teoría de los números en el Proyecto Gutenberg