Função totiente de Euler (função phi)

Função totiente de Euler (também conhecida como função phi)

O Euler continuou a investigar as propriedades dos numeros

especificamente a distribuição de números primos.

Uma função importante que ele definiu

é chamada função phi.

Mede a divisibilidade de um numero.

Dado um numero, 'n' por exemplo

o resultado é o numero de inteiros menores ou iguais a 'n'

que não partilham um factor comum com 'n'.

Por exemplo, se quisermos encontrar o phi de 8,

olhamos para todos os valores de 1 a 8,

depois contamos com quantos inteiros

o 8 não partilha um factor maior que 1.

Note que o 6 não é contado,

porque 6 e 8 partilham factor 2,

enquanto 1,3,5 e 7 são todos contados,

porque apenas partilham o factor 1.

Logo, phi(8) = 4.

O que é interessante é que

calcular a função Phi é complicado, excepto num caso.

Olhe para este gráfico.

Representa os valores de phi de inteiros de 1 a 1000.

Reparou em algum padrão?

A linha recta de pontos no topo

representa todos os números primos.

Já que os números primos não têm factores maiores que 1,

o phi de qualquer numero, 'p', é simplesmente p-1.

Para calcular o phi de 7 - um numero primo -

contamos todos os inteiros excepto 7 -

já que nenhum partilha um factor com 7.

Phi de 7 = 6.

Então se perguntar pelo phi de 21,377, um numero primo,

apenas teria de subtrair 1 para achar a solução -

21,376.

Phi de qualquer primo é fácil de computar.

Isto leva a um resultado interessante, baseado no facto

da função phi ser multiplicativa.

Ou seja, phi(A x B) = phi(A) x phi(B).

Se soubermos que o numero 'N',

é o resultado do produto de dois primos, 'P1' e 'P2',

então phi de N é o valor

da multiplicação do phi de cada primo, -

ou (P1 - 1) x (P2 - 1)