Função Φ

A função Φ de Euler, calcula quais os números que são primos em relação a um dado n. Por exemplo:

n = 4

os números menores iguais a 4  são {1,2,3,4} quais desses são primos em relação ao 4? apenas o 1 e 3.

A função Φ é expressa da seguinte maneira:

Φ( p^(a) ) =p^(a) – p^(a-1)

Confirmando o caso n = 4:

Φ(2²) = 2² – 2 = 2

A função Φ também é multiplicativa, então:

Se Φ(p^(a) ) = p^(a)[ 1 – 1/p^(a)]

Então para um dado número n, seja ele igual a n = p1^(a1) . p2^(a2) . …….pk^(ak), então Φ( n) será:

Φ(n) = Φ(p1^(a1)…..pk^(ak)) = p1^(a1)[ 1 – 1/p1]. p2^(a2)[1 – 1/p2] …………..pk^(ak)[1  – 1/pk]

organizando:

Φ(n) = p1^(a1)….pk^(ak)[1 – 1/p1]…..[1 – 1/pk]

Φ(n) = n[1 – (1/p1)][1 – (1/p2)]……[1 – (1/pk)]

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: