Somma funzione totiente di Eulero
Per \( n \in \mathbb{Z}_{\geq 1} \) abbiamo che
\[ \sum\limits_{d \mid n } \phi(d)=n \]
dove \( \phi \) è la funzione totiente di Eulero. Trova una dimostrazione usando argomentazioni di combinatoria di questa formula
Vi domando se vi sembra abbastanza combinatoria come dimostrazione
e se va bene.
Io ho pensato a questo definiamo \( \Phi_d := \{ \ell \in [d] : \operatorname{gcd}(\ell,d)=1 \} \) abbiamo \( \left| \Phi_d \right| = \phi(d) \) e quindi dimostrare che \[ \bigsqcup\limits_{d \mid n} \Phi_d \cdot \frac{n}{d}= [n] \]
Dove con \( [n] = \{1,\ldots,n\} \) e con la notazione \( \Phi_d \cdot \frac{n}{d} \) intendo moltiplicare ogni elemento di \(\Phi_d \) per \( \frac{n}{d} \)
Allora per fare questo notiamo che \( \forall k \in [n] \) abbiamo \( k=k \cdot \frac{n}{n} = \frac{\ell}{d} n \) dove la frazione \( \frac{\ell}{d} \) è ridotta ai minimi termini e quindi \( \operatorname{gcd}(\ell,d) =1 \) e pertanto abbiamo che \( \ell \in \Phi_d \). Inoltre \( d \) è un divisore di \( n \) e quindi per ogni elemento \( \ell \in \Phi_d \) con \( d \mid n \) abbiamo che \( \ell \frac{n}{d} = k \in [n] \). Pertanto abbiamo dimostrato che
\[ \bigcup\limits_{d \mid n} \Phi_d \cdot \frac{n}{d}= [n] \]
Ora dimostriamo che l'unione è disgiunta.
E quindi siano \( d \mid n \) e \( d' \mid n \) tale che \(\Phi_d \cdot \frac{n}{d} \cap \Phi_{d'} \cdot \frac{n}{d'} \neq \emptyset \), abbiamo che allora esiste \([n] \ni k= \frac{\ell}{d} n= \frac{\ell}{d'} n \), con \( \operatorname{gcd}(\ell,d)=1 =\operatorname{gcd}(\ell,d') \).
Pertanto \( \frac{\ell}{d} = \frac{\ell}{d'} \) e dunque risulta che \( d= d' \), pertanto l'unione è disgiunta.
\[ \bigsqcup\limits_{d \mid n} \Phi_d \cdot \frac{n}{d}= [n] \]
E dunque
\[ \sum\limits_{d \mid n} \left| \Phi_d \right| = n \]
Inoltre abbiamo che per definizione di \( \Phi_d \) risulta che \( \left| \Phi_d \right|= \phi(d) \) pertanto
\[ \sum\limits_{d \mid n} \phi(d) = n \]
\[ \sum\limits_{d \mid n } \phi(d)=n \]
dove \( \phi \) è la funzione totiente di Eulero. Trova una dimostrazione usando argomentazioni di combinatoria di questa formula
Vi domando se vi sembra abbastanza combinatoria come dimostrazione
e se va bene.Io ho pensato a questo definiamo \( \Phi_d := \{ \ell \in [d] : \operatorname{gcd}(\ell,d)=1 \} \) abbiamo \( \left| \Phi_d \right| = \phi(d) \) e quindi dimostrare che \[ \bigsqcup\limits_{d \mid n} \Phi_d \cdot \frac{n}{d}= [n] \]
Dove con \( [n] = \{1,\ldots,n\} \) e con la notazione \( \Phi_d \cdot \frac{n}{d} \) intendo moltiplicare ogni elemento di \(\Phi_d \) per \( \frac{n}{d} \)
Allora per fare questo notiamo che \( \forall k \in [n] \) abbiamo \( k=k \cdot \frac{n}{n} = \frac{\ell}{d} n \) dove la frazione \( \frac{\ell}{d} \) è ridotta ai minimi termini e quindi \( \operatorname{gcd}(\ell,d) =1 \) e pertanto abbiamo che \( \ell \in \Phi_d \). Inoltre \( d \) è un divisore di \( n \) e quindi per ogni elemento \( \ell \in \Phi_d \) con \( d \mid n \) abbiamo che \( \ell \frac{n}{d} = k \in [n] \). Pertanto abbiamo dimostrato che
\[ \bigcup\limits_{d \mid n} \Phi_d \cdot \frac{n}{d}= [n] \]
Ora dimostriamo che l'unione è disgiunta.
E quindi siano \( d \mid n \) e \( d' \mid n \) tale che \(\Phi_d \cdot \frac{n}{d} \cap \Phi_{d'} \cdot \frac{n}{d'} \neq \emptyset \), abbiamo che allora esiste \([n] \ni k= \frac{\ell}{d} n= \frac{\ell}{d'} n \), con \( \operatorname{gcd}(\ell,d)=1 =\operatorname{gcd}(\ell,d') \).
Pertanto \( \frac{\ell}{d} = \frac{\ell}{d'} \) e dunque risulta che \( d= d' \), pertanto l'unione è disgiunta.
\[ \bigsqcup\limits_{d \mid n} \Phi_d \cdot \frac{n}{d}= [n] \]
E dunque
\[ \sum\limits_{d \mid n} \left| \Phi_d \right| = n \]
Inoltre abbiamo che per definizione di \( \Phi_d \) risulta che \( \left| \Phi_d \right|= \phi(d) \) pertanto
\[ \sum\limits_{d \mid n} \phi(d) = n \]
Risposte
Scrivere le frazioni $1/n, 2/n,\ldots, n/n$. Ce ne sono $n$.
Ridurle ai minimi termini. I denominatori che appaiano
sono divisori $d$ di $n$. Per un denominatore $d$ dato,
i possibili numeratori sono interi fra $1$ e $d$
che sono coprimi a $d$. Ce ne sono $\phi(d)$.
Conclusione $\sum_{d|n}\phi(d) = n$.
Si veda: https://en.wikipedia.org/wiki/Euler%27s_totient_function
Ridurle ai minimi termini. I denominatori che appaiano
sono divisori $d$ di $n$. Per un denominatore $d$ dato,
i possibili numeratori sono interi fra $1$ e $d$
che sono coprimi a $d$. Ce ne sono $\phi(d)$.
Conclusione $\sum_{d|n}\phi(d) = n$.
Si veda: https://en.wikipedia.org/wiki/Euler%27s_totient_function
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo