Función de Carmichael

Función en la teoría matemática de números

Función λ de Carmichael : λ ( n ) para 1 ≤ n ≤ 1000 (en comparación con la función φ de Euler )

En teoría de números , una rama de las matemáticas , la función de Carmichael λ ( n ) de un entero positivo n es el entero positivo más pequeño m tal que

${\displaystyle a^{m}\equiv 1{\pmod {n}}}$

se cumple para cada entero coprimo con n . En términos algebraicos, λ ( n ) es el exponente del grupo multiplicativo de los enteros módulo n . Como se trata de un grupo abeliano finito , debe existir un elemento cuyo orden sea igual al exponente, λ ( n ) . Tal elemento se denomina raíz λ primitiva módulo n .

La función de Carmichael recibe su nombre del matemático estadounidense Robert Carmichael , quien la definió en 1910. ^[1] También se conoce como función λ de Carmichael , función totiente reducida y función de exponente mínimo universal .

El orden del grupo multiplicativo de números enteros módulo n es φ ( n ) , donde φ es la función totiente de Euler . Como el orden de un elemento de un grupo finito divide el orden del grupo, λ ( n ) divide a φ ( n ) . La siguiente tabla compara los primeros 36 valores de λ ( n ) (secuencia A002322 en la OEIS ) y φ ( n ) (en negrita si son diferentes; los n tales que son diferentes se enumeran en la OEIS : A033949 ).

Ejemplos numéricos

• n = 5 . El conjunto de números menores que y coprimos con 5 es {1,2,3,4 }. Por lo tanto, la función totiente de Euler tiene valor φ (5) = 4 y el valor de la función de Carmichael, λ (5) , debe ser un divisor de 4. El divisor 1 no satisface la definición de la función de Carmichael ya queexcepto para. Tampoco lo hace 2 ya que. Por lo tanto λ (5) = 4 . De hecho,. Tanto 2 como 3 son raíces primitivas λ módulo 5 y también raíces primitivas módulo 5. ${\displaystyle a^{1}\not \equiv 1{\pmod {5}}}$ ${\displaystyle a\equiv 1{\pmod {5}}}$ ${\displaystyle 2^{2}\equiv 3^{2}\equiv 4\not \equiv 1{\pmod {5}}}$ ${\displaystyle 1^{4}\equiv 2^{4}\equiv 3^{4}\equiv 4^{4}\equiv 1{\pmod {5}}}$
• n = 8 . El conjunto de números menores que y coprimos con 8 es {1,3,5,7} . Por lo tanto φ (8) = 4 y λ (8) debe ser divisor de 4. De hecho λ (8) = 2 ya que. Las raíces primitivas λ módulo 8 son 3, 5 y 7. No hay raíces primitivas módulo 8. ${\displaystyle 1^{2}\equiv 3^{2}\equiv 5^{2}\equiv 7^{2}\equiv 1{\pmod {8}}}$

Recurrencia de λ ( n )

La función lambda de Carmichael de una potencia prima se puede expresar en términos del tociente de Euler. Cualquier número que no sea 1 o una potencia prima se puede escribir de forma única como el producto de potencias primas distintas, en cuyo caso λ del producto es el mínimo común múltiplo de λ de los factores de potencia prima. Específicamente, λ ( n ) viene dado por la recurrencia

${\displaystyle \lambda (n)={\begin{cases}\varphi (n)&{\text{if }}n{\text{ is 1, 2, 4, or an odd prime power,}}\\{\tfrac {1}{2}}\varphi (n)&{\text{if }}n=2^{r},\ r\geq 3,\\\operatorname {lcm} {\Bigl (}\lambda (n_{1}),\lambda (n_{2}),\ldots ,\lambda (n_{k}){\Bigr )}&{\text{if }}n=n_{1}n_{2}\ldots n_{k}{\text{ where }}n_{1},n_{2},\ldots ,n_{k}{\text{ are powers of distinct primes.}}\end{cases}}}$

El totiente de Euler para una potencia prima, es decir, un número p ^r con p primo y r ≥ 1 , está dado por

