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:

${\displaystyle 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).

Definición

La función se puede definir recursivamente como sigue:

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

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

Para p=2 y un exponente k ≥ 3,

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

Para distintos primos ${\displaystyle p_{1},p_{2},\ldots ,p_{t}}$ y enteros positivos ${\displaystyle k_{1},k_{2},\ldots ,k_{t}}$:

${\displaystyle \lambda (p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{t}^{k_{t}})=\operatorname {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:

${\displaystyle \lambda (n)={\begin{cases}p^{k-1}(p-1)&{\text{si}}\ \ n=p^{k},\;{\text{con}}\;p\geq 3\;{\text{o}}\;k\leq 2\\2^{k-2}&{\text{si}}\ \ n=2^{k},\;{\text{con}}\;k\geq 3\\\operatorname {mcm} (\lambda (p_{1}^{k_{1}}),\lambda (p_{2}^{k_{2}}),\cdots ,\lambda (p_{t}^{k_{t}}))&{\text{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 ${\displaystyle \lambda }$ 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

• Aritmética modular
• Pequeño teorema de Fermat
• Teorema de Euler

Referencias

• Eric W. Weisstein. «Carmichael function.». Consultado el 30 de diciembre de 2008. 
• Eric W. Weisstein. «Carmichael's theorem.». Consultado el 30 de diciembre de 2008. 

• Datos: Q1043778
• Multimedia: Carmichael function / Q1043778