Esercizzzietto 2

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Salvador
Messaggi: 42
Iscritto il: 09 apr 2017, 14:35

Esercizzzietto 2

Messaggio da Salvador »

Sia $n$ un intero positivo. Dimostrare che:
$$\displaystyle{\sum_{d | n}{\phi(d)} = n}$$
Avatar utente
Fenu
Messaggi: 77
Iscritto il: 10 set 2017, 16:34

Re: Esercizzzietto 2

Messaggio da Fenu »

$\phi(\frac{n}{k})$ conta (quasi) chiaramente tutti gli interi $m<=n$ tali che $(m,n)=k$.
Consideriamo ora l' insieme $S={1,2,3,...,n}$.
Contiamo la sua cardinalità in 2 modi.
Primo modo:
Tutti i numeri $k$ che hanno $(k, n)=1$.. Poi tutti quelli tali che $(k,n)=2$..fino ad arrivare a $(k,n)=n$..dato che scelto un $k$ è ovvio che esista un solo $h$ tale che $(k,n)=h$, sono sicuro di star contando tutti gli elementi dell' insieme una e una sola volta.
Questo equivale a $\sum_{d|n} \phi(\frac{n}{d})$. Dato che $d$ ed $\frac{n}{d}$ sono entrambi divisori di $n$, questa somma equivale a $\sum_{d|n} \phi(d)$.
Secondo modo:
A mano, lol.
Chiaramente i due modi coincidono, ed è immediato concludere che dal secono modo contiamo esattamente $|S|=n$. Per cui $\sum_{d|n} \phi(d)=n$.
Da qui si ricava molto velocemente anche un' altra identità:
$$\phi(n)=\sum_{d|n} \mu(d)\cdot\frac{n}{d}$$
Aspetto correzioni.
Salvador
Messaggi: 42
Iscritto il: 09 apr 2017, 14:35

Re: Esercizzzietto 2

Messaggio da Salvador »

Buona.
Volendo puoi fare anche per induzione
Rispondi