Función de Carmichael


Función de Carmichael

En Teoría de números, la función de Carmichael de un entero positivo n, denotada λ(n), se define como el menor entero m tal que cumple:

a^m \equiv 1 \pmod{n}

para cada número entero a coprimo con n. En otras palabras, define el exponente del grupo multiplicativo de residuos módulo n (Z/nZ)×.

Los primeros valores de λ(n) son 1, 1, 2, 2, 4, 2, 6, 2, 6, 4, 10, 2, 12, 6, 4, 4, 16, 6, 18, 4, 6, 10, 22, 2, 20, 12 (sucesión A002322 en OEIS).

Contenido

Definición

La función puede definirse recursivamente, como sigue:

Para un primo p y un entero positivo k tal que p ≥ 3 o k ≤ 2:

\lambda(p^k) = p^{k-1}(p-1).\, (De la misma manera que la función φ de Euler).

Para un entero k ≥ 3,

\lambda(2^k) = 2^{k-2}\, .

Para distintos primos p_1,p_2,\ldots,p_t y enteros positivos k_1,k_2,\ldots,k_t:

\lambda(p_1^{k_1} p_2^{k_2} \cdots p_t^{k_t}) = 
       \mathrm{mcm}( \lambda(p_1^{k_1}), \lambda(p_2^{k_2}), \cdots, \lambda(p_t^{k_t}) )

donde mcm denota el mínimo común múltiplo.

En forma compactada, la función queda como:

\lambda(n)=
\begin{cases}
p^{k-1}(p-1) & \mathrm{si} \ \  n=p^k, \; p \geq 3,\; k \leq 2\\
2^{k-2} & \mathrm{si} \ \  n=2^k, \; k \geq 3\\
\mathrm{mcm}( \lambda(p_1^{k_1}), \lambda(p_2^{k_2}), \cdots, \lambda(p_t^{k_t}) ) & \mathrm{si} \ \  n=\prod_{i=1}^t p_i^{k_i}

\end{cases}

Teorema de Carmichael

Con la función de Carmichael, se puede elaborar un teorema, similar al teorema de Euler, éste dice:

Si a es un número coprimo con n, entonces aλ(n) ≡ 1 (mod n)

donde λ es la función de Carmichael. Éste puede probarse considerando cualquier raíz primitiva módulo n y el teorema chino del resto.

Véase también

Referencias


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Función φ de Euler — Los primeros mil valores de . La función φ de Euler (también llamada función indicatriz de Euler) es una función importante en teoría de números. Si n es un número entero positivo, entonces φ(n) se define como el número de enteros positivos… …   Wikipedia Español

  • Teorema de Carmichael — Este artículo habla del teorema de Carmichael de los números de Fibonacci. También existe otro teorema de Carmichael aplicado a la definición recursiva de la función de Carmichael. El teorema de Carmichael, nombrado así en honor al matemático… …   Wikipedia Español

  • Robert Daniel Carmichael — Saltar a navegación, búsqueda Robert Daniel Carmichael (Goodwater, Alabama, 1 de marzo de 1879 1967) fue un matemático estadounidense. Doctorado en la Universidad de Princeton en 1911, se hizo conocido por sus trabajos con números primos. También …   Wikipedia Español

  • Pequeño teorema de Fermat — Saltar a navegación, búsqueda …   Wikipedia Español

  • RSA — En criptografía, RSA (Rivest, Shamir y Adleman) es un sistema criptográfico de clave pública desarrollado en 1977. Es el primer y más utilizado algoritmo de este tipo y es válido tanto para cifrar como para firmar digitalmente. La seguridad de… …   Wikipedia Español

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

  • Cancún — Saltar a navegación, búsqueda Cancún Escudo …   Wikipedia Español

  • Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número …   Wikipedia Español

  • Aritmética Modular Compleja — Saltar a navegación, búsqueda La ‘Aritmética Modular Compleja’ (hacia un nuevo test de primalidad) Contenido 1 La ‘Aritmética Modular Compleja’.La ‘semiarcotangente discreta’ 2 El Indicador imaginario de Euler´: IiE (M) …   Wikipedia Español

  • Colina (química) — El catión N,N,N trimetiletanolamonio, con un contraión indefinidio, X ). La colina es un nutriente esencial soluble en agua.[1] …   Wikipedia Español