función carmichael

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

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

se cumple para cada número entero $un$ coprimo para $n$ . En términos algebraicos, $λ$ $($ $n$ $)$ es el exponente del grupo multiplicativo de números 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 llama primitivo $λ$ -raíz módulo $n$ .

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\cdot4$ $= 1$ $4$ $\equiv 1 (mod 5)$ , $2$ $4$ $= 16 \equiv 1 (mod 5)$ , $3$ $4$ $= 81 \equiv 1 (mod 5)$ y $4$ $2\cdot2$ $= 16$ $2$ $\equiv 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$ $\equiv 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. $0<a<5$ $a\en \{1,2,3,4\}~,$ $a^{m}\equiv 1\,({\text{mod }}5)$ $m=4,$ $2^{2}=4\not \equiv 1\,({\text{mod }}5)$ $3^{2}=9\not \equiv 1\,({\text{mod }}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$ $\equiv 1 (mod 8)$ . Es decir, $1$ $1\cdot2$ $= 1$ $2$ $\equiv 1 (mod 8)$ , $3$ $2$ $= 9 \equiv 1 (mod 8)$ , $5$ $2$ $= 25 \equiv 1 (mod 8)$ y $7$ $2$ $= 49 \equiv 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$ $\equiv 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. $a\en \{1,3,5,7\}~,$

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

\lambda (n)={\begin{cases}\varphi (n)&{\text{si }}n{\text{ es 1, 2, 4 o una potencia prima impar,}}\\ {\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{si }}n=n_{1}n_{2 }\ldots n_{k}{\text{ donde }}n_{1},n_{2},\ldots ,n_{k}{\text{ son potencias de números primos distintos.}}\end{cases}}

El totiente de Euler para una potencia prima, es decir, un número $p$ $r$ con $p$ primo y $r$ $\geq 1$ , está dado 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 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$ . $a^{m}\equiv 1{\pmod {n}}$

Teorema 1 : si $a$ es primo relativo con respecto a $n$ , entonces . ^[2] $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 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$ ). $a^{\lambda (n)}$ $\varphi$

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] $\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 $m$ $<$ $λ$ $($ $n$ $)$ positivo tal que para todos $un$ primo relativo a $n$ . $g^{m}\equiv 1{\pmod {n}}$ $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 ú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. $\varphi (n)=8$ $\varphi (\lambda (n))=2$ $1\equiv 2^{4}\equiv 8^{4}\equiv 7^{4}\equiv 13^{4}$ $4\equiv 2^{2}\equiv 8^{2}\equiv 7^{2}\equiv 13^{2}$

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. $\lambda (n)=\varphi (n)=6$ $\varphi (\lambda (n))=2$ $\varphi$

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 $n$ $m$ $k$ $n=km$

m\mid n.

Una consecuencia de la minimalidad de λ ( n )

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

Prueba: 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 $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$ .

λ ( 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 primas impares.

Por tanto, podemos ver el teorema de Carmichael como una mejora del teorema de Euler .

Divisibilidad

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

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 . $k$ $\gcd(k,b)=1$ $\gcd(k,a)=1$ $b\,|\,(k^{\lambda (b)}-1)$ $a\,|\,(k^{\lambda (b)}-1)$ $k^{\lambda (b)}\equiv 1{\pmod {a}}$ $\lambda (a)\,|\,\lambda (b)$

Composición

Para todos los números 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 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$ $\geq$ $r$ $max$ , $r_{\mathrm {max} }=\max _{i}\{r_{i}\}$ ${\ Displaystyle n = p_ {1} ^ {r_ {1}} p_ {2} ^ {r_ {2}} \ cdots p_ {k} ^ {r_ {k}}}$

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$ : ^[6]^[7]

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

B:=e^{-\gamma }\prod _{p\in \mathbb {P} }\left({1-{\frac {1}{(p-1)^{2}(p +1)}}}\derecha)\aproximadamente 0,34537

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

La siguiente tabla ofrece una descripció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 ofrece una descripción general de los valores de “logaritmo sobre logaritmo” más fácilmente accesibles $LoL( n ):=.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}en λ ( norte )/en norte$ con

$jajaja(n) > 4 / 5 \Leftrightarrow λ (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 \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 menos $o$ $($ $N$ $)$ ^[8] enteros positivos $n$ $\leq$ $N$ (una mayoría "prevaleciente"):

\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}}}\aproximadamente 0,2269688

límites inferiores

Para cualquier número suficientemente grande $N$ 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$ $-Δ$ . ^[9]

Orden mínima

Para cualquier secuencia $n$ $1$ $<$ $n$ $2$ $<$ $n$ $3$ $< \dots$ de enteros positivos, cualquier constante $0 <$ $c$ $<$ $1 / en 2$ $, y cualquier i$ suficientemente grande : ^[10]^[11]

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

Valores pequeños

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

\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$ . ^[10]

Imagen de la función

El conjunto de valores de la función 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 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:

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 número entero $h$ , luego elevando ambos lados a la potencia $p$ se obtiene

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

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. $h'$ $a^{\varphi (p^{r})}\equiv 1{\pmod {p^{r}}}$

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,

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

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

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

Al elevar ambos lados al cuadrado se obtiene

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 número entero. Se deduce por inducción que $h_{r+1}$

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

para todos y todas $un$ coprime para . ^[13] $r\geq 3$ $2^{r}$

Enteros con múltiples factores primos

Según el teorema de factorización única , cualquier $n$ $> 1$ se puede escribir de forma única como

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

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

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

Ver también

número de carmichael

Notas

^ 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