0:00:02.011,0:00:05.150
O Euler continuou a investigar as propriedades dos numeros

0:00:05.150,0:00:09.007
especificamente a distribuição de números primos.

0:00:09.007,0:00:10.919
Uma função importante que ele definiu

0:00:10.919,0:00:12.733
é chamada função phi.

0:00:12.733,0:00:15.885
Mede a divisibilidade de um numero.

0:00:15.885,0:00:17.879
Dado um numero, 'n' por exemplo

0:00:17.879,0:00:21.439
o resultado é o numero de inteiros menores ou iguais a 'n'

0:00:21.439,0:00:24.921
que não partilham um factor comum com 'n'.

0:00:24.921,0:00:28.375
Por exemplo, se quisermos encontrar o phi de 8,

0:00:28.375,0:00:30.868
olhamos para todos os valores de 1 a 8,

0:00:30.883,0:00:32.983
depois contamos com quantos inteiros

0:00:32.983,0:00:35.954
o 8 não partilha um factor maior que 1.

0:00:35.954,0:00:37.371
Note que o 6 não é contado,

0:00:37.371,0:00:39.302
porque 6 e 8 partilham factor 2,

0:00:39.302,0:00:42.002
enquanto 1,3,5 e 7 são todos contados,

0:00:42.002,0:00:44.528
porque apenas partilham o factor 1.

0:00:44.528,0:00:48.855
Logo, phi(8) = 4.

0:00:48.855,0:00:50.271
O que é interessante é que

0:00:50.271,0:00:54.523
calcular a função Phi é complicado, excepto num caso.

0:00:54.523,0:00:56.061
Olhe para este gráfico.

0:00:56.061,0:01:01.307
Representa os valores de phi de inteiros de 1 a 1000.

0:01:01.307,0:01:04.891
Reparou em algum padrão?

0:01:04.891,0:01:07.749
A linha recta de pontos no topo

0:01:07.749,0:01:11.016
representa todos os números primos.

0:01:11.016,0:01:14.463
Já que os números primos não têm factores maiores que 1,

0:01:14.463,0:01:19.991
o phi de qualquer numero, 'p', é simplesmente p-1.

0:01:19.991,0:01:22.616
Para calcular o phi de 7 - um numero primo -

0:01:22.616,0:01:24.984
contamos todos os inteiros excepto 7 -

0:01:24.984,0:01:27.575
já que nenhum partilha um factor com 7.

0:01:27.575,0:01:31.536
Phi de 7 = 6.

0:01:31.536,0:01:37.905
Então se perguntar pelo phi de 21,377, um numero primo,

0:01:37.905,0:01:41.356
apenas teria de subtrair 1 para achar a solução -

0:01:41.356,0:01:44.132
21,376.

0:01:44.132,0:01:48.090
Phi de qualquer primo é fácil de computar.

0:01:48.090,0:01:50.766
Isto leva a um resultado interessante, baseado no facto

0:01:50.766,0:01:53.875
da função phi ser multiplicativa.

0:01:53.875,0:02:00.899
Ou seja, phi(A x B) = phi(A) x phi(B).

0:02:00.899,0:02:02.792
Se soubermos que o numero 'N',

0:02:02.792,0:02:06.666
é o resultado do produto de dois primos, 'P1' e 'P2',

0:02:06.666,0:02:09.627
então phi de N é o valor

0:02:09.627,0:02:13.434
da multiplicação do phi de cada primo, -

0:02:13.434,0:02:17.057
ou (P1 - 1) x (P2 - 1)