${\displaystyle \varphi (p^{r}){=}p^{r-1}(p-1).}$

Teoremas de Carmichael

Carmichael demostró dos teoremas que, en conjunto, establecen que si λ ( n ) se considera como definido por la recurrencia de la sección anterior, entonces satisface la propiedad establecida en la introducción, es decir, que es el entero positivo más pequeño m tal que para todo primo relativo a n . ${\displaystyle a^{m}\equiv 1{\pmod {n}}}$

Teorema 1  :  Si a es relativamente primo a n entonces . ^[2] ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$

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 menor potencia de a congruente con 1 (mod n ) una raíz λ-primitiva módulo n . ^[3] (Esto no debe confundirse con una raíz primitiva módulo n , a la que Carmichael a veces se refiere como una raíz primitiva módulo n ). ${\displaystyle a^{\lambda (n)}}$ ${\displaystyle \varphi }$

Teorema 2  :  Para cada entero positivo n existe una raíz λ primitiva módulo n . Además, si g es una raíz de este tipo, entonces existen raíces λ primitivas que son congruentes con potencias de g . ^[4] ${\displaystyle \varphi (\lambda (n))}$

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 ningún m < λ ( n ) positivo tal que para todo a primo relativo a n . ${\displaystyle g^{m}\equiv 1{\pmod {n}}}$ ${\displaystyle a^{m}\equiv 1{\pmod {n}}}$

El segundo enunciado del Teorema 2 no implica que todas las raíces λ primitivas módulo n sean congruentes con potencias de una sola 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. ${\displaystyle \varphi (n)=8}$ ${\displaystyle \varphi (\lambda (n))=2}$ ${\displaystyle 1\equiv 2^{4}\equiv 8^{4}\equiv 7^{4}\equiv 13^{4}}$ ${\displaystyle 4\equiv 2^{2}\equiv 8^{2}\equiv 7^{2}\equiv 13^{2}}$

Por ejemplo, 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 con la quinta potencia de la otra. También son ambas raíces primitivas módulo 9. ${\displaystyle \lambda (n)=\varphi (n)=6}$ ${\displaystyle \varphi (\lambda (n))=2}$ ${\displaystyle \varphi }$

Propiedades de la función de Carmichael

En esta sección, un entero es divisible por un entero distinto de cero si existe un entero tal que . Esto se escribe como ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle n=km}$

${\displaystyle m\mid n.}$

Una consecuencia de la minimidad de λ ( n )

Supóngase que a ^m ≡ 1 (mod n ) para todos los números a coprimos con n . Entonces λ ( n ) | m .

Demostración: Si m = kλ ( n ) + r con 0 ≤ r < λ ( n ) , entonces

${\displaystyle a^{r}=1^{k}\cdot a^{r}\equiv \left(a^{\lambda (n)}\right)^{k}\cdot a^{r}=a^{k\lambda (n)+r}=a^{m}\equiv 1{\pmod {n}}}$

para todos los números a coprimos con n . Se deduce que r = 0 ya que r < λ ( n ) y λ ( n ) es el exponente positivo mínimo para el cual se cumple la congruencia para todos los a coprimos con n .

λ ( n )divide φ ( n )

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 primos impares.

Por lo tanto, podemos considerar el teorema de Carmichael como una agudización del teorema de Euler .

Divisibilidad

${\displaystyle a\,|\,b\Rightarrow \lambda (a)\,|\,\lambda (b)}$

Prueba.

Por definición, para cualquier entero con (y por lo tanto también ), tenemos que , y por lo tanto . Esto establece que para todo k primo relativo a a . Por la consecuencia de minimalidad demostrada anteriormente, tenemos . ${\displaystyle k}$ ${\displaystyle \gcd(k,b)=1}$ ${\displaystyle \gcd(k,a)=1}$ ${\displaystyle b\,|\,(k^{\lambda (b)}-1)}$ ${\displaystyle a\,|\,(k^{\lambda (b)}-1)}$ ${\displaystyle k^{\lambda (b)}\equiv 1{\pmod {a}}}$ ${\displaystyle \lambda (a)\,|\,\lambda (b)}$

