Función de Carmichael

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

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

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

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

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

El orden del grupo multiplicativo de enteros módulo $n$ es $φ$ $($ $n$ $)$ , donde $φ$ es la función totiente de Euler . Dado que 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 el OEIS ) y $φ$ $($ $n$ $)$ (en negrita si son diferentes; los valores de $n$ tales que son diferentes se enumeran en (secuencia A033949 en el OEIS ) ).

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 que $a^{1}\not \equiv 1{\pmod {5}}$ excepto $a\equiv 1{\pmod {5}}$ . Tampoco lo hace 2 ya que $2^{2}\equiv 3^{2}\equiv 4\not \equiv 1{\pmod {5}}$ . Por lo tanto, $λ$ $(5) = 4$ . En efecto, $1^{4}\equiv 2^{4}\equiv 3^{4}\equiv 4^{4}\equiv 1{\pmod {5}}$ . Tanto 2 como 3 son raíces $λ$ primitivas módulo 5 y también raíces primitivas módulo 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 un divisor de 4. De hecho, $λ$ $(8) = 2$ ya que $1^{2}\equiv 3^{2}\equiv 5^{2}\equiv 7^{2}\equiv 1{\pmod {8}}$ . Las raíces primitivas $λ$ módulo 8 son 3, 5 y 7. No hay raíces primitivas módulo 8.

Recurrencia para $λ$ $($ $n$ $)$

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 ni una potencia prima se puede escribir de forma única como el producto de distintas potencias primas, en cuyo caso $λ$ del producto es el mínimo común múltiplo de $λ$ de los factores de potencia prima. Específicamente, $λ$ $($ $n$ $)$ viene dada por la recurrencia

\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}}

La totiente de Euler para una potencia prima, es decir, un número $p$ $r$ con $p$ primo y $r$ $\geq 1$ , viene dada por

\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 se define por la recurrencia de la sección anterior, entonces satisface la propiedad enunciada en la introducción, a saber, que es el entero positivo más pequeño $m$ tal que $a^{m}\equiv 1{\pmod {n}}$ para todo $a$ relativamente primo a $n$ .

Teorema 1 — Si $a$ es primo relativo a $n,$ entonces $a^{\lambda (n)}\equiv 1{\pmod {n}}$ . ^{[ 2 ]}

Esto implica que el orden de cada elemento del grupo multiplicativo de enteros módulo $n$ divide a $λ$ $($ $n$ $)$ . Carmichael llama a un elemento $a$ para el cual $a^{\lambda (n)}$ es la menor potencia de $una$ congruente a 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 $\varphi$ -raíz módulo $n$ .)

Teorema 2 — Para cada entero positivo $n$ existe una raíz $λ$ primitiva módulo $n$ . Además, si $g$ es tal raíz, entonces existen $\varphi (\lambda (n))$ $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$ $g^{m}\equiv 1{\pmod {n}}$ no tiene soluciones enteras positivas $m$ menores que $λ$ $($ $n$ $)$ , lo que demuestra que no existe ningún $m$ $<$ $λ$ $($ $n$ $)$ positivo tal que $a^{m}\equiv 1{\pmod {n}}$ para todo $a$ relativamente primo a $n$ .

La segunda afirmación 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 $\varphi (n)=8$ y $\varphi (\lambda (n))=2$ . Hay cuatro raíces $λ$ primitivas módulo 15, a saber, 2, 7, 8 y 13 como $1\equiv 2^{4}\equiv 8^{4}\equiv 7^{4}\equiv 13^{4}$ Las raíces 2 y 8 son congruentes a potencias entre sí, y las raíces 7 y 13 son congruentes a potencias entre sí, pero ni 7 ni 13 son congruentes a una potencia de 2 u 8, y viceversa. Los otros cuatro elementos del grupo multiplicativo módulo 15, a saber, 1, 4 (que satisface $4\equiv 2^{2}\equiv 8^{2}\equiv 7^{2}\equiv 13^{2}$ ), 11 y 14 no son raíces $λ$ primitivas módulo 15.

Por ejemplo contrastante, si $n$ $= 9$ , entonces $\lambda (n)=\varphi (n)=6$ y $\varphi (\lambda (n))=2$ 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. Ambas son también primitivas. $\varphi$ -raíces módulo 9.

Propiedades de la función de Carmichael

En esta sección, un número entero $n$ es divisible por un número entero distinto de cero $m$ si existe un número entero $k$ de tal manera que $n=km$ Esto está escrito como

m\mid n.

Una consecuencia de la minimalidad de $λ$ $($ $n$ $)$

Supongamos $que$ $m$ $\equiv 1 (mod$ $n$ $)$ para todos los números $coprimos$ con $n$ . Entonces $λ$ $($ $n$ $) |$ $m$ .

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

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 $coprimos$ con $n$ . De ello se deduce que $r = 0$ puesto que $r$ $<$ $λ$ $($ $n$ $)$ y $λ$ $($ $n$ $)$ es el exponente positivo mínimo para el cual la congruencia se cumple para todos $los números$ coprimos con $n$ .

$λ (n)$ divide $a φ$ $($ $n$ $)$

