Função totiente de Euler

RKA4 - Euler continuou a investigar as propriedades dos números, especificamente a distribuição dos números primos. Uma função importante que ele definiu é chamada de "Função Phi". [Φ] Essa função mede a capacidade de quebra de um número. Assim, dado o número, por exemplo "N", ele mostra quantos números inteiros são menores do que, ou iguais a, N. Esses números inteiros não podem compartilhar qualquer fator comum com N. Por exemplo, se quisermos encontrar o Φ8, olharemos para todos os valores de 1 a 8. Então, contamos quantos inteiros não compartilham um fator maior do que 1 com o número 8. Note que 6 não é contado porque compartilha um fator de 2, enquanto 1, 3, 5 e 7 são todos contados porque apenas partilham um fator de 1. Portanto, Φ8 é igual a 4. O interessante é que o cálculo da função de Φ é difícil, exceto em um caso. Olha para esse gráfico. É um gráfico de valores de Φ sobre números inteiros de um a mil. Você nota qualquer padrão previsível? Essa reta de pontos que cruza o gráfico do eixo zero-zero até o eixo mil-mil, marcado em verde, representa todos os números primos. Já que números primos não tem nenhum valor maior que 1, o Φ de qualquer número primo "P" é simplesmente "P menos 1". Outro exemplo: para calcular o Φ7, um número primo, contamos todos os inteiros, exceto 7, uma vez que nenhum deles compartilha um fator com 7. O Φ7 é igual a 6. Então, se você está procurando encontrar Φ21.377, um número primo, você só precisa subtrair 1 para obter a solução 21.376. O Φ de qualquer número primo é fácil de calcular. Isso leva a um resultado interessante, baseado no fato que a função Φ também é multiplicativa, ou seja, Φ(A vezes B) é igual a ΦA vezes ΦB. Se sabemos que o número N é o produtos de dois números primos, P1 e P2, então ΦN é apenas o valor de Φ para cada número primo multiplicado um pelo outro, ou P1 menos 1 vezes P2 menos 1.