Função de Carmichael

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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:

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(/n)×.[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) ).

Definição[editar | editar código-fonte]

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:
 :(Da mesma maneira que a função φ de Euler).
  • Para p=2 e um expoente k ≥ 3,
  • Para diferentes primos e inteiros positivos :

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

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

Teorema de Carmichael[editar | editar código-fonte]

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 é a função de Carmichael. Este pode se provar considerando qualquer raiz primitiva módulo n e o teorema chinês do resto.

Ver também[editar | editar código-fonte]

Referências

  1. de Vries (2002). «The Carmichael function λ(n)» (em inglês). mat IT. Consultado em 1 de junho de 2018 
  2. Greg Martin (16 de maio de 2007). «Iterates of the Carmichael function» (pdf) (em inglês). Departamento de matemática da Universidade da Colúmbia Britânica. Consultado em 1 de junho de 2018 
  3. Richard Pinch (19 de dezembro de 2014). «Carmichael function» (em inglês). Encyclopedia of Mathematics. Consultado em 1 de junho de 2018