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)