Função de Carmichael

Em Teoria de números, a função de Carmichael de um inteiro positivo n, denotada λ(n), define-se como o menor inteiro m que cumpre:

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

para cada número inteiro a coprimo com n.^[1] Em outras palavras, define o expoente do grupo multiplicativo de resíduos quadráticos de módulo n(${\displaystyle {Z}}$/n${\displaystyle {Z}}$)^×.^[2]

Os primeiros valores de λ(n) são 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 ((sequência A002322 na OEIS) ).

A função pode-se definir recursivamente como segue:

• Para um primo p e um inteiro positivo k tal que p ≥ 3 ou k ≤ 2:

:${\displaystyle \lambda (p^{k})=p^{k-1}(p-1).\,}$(Da mesma maneira que a função φ de Euler).

• Para p=2 e um expoente k ≥ 3,

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

• Para diferentes primos ${\displaystyle p_{1},p_{2},\ldots ,p_{t}}$ e inteiros 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}}))}$

onde mcm denota o mínimo comum múltiplo.

Em forma compactada, a função fica como:^[3]

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

Com a função de Carmichael, pode-se elaborar um teorema, similar ao teorema de Euler, este diz:

onde ${\displaystyle \lambda }$ é a função de Carmichael. Este pode se provar considerando qualquer raiz primitiva módulo n e o teorema chinês do resto.${\displaystyle }$

• Robert Daniel Carmichael
• Função totiente de Euler

Referências