Racismo

A Função de Euler
Seja . Chama-se função de Euler, indicador de ou totalizador de , a função assim definida:

número de inteiros positivos menores ou iguais à e que são primos com .

Ou seja, é o número de elementos do conjunto

Também representa-se esta função por . Eis seus primeiros valores:

porque o único inteiro positivo menor que é o próprio e ainda se verifica . Agora, para qualquer , temos , de forma que, a princípio, .

Exemplo. Calcular . Veja que o número de elementos do conjunto

é . Logo, .

Este processo de montar o conjunto para um certo e contar seu número de elementos é fácil apenas se este for relativamente pequeno. Esta tarefa torna-se complicada com, por exemplo .

Mas se for primo, simplesmente , tendo em vista que todos os inteiros positivos menores que primo são primos com o mesmo. Vejam na tabela que , , , e podem ter certeza que , etc.

Esta é a pergunta principal. Sendo um inteiro positivo qualquer, como calcular ? Podemos utilizar, então, a importante propriedade de que a função de Euler é uma função aritmética multiplicatica, ou seja, se e são inteiros positivos tais que , então

Este fato não é evidente e precisa ser demonstrado. Para isto, nos apoiaremos no seguinte teorema auxiliar.

Lema . Dados os inteiros positivos , e , com , então os restos das divisões dos inteiros

, , ,...,

por , são todos diferentes.

Demonstração. Seja a desigualdade . Suponhamos, por absurdo, que e deixem o mesmo resto na divisão por . Assim, e . Vejam, então, que divide o produto :

Mas por hipótese, , logo, divide , o que é impossível porque foi imposto que .

Concluimos, então, que os restos, conforme o lema , são todos diferentes.

Corolário. Como divide com resto exatamente uma quantidade de inteiros positivos, segue que estes restos dispostos em ordem são
,,,...,

Teorema . A função de Euler é uma função aritmética multiplicativa.

Demonstração. O que queremos provar é que ,