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:

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

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

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

Definição

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:

:$\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,

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

• Para diferentes primos $p_{1},p_{2},\ldots ,p_{t}$ e inteiros positivos $k_{1},k_{2},\ldots ,k_{t}$:

$\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:

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

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

Teorema — Se a é um número coprimo com n, então a^λ(n) ≡ 1 (mod n)

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

Ver também

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