Esto se deduce de la teoría elemental de grupos , ya que el exponente de cualquier grupo finito debe dividir el orden del grupo. $λ$ $($ $n$ $)$ es el exponente del grupo multiplicativo de los enteros módulo $n,$ mientras que $φ$ $($ $n$ $)$ es el orden de dicho grupo. En particular, ambos deben ser iguales en los casos en que el grupo multiplicativo es cíclico debido a la existencia de una raíz primitiva , como ocurre con las potencias de primos impares.

Podemos considerar, por lo tanto, el teorema de Carmichael como una versión más precisa del teorema de Euler .

Divisibilidad

a\,|\,b\Rightarrow \lambda (a)\,|\,\lambda (b)

Prueba.

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

Composición

Para todos los enteros positivos $a$ y $b$ se cumple que

\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 $r_{\mathrm {max} }=\max _{i}\{r_{i}\}$ es el mayor exponente en la factorización prima $n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}$ de $n$ , entonces para todo $a$ (incluidos aquellos que no son coprimos con $n$ ) y todo $r$ $\geq$ $r$ $max$ ,

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

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

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

Valor promedio

Para cualquier $n$ $\geq 16$ : ^[⁶^]^[⁷^]

{\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)}

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

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

y $γ$ $\approx 0,57721$ , la constante de Euler-Mascheroni .

La siguiente tabla ofrece una visión general de los primeros $226 - 1 = 67108863$ 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 "logaritmo sobre logaritmo" más accesibles $LoL(n) := ⁠ ln λ (n) / ln n ⁠$ con

$LoL (n$ ) $>$ $4$ $/$ $5$ $\Leftrightarrow$ $λ$ $($ $n$ $)$ $>$ $n$ $4$ $/$ $5$ $.$ $$

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

$% LoL > 4 / 5 \to$ 60,49

indica que el 60,49% (≈40 000 000 ) de los enteros $1 \leq n \leq 67108863$ tienen $λ$ $($ $n$ $) >$ $n$ $⁠$ $4$ $/$ $5$ $⁠$ lo que significa que la mayoría de los $valores de λ$ son exponenciales en la longitud $l$ $:= log$ $2$ $($ $n$ $)$ de la entrada $n$ , es decir

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

Intervalo predominante

Para todos los números $N$ y todos los enteros positivos $n$ $\leq$ $N excepto$ $o$ $($ $N$ $)$ ^[⁸^] (una mayoría "predominante"):

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

con la constante ^{[ 7 ]}

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

límites inferiores

$Para cualquier número N$ suficientemente grande y para cualquier $Δ \geq (ln ln N) 3$ , hay como máximo

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

enteros positivos $n$ $\leq N$ tales que $λ$ $($ $n$ $) \leq$ $ne$ $-Δ$ . ^[⁹^]

Pedido mínimo

Para cualquier secuencia $n$ $1$ $<$ $n$ $2$ $<$ $n$ $3$ $< \dots$ de enteros positivos, cualquier constante $0 <$ $c$ $<$ $⁠$ $1$ $/$ $ln 2$ $⁠$ , y cualquier $i$ suficientemente grande : ^[¹⁰^]^[¹¹^]

\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 ^[¹¹^]

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

Además, $n$ es de la forma

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$ . ^[¹⁰^]

Imagen de la función

El conjunto de valores de la función de Carmichael tiene función de conteo ^{[ 12 ]}

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

dónde

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

Uso en criptografía

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

Demostración del Teorema 1

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

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

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

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

se cumple para algún entero $h$ , entonces elevar ambos lados a la potencia $p$ da

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

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

Mejorar el resultado para potencias más altas de dos

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

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

,

dónde $h_{3}$ es un número entero. Con $r = 3$ , esto se escribe

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

Elevando al cuadrado ambos lados obtenemos

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},

dónde $h_{r+1}$ es un número entero. Por inducción se deduce que

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

a pesar de $r\geq 3$ y todos $son$ coprimos a $2^{r}$ . ^{[ 13 ]}

Números enteros con múltiples factores primos

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

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

donde $p$ $1$ $<$ $p$ $2$ $< ... <$ $p$ $k$ son primos y $r$ $1$ $,$ $r$ $2$ $, ...,$ $r$ $k$ son enteros positivos. Los resultados para potencias de primos establecen que, para $1\leq j\leq k$ ,

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

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

donde, según lo dado por la recurrencia,

\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 chino del resto se concluye que

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

↑ 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 .
↑ Carmichael (1914) pág. 40
↑ Carmichael (1914) pág. 54
↑ Carmichael (1914) pág. 55
↑ Carmichael (1914) pág. 56
↑ Teorema 3 en Erdős (1991)
^ Sándor y Crstici (2004) p.194
↑ Teorema 2 en Erdős (1991) 3. Orden normal. (pág.365)
↑ Teorema 5 en Friedlander (2001)
1 2 Teorema 1 en Erdős (1991)
^ Sándor y Crstici (2004) p.193
↑ 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 .
↑ 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). "Periodo del generador de potencia y valores pequeños de la función de Carmichael" . Mathematics of Computation . 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 a 36, 193 a 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.

[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)

[HBII194-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)

[Theorem_1_in_Erdős_(1991)-10] 1 2 Teorema 1 en Erdős (1991)

[HBII193-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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

[

[

[

[

[

[ 12 ]

[ 13 ]