Composición

Para todos los números enteros positivos a y b se cumple que

${\displaystyle \lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))}$.

Esta es una consecuencia inmediata de la recurrencia de la función de Carmichael.

Duración del ciclo exponencial

Si es el mayor exponente en la factorización prima de n , entonces para todos los a (incluidos aquellos que no son coprimos con n ) y todos los r ≥ r _max , ${\displaystyle r_{\mathrm {max} }=\max _{i}\{r_{i}\}}$ ${\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}}$

${\displaystyle a^{r}\equiv a^{\lambda (n)+r}{\pmod {n}}.}$

En particular, para n libre de cuadrados ( r _max = 1 ), para todo a tenemos

${\displaystyle a\equiv a^{\lambda (n)+1}{\pmod {n}}.}$

Valor medio

Para cualquier n ≥ 16 : ^{[6] [7]}

${\displaystyle {\frac {1}{n}}\sum _{i\leq n}\lambda (i)={\frac {n}{\ln n}}e^{B(1+o(1))\ln \ln n/(\ln \ln \ln n)}}$

(llamada aproximación de Erdős en lo sucesivo) con la constante

${\displaystyle B:=e^{-\gamma }\prod _{p\in \mathbb {P} }\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0.34537}$

y γ ≈ 0,57721 , la constante de Euler-Mascheroni .

La siguiente tabla ofrece una descripción general de los primeros 2 ²⁶ – 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 ofrece una descripción general de los valores de "logaritmo sobre logaritmo" más accesibles LoL( n ) := ⁠en λ ( n )/en n⁠ con

• LoL( n ) > ⁠4/5⁠ ⇔ λ ( n ) > n ^⁠4/5⁠ .

Allí, la entrada de la tabla en la fila número 26 en la columna

•  % LoL > ⁠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 losλson exponenciales en la longitud l  := log ₂ ( n )de la entradan, es decir

${\displaystyle \left(2^{\frac {4}{5}}\right)^{l}=2^{\frac {4l}{5}}=\left(2^{l}\right)^{\frac {4}{5}}=n^{\frac {4}{5}}.}$

Intervalo prevaleciente

Para todos los números N y todos excepto o ( N ) ^[8] los enteros positivos n ≤ N (una mayoría "prevaleciente"):

${\displaystyle \lambda (n)={\frac {n}{(\ln n)^{\ln \ln \ln n+A+o(1)}}}}$

con la constante ^[7]

${\displaystyle A:=-1+\sum _{p\in \mathbb {P} }{\frac {\ln p}{(p-1)^{2}}}\approx 0.2269688}$

Límites inferiores

Para cualquier número suficientemente grande N y para cualquier Δ ≥ (ln ln N ) ³ , hay como máximo

${\displaystyle N\exp \left(-0.69(\Delta \ln \Delta )^{\frac {1}{3}}\right)}$

números enteros positivos n ≤ N tales que λ ( n ) ≤ ne ^−Δ . ^[9]

Pedido mínimo

Para cualquier secuencia n ₁ < n ₂ < n ₃ < ⋯ de números enteros positivos, cualquier constante 0 < c < ⁠ 1/en 2⁠ , y cualquier i suficientemente grande: ^{[10] [11]}

${\displaystyle \lambda (n_{i})>\left(\ln n_{i}\right)^{c\ln \ln \ln n_{i}}.}$

Valores pequeños

Para una constante c y cualquier A positivo suficientemente grande , existe un entero n > A tal que ^[11]

${\displaystyle \lambda (n)<\left(\ln A\right)^{c\ln \ln \ln A}.}$

Además, n tiene la forma

${\displaystyle n=\mathop {\prod _{q\in \mathbb {P} }} _{(q-1)|m}q}$

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]

${\displaystyle {\frac {x}{(\ln x)^{\eta +o(1)}}},}$

dónde

${\displaystyle \eta =1-{\frac {1+\ln \ln 2}{\ln 2}}\approx 0.08607}$

Uso en criptografía

La función Carmichael es importante en criptografía debido a su uso en el algoritmo de cifrado RSA .

Prueba del teorema 1

