OliForum Matematico

E' già apparso sul forum molto tempo fa, ma presenta ha piu' di una soluzione istruttiva, per cui..

Siano $a_1,a_2,\ldots,a_k$ tutti e i soli divisori positivi di $n \in \mathbb{N}_0$. Mostrare che
\[ \varphi(a_1)+\varphi(a_2)+\ldots+\varphi(a_k)=n \]

Si può dimostrare per induzione: la tesi è valida per ogni $n$ che può essere espresso come potenza di un numero primo; inoltre, se è valida per un certo $n$, allora lo è anche per $n \cdot q^k$, dove $q$ è un primo che non divide $n$

Innanzitutto ricordiamo che $\varphi(n)=n \cdot \prod\limits_{p \in \mathbb{P} \wedge p \mid n} \left(1-\dfrac{1}{p} \right)$ e che $\varphi(ab)=\varphi(a) \cdot \varphi(b)$ per ogni $a$ e $b$ primi fra loro, da cui segue:

1) se $n=p^k$ con $p$ primo e $k \in \mathbb{N}_0$, allora $\sum\limits_{d\mid n} \varphi(d)=\sum\limits_{i=0}^k \varphi(p^i)=1+\sum\limits_{i=1}^k (p^i-p^{i-1})=p^k=n$ (tutti gli altri termini si semplificano)

2) se $\sum\limits_{d\mid n}{\varphi(d)}=n$ allora per ogni $m=n \cdot q^k$, con $q \in \mathbb{P}| q\nmid n$ e $k \in \mathbb{N}_0$, si ha

$\sum\limits_{d\mid m}{\varphi(d)}=\sum\limits_{d\mid n} \left( \sum\limits_{i=0}^k \varphi(d \cdot q^i) \right)=\sum\limits_{d\mid n} \left( \varphi(d)\cdot \sum\limits_{i=0}^k \varphi(q^i) \right)=q^k \cdot \sum\limits_{d\mid n} \varphi(d)=n \cdot q^k=m$

Resta escluso solo il caso $n=1$ che però è banale

Sì, giusta; qualche altra dimostrazione che non usi l'induzione?

Una soluzione "prodotto di Eulero-like":
$$\displaystyle n=\\=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}=\\=\prod_{i=1}^k{\sum_{j=0}^{a_i}{\varphi(p_i^j)}}=\\=\sum_{d\mid n}{\varphi(d)}$$

Spieghiamo un po' i vari passaggi:
Il primo è la scomposizione in primi normale
Il secondo è scrivere cisascun $p_i^{a_i}$ come $\displaystyle\sum_{j=0}^{a_i}{\varphi(p_i^j)}=\varphi(1)+\varphi(p)+\varphi(p^2)+\dots+\varphi(p_i^{a_i})$, che viene facilmente da $\varphi(p^k)=p^k-p^{k-1}$
Il terzo è quello bello: in pratica si applica tante volte la proprietà distributiva e poi si sfrutta la moltiplicatività della $\varphi$ per ottenere ciascun divisore una ed una sola volta. Esempio senza phi: $(1+2+2^2)(1+3)(1+5)=(1+2+2^2)(1+3+5+3\cdot5)=1+3+5+3\cdot5+2+2\cdot3+2\cdot5+2\cdot3\cdot5+2^2+2^2\cdot3+2^2\cdot5+2^2\cdot3\cdot5$ è chiaro che sono tutti e soli i divisori di $2^2\cdot3\cdot5$ ?

C'è anche una soluzione "combinatorica"...

Un suggerimento semplice: quanti sono i generatori di $C_d$?

Scusa l'ignoranza: cos'è $C_d$? Su google esce solo "compact disk" xd

gruppo ciclico con $d$ elementi. è la stessa cosa di $\mathbb{Z}/d\mathbb{Z}$, solo che quest'ultimo ha anche una struttura moltiplicativa. approvo molto la distinzione (un po' bourbakista, se vuoi) tra i due concetti.