Proprietà della funzione di Eulero $n=sum_(d|n) varphi(d)$

[miles_davis]

dimostrare che

$n=sum_(d|n) varphi(d)$

mi dareste una mano? Grazie.

[Ravok]

Ciao,
l'idea per una dimostrazione è:
in un gruppo ciclico di ordine $n$, prendi un elemento di ordine $n$, e fai vedere per quanti $k$ si ha che il periodo di $a^k$ divide $n$.
Saluti

[Martino]

In effetti non è banale trovare una dimostrazione che non faccia uso della teoria dei gruppi

[miles_davis]

ce l'ho fatta... non avevo pensato a vedere $ZZ_n$ come gruppo additivo. Grazie.
P.S.: Avete visto l'altro messaggio, quello sui residui quadratici? Help me, please.

[Gabriel]

Se $f: \mathbb{N} \to \mathbb{C}$ è moltiplicativa e $g(n) = \sum_{d | n} f(d)$, per ogni $n \in \mathbb{N}$, allora $g$ è moltiplicativa. In tal senso, basta considerare che, comunque scelti $a, b \in \mathbb{N}$, per cui $\gcd(a,b) = 1$: $g(ab) = \sum_{h | a} \sum_{k | b} f(hk) = \sum_{h | a} \sum_{k | b} f(h) f(k) = g(a) g(b)$. Nel nostro caso, $f$ è la funzione di Eulero - infatti moltiplicativa. Di modo che, quando $n$ è un intero positivo e $\prod_{i = 1}^r p_i^{\alpha_i}$ è la sua fattorizzazione canonica in primi, vale $\sum_{d | n} \varphi(d) = \prod_{i=1}^r \sum_{k=0}^{\alpha_i} \varphi(p_i^k) = \prod_{i=1}^r p_i^{\alpha_i} = n$. []