Para n = p , un primo, el Teorema 1 es equivalente al pequeño teorema de Fermat:

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}\qquad {\text{for all }}a{\text{ coprime to }}p.}$

Para potencias primas p ^r , r > 1 , si

${\displaystyle a^{p^{r-1}(p-1)}=1+hp^{r}}$

se cumple para algún entero h , entonces elevando ambos lados a la potencia p obtenemos

${\displaystyle a^{p^{r}(p-1)}=1+h'p^{r+1}}$

para algún otro entero . Por inducción se sigue que para todo primo relativo a p y, por lo tanto, a p ^r . Esto establece el teorema para n = 4 o cualquier potencia prima impar. ${\displaystyle h'}$ ${\displaystyle a^{\varphi (p^{r})}\equiv 1{\pmod {p^{r}}}}$

Afilando el resultado para potencias de dos más altas

Para un coprimo de (potencias de) 2 tenemos a = 1 + 2 h ₂ para algún entero h ₂ . Entonces,

${\displaystyle a^{2}=1+4h_{2}(h_{2}+1)=1+8{\binom {h_{2}+1}{2}}=:1+8h_{3}}$,

donde es un entero. Con r = 3 , esto se escribe ${\displaystyle h_{3}}$

${\displaystyle a^{2^{r-2}}=1+2^{r}h_{r}.}$

Elevando al cuadrado ambos lados se obtiene

${\displaystyle a^{2^{r-1}}=\left(1+2^{r}h_{r}\right)^{2}=1+2^{r+1}\left(h_{r}+2^{r-1}h_{r}^{2}\right)=:1+2^{r+1}h_{r+1},}$

donde es un entero. Se deduce por inducción que ${\displaystyle h_{r+1}}$

${\displaystyle a^{2^{r-2}}=a^{{\frac {1}{2}}\varphi (2^{r})}\equiv 1{\pmod {2^{r}}}}$

para todos y todos coprimos a . ^[13] ${\displaystyle r\geq 3}$ ${\displaystyle 2^{r}}$

Números enteros con múltiples factores primos

Por el teorema de factorización única , cualquier n > 1 puede escribirse de manera única como

${\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}}$

donde p ₁ < p ₂ < ... < p _k son primos y r ₁ , r ₂ , ..., r _k son números enteros positivos. Los resultados para potencias primos establecen que, para , ${\displaystyle 1\leq j\leq k}$

${\displaystyle a^{\lambda \left(p_{j}^{r_{j}}\right)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n{\text{ and hence to }}p_{i}^{r_{i}}.}$

De esto se deduce que

${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n,}$

donde, como lo indica la recurrencia,

${\displaystyle \lambda (n)=\operatorname {lcm} {\Bigl (}\lambda \left(p_{1}^{r_{1}}\right),\lambda \left(p_{2}^{r_{2}}\right),\ldots ,\lambda \left(p_{k}^{r_{k}}\right){\Bigr )}.}$

Del teorema del resto chino se concluye que

${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}\qquad {\text{for all }}a{\text{ coprime to }}n.}$

Véase también

• Número de Carmichael

Notas

1. Carmichael, Robert Daniel (1910). "Nota sobre una nueva función de la 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 .
2. Carmichael (1914) pág. 40
3. Carmichael (1914) pág. 54
4. Carmichael (1914) pág. 55
5. Carmichael (1914) pág. 56
6. Teorema 3 en Erdős (1991)
7. Sándor y Crstici (2004) p.194
8. Teorema 2 en Erdős (1991) 3. Orden normal. (pág.365)
9. Teorema 5 en Friedlander (2001)
10. Teorema 1 en Erdős (1991)
11. Sándor y Crstici (2004) p.193
12. Ford, Kevin; Luca, Florian; 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.
13. 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. ; Pomerance, Carl; Shparlinski, Igor E. (2001). "Período del generador de potencia y pequeños valores de la función de Carmichael". Matemáticas de la computación . 70 (236): 1591–1605, 1803–1806. doi : 10.1090/s0025-5718-00-01282-5 . ISSN  0025-5718. MR  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