La función del indicador de Carmichael , o el indicador de Carmichael o incluso la función de Carmichael , señalada como λ , se define en números naturales estrictamente positivos; asocia con un número entero n el número entero más pequeño m que satisface, para cualquier número entero un primo con n , a m ≡ 1 mod n . Es presentado por Robert Daniel Carmichael en un artículo de 1910.
La indicatriz de Carmichael λ tiene una estrecha relación con la función indicatriz de Euler φ , en particular λ ( n ) divide φ ( n ) . Las dos funciones coinciden en 1, 2, 4, las potencias de un número primo impar y sus dobles, pero difieren en todas partes.
Los enteros una primos con n son exactamente aquellas que son invertible módulo n (por el Bachet-Bézout teorema y su recíproco). Así que si dos números enteros m y k satisfacen una m ≡ 1 mod n y un k ≡ 1 mod n , el resto de la división euclidiana de uno por el otro también. Por tanto, la definición puede reformularse:
Luego deducimos del teorema de Euler que:
La definición también resulta, según el teorema del resto chino, que:
La definición se puede reformular utilizando la teoría de grupos . Un entero un prime con n es exactamente un número entero cuya clase de módulo n es un elemento invertible del anillo ℤ / n ℤ , es decir, un elemento del grupo multiplicativo (ℤ / n ℤ) *. Por definición, el entero más pequeño m que satisface α m = 1 para cualquier elemento α de un grupo se llama exponente de este grupo y, por lo tanto:
Otra caracterización del exponente da
Por tanto, encontramos que λ ( n ) divide φ ( n ) que es el cardinal, u orden, del grupo (ℤ / n ℤ) * y, por tanto, un múltiplo común de los órdenes de sus elementos (según el teorema de Lagrange ).
En un grupo conmutativo finito, como (ℤ / n ℤ) *, existe un elemento de orden el exponente, es decir que:
Inmediatamente deducimos que:
Cuando p es primo, ℤ / p ℤ es un campo finito (primo), y su grupo multiplicativo (ℤ / p ℤ) * es entonces cíclico. Entonces :
No siempre tenemos λ ( n ) = φ ( n ) : el grupo multiplicativo (ℤ / 8 ℤ) * es el grupo de Klein , de orden 4 y exponente 2, por lo tanto tenemos λ (8) = 2 pero φ (8 ) = 4 .
No son solo los números primos para los que las funciones φ y λ toman el mismo valor: comprobamos que (ℤ / 4 ℤ) * y (ℤ / 6 ℤ) * son de orden 2, por lo tanto λ (4) = φ ( 4) = 2 y λ (6) = φ (6) = 2 , (ℤ / 9 ℤ) * es de orden φ (9) = 6 , y 2 es un elemento de orden 6 de (ℤ / 9 ℤ) * por lo tanto, λ (9) = φ (9) = 6 (los casos en los que φ ( n ) = λ ( n ) se especifican en el siguiente párrafo).
La siguiente oeis: A002322 da los primeros valores de la función λ de Carmichael (y propone otros en las referencias). Los primeros 36 valores de la función λ se dan en la siguiente tabla, con los del correspondiente índice de Euler φ .
no | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
λ ( n ) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 2 | 6 | 4 | 10 | 2 | 12 | 6 | 4 | 4 | dieciséis | 6 | 18 | 4 | 6 | 10 | 22 | 2 | 20 | 12 | 18 | 6 | 28 | 4 | 30 | 8 | 10 | dieciséis | 12 | 6 |
φ ( n ) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 | 12 | 6 | 8 | 8 | dieciséis | 6 | 18 | 8 | 12 | 10 | 22 | 8 | 20 | 12 | 18 | 12 | 28 | 8 | 30 | dieciséis | 20 | dieciséis | 24 | 12 |
Sabemos cómo calcular λ ( m × n ) sabiendo λ ( m ) y λ ( n ) cuando m y n son primos entre sí. Por tanto, podemos calcular λ ( n ) a partir de la descomposición en factores primos de n , si sabemos cómo calcular λ ( p r ) para p un número primo, que obtenemos estudiando los grupos multiplicativos correspondientes:
Luego obtenemos una caracterización más computacional de la función indicadora de Carmichael (a veces tomada como definición, en particular en el artículo original de Carmichael).
Teorema de Carmichael. - La función del indicador de Carmichael es la función λ definida en enteros estrictamente positivos por:
La función indicadora de Carmichael toma el mismo valor que la función indicadora de Euler en n si y solo si el grupo (ℤ / n ℤ) * es cíclico, es decir, si y solo si:
(el siguiente oeis: A034380 enumera los primeros valores del cocienteφ ( n )λ ( n ), y ofrece otros datos como referencias).
Deducimos, ya sea de la definición, o de la forma más explícita dada por el teorema, que:
en particular :
Cuando n es un número sin un factor cuadrado, es decir, n es el producto de números primos distintos p 1 , ..., p k :
Los números de Carmichael son números naturales n que no son los primeros pero que, sin embargo, satisfacen la conclusión del pequeño teorema de Fermat , a saber:
para cualquier número entero un primo con n , a n - 1 ≡ 1 mod n .Carmichael los estudia en el mismo artículo donde introduce su función indicadora y da en particular esta caracterización, que se desprende inmediatamente de la definición adoptada anteriormente:
un número n que no es primo es de Carmichael si y solo si λ ( n ) divide n - 1 .En consecuencia :
Aprovechando estas propiedades, y de la expresión en este caso de λ ( n ) (ver apartado anterior), la caracterización de Carmichael se convierte en:
Teorema.— Un número natural n que no es primo es un número de Carmichael si y solo si es un producto de primos impares distintos, sea n = p 1 … p k , satisfaciendo p i - 1 divide n - 1 , para 1 ≤ yo ≤ k .
Este resultado, demostrado en el artículo de Carmichael, a veces se denomina teorema de Korselt (ver el artículo detallado Número de Carmichael ).