Ou seja,
é
. 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:
.
![tp=p^{\alpha} [;tp=p^{\alpha};]](http://thewe.net/tex/tp=p%5E%7B%5Calpha%7D)
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.
![\varphi(2^3)=2^3-2^2=8-4=4 [;\varphi(2^3)=2^3-2^2=8-4=4;]](http://thewe.net/tex/%5Cvarphi%282%5E3%29=2%5E3-2%5E2=8-4=4)
![\varphi(3^2)=3^2-3^1=9-3=6 [;\varphi(3^2)=3^2-3^1=9-3=6;]](http://thewe.net/tex/%5Cvarphi%283%5E2%29=3%5E2-3%5E1=9-3=6)
![\varphi(5^7)=5^7-5^6=78125-15625=62500 [;\varphi(5^7)=5^7-5^6=78125-15625=62500;]](http://thewe.net/tex/%5Cvarphi%285%5E7%29=5%5E7-5%5E6=78125-15625=62500)
Terceiro Passo: Aplica-se a propriedade multiplicativa de
.
![\varphi(5625000)=\varphi(2^3.3^2.5^7)=\varphi(2^3).\varphi(3^2).\varphi(5^7)=4.6.62500=1500000 [;\varphi(5625000)=\varphi(2^3.3^2.5^7)=\varphi(2^3).\varphi(3^2).\varphi(5^7)=4.6.62500=1500000;]](http://thewe.net/tex/%5Cvarphi%285625000%29=%5Cvarphi%282%5E3.3%5E2.5%5E7%29=%5Cvarphi%282%5E3%29.%5Cvarphi%283%5E2%29.%5Cvarphi%285%5E7%29=4.6.62500=1500000)
Ou seja, existem
inteiros positivos que são menores que e primos com
.
Os inteiros da
Na primeira linha temos
Suponhamos que a
Portando, em cada coluna ( em um total de
Logo, o número de inteiros da matriz
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
.![\varphi(p^{\alpha})=p^{\alpha}-p^{\alpha-1} [;\varphi(p^{\alpha})=p^{\alpha}-p^{\alpha-1};]](http://thewe.net/tex/%5Cvarphi%28p%5E%7B%5Calpha%7D%29=p%5E%7B%5Calpha%7D-p%5E%7B%5Calpha-1%7D)
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,
.
Exemplo. Calcular
Primeiro passo. Fatorar
Segundo Passo. Calcular
Terceiro Passo: Aplica-se a propriedade multiplicativa de
Ou seja, existem
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