número de inteiros positivos menores ou iguais à e que são primos com .
Ou seja, é o número de elementos do conjunto
porque o único inteiro positivo menor que é o próprio e ainda se verifica . Agora, para qualquer , temos , de forma que, a princípio, .
é . 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 , desde que .
Se ou , o teorema é válido, pois
Sejam, então e . Vamos agora dispor todos os inteiros ,,..., em linhas e colunas, para daí tirar algumas conclusões.
Os inteiros da -ésima coluna serão primos com apenas se for primo com . De fato, pois, de modo inverso, divide , apenas se for múltiplo de .
Na primeira linha temos inteiros que são primos com . Assim, temos colunas onde todos os inteiros são primos com .
Suponhamos que a -ésima coluna seja uma destas colunas. Pelo lema , os restos das divisões dos inteiros desta coluna por são ,,...,. Logo, o número de inteiros da -ésima coluna que são primos com é .
Portando, em cada coluna ( em um total de ) de inteiros onde todos são primos com , vamos ter inteiros que são primos com .
Logo, o número de inteiros da matriz que são primos com e é . É claro que todo número que não tem fatores primos com e também não terão com o produto . Assim, também é a quantidade de inteiros positivos menores que e primos com . Conclusão: .
Exemplo. Calcular .
Primeiro passo. Fatorar , ou seja .
Segundo Passo. Calcular para cada potência da fatoração.
Terceiro Passo: Aplica-se a propriedade multiplicativa de .
Ou seja, existem inteiros positivos que são menores que e primos com .
Os inteiros da -ésima coluna serão primos com apenas se for primo com . De fato, pois, de modo inverso, divide , apenas se for múltiplo de .
Na primeira linha temos inteiros que são primos com . Assim, temos colunas onde todos os inteiros são primos com .
Suponhamos que a -ésima coluna seja uma destas colunas. Pelo lema , os restos das divisões dos inteiros desta coluna por são ,,...,. Logo, o número de inteiros da -ésima coluna que são primos com é .
Portando, em cada coluna ( em um total de ) de inteiros onde todos são primos com , vamos ter inteiros que são primos com .
Logo, o número de inteiros da matriz que são primos com e é . É claro que todo número que não tem fatores primos com e também não terão com o produto . Assim, também é a quantidade de inteiros positivos menores que e primos com . Conclusão: .
Corolário: Se os inteiros positivos ,,,..., são primos entre si, dois a dois, então
Demonstração. Esta generalização do teorema é uma propriedade comum à todas as funções aritméticas multiplicativas e foi demonstrada no post 011.
Já sabemos que se é primo, então . Dado , com , vamos demonstrar agora a fórmula para calcular .
Teorema .
Demonstração. Os inteiros menores que e que são primos com são, obviamente, aqueles números que não possuem o fator primo . Os que possuem são da forma , ,...,, onde
Logo, se indica a quantidade de inteiros menores que que não são primos com , então a quantidade de inteiros que são menores que e primos com são exatamente . Assim, .
Agora, com a propriedade multiplicativa da função de Euler em conexão com o teorema , estamos em condições de calcular para qualque inteiro positivo .
Exemplo. Calcular .
Primeiro passo. Fatorar , ou seja .
Segundo Passo. Calcular para cada potência da fatoração.
Terceiro Passo: Aplica-se a propriedade multiplicativa de .
Ou seja, existem inteiros positivos que são menores que e primos com .
Referência bibliográfica
Edgard de Alencar Filho, Editora Nobel, 1988
Gostará de ler também:
ola Aloisio,
ResponderExcluirVc conhece a soma de Paulo?
phi(n) = soma finita.
depois mando pra vc
Não conheço, caro Anônimo.
ResponderExcluirVc é o Paulo?
Se desejar, mande para o meu e-mail.
Abraços
Caro aloisio, me mande seu e-mail. Se preferir acesse youtube/phi de euler / ou a função de euler é uma soma finita.
Excluir