Função de Euler

por **Crist** » Seg Dez 02, 2013 09:06

Encontre o menor inteiro positivo n para o qual (phi) = 21.

fiz assim,

$\phi\left(n \right)=\phi\left({p}^{k} \right)={p}^{k}-{p}^{k-1}$

temos que para qualquer numero primo p,

$\phi\left(p \right)=p-1$ , temos

$\phi\left(n \right)=\phi\left({p}^{k} \right)$ e

$\phi\left(n \right)= 21$

21= p-1
p = 22

mas esse resultado nao deve estar correto, alguém me ajuda?

por **Bravim** » Seg Dez 02, 2013 10:20

A função de Euler verifica os coprimos menores que o número dado então deveria ser igual 12:
{1,2,4,5,8,10,11,13,16,17,19,20} são coprimos de 21.
Pelo que vi na fórmula aqui http://en.wikipedia.org/wiki/Euler%27s_totient_function
$\varphi(21)=21(1-\frac{1}{3})(1-\frac{1}{7})=21*\frac{2}{3}*\frac{6}{7}=12$
Os coprimos de 22 são:{1,3,5,7,9,11,13,15,17,19,21}, são 11
Os coprimos de 23 são:{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22}(visto que 23 é primo), mas aqui eu tenho 22
Os coprimos de 25 são:{1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24}, mas aqui eu tenho 20
Imagem