Woody ha scritto:Salve a tutti! Conoscete la dimostrazione del fatto che: $\sum_{d|n} \phi(d) = n \qquad\forall n\in NN\\{0}$ ?
Si, guarda che l'ho già dimostrato nel post di balckdie "Successioni di frazioni".
Comunque se vuoi che mi spieghi meglio, ecco fatto!
Come ben sappiamo per ogni numero primo $p$ si ha $phi(p^a)=p^a-p^a-1$, da cui segue che
$p^a=sum_(p|p^a) phi(p)$
infatti quest'ultima è una serie telescopica facilmente dove si annullano tutti i termini tranne $p^a$. Ora sappiamo che $phi$ è moltiplicativa cioè
$phi(ab)=phi(a)phi(b) forall gcd(a,b)=1$
quindi preso un $n$ in forma canonica $n=p_1^(a_1)p_2^(a_2)...p_u^(a_u)$ si ha
$n=prod_(k=1)^usum_(p|p_k^(a_k)) phi(p)=sum_(d|n)phi(d)$
Ciao!