Mah è piuttoso semplice però è carino, non ho la certezza che se ne sia parlato, ma mi pare probabile: ho cercato un pò tra i vecchi post ma dopo un pò ci si stanca, a phi si aprono volumi interi di post!
Un'altra simpatica proprietà di phi
Un'altra simpatica proprietà di phi
Dimostrare che $ \sum{\phi(d)}=n $ dove $ d $ è variabile tra tutti i divisori di n, dove n è un naturale generico.
Mah è piuttoso semplice però è carino, non ho la certezza che se ne sia parlato, ma mi pare probabile: ho cercato un pò tra i vecchi post ma dopo un pò ci si stanca, a phi si aprono volumi interi di post!
Mah è piuttoso semplice però è carino, non ho la certezza che se ne sia parlato, ma mi pare probabile: ho cercato un pò tra i vecchi post ma dopo un pò ci si stanca, a phi si aprono volumi interi di post!
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Dopo il 49 primo spero di non sparare altre cavolate..
Sia $ \displaystyle \phi_n(X)=\prod_{\alpha^n=1, ord(\alpha)=n}{(X-\alpha)}, deg(\phi_n)=\varphi{(n)}, n \in \mathbb{N} $ l'n-esimo polinomio ciclotomico; comparando i gradi della nota identità $ X^n-1=\prod_{d|n}{\phi_d(X)} $ si ha la tesi.
Sia $ \displaystyle \phi_n(X)=\prod_{\alpha^n=1, ord(\alpha)=n}{(X-\alpha)}, deg(\phi_n)=\varphi{(n)}, n \in \mathbb{N} $ l'n-esimo polinomio ciclotomico; comparando i gradi della nota identità $ X^n-1=\prod_{d|n}{\phi_d(X)} $ si ha la tesi.
The only goal of science is the honor of the human spirit.
Provo a dare una soluzione elementare:
Sia $ \begin{math}D=\{d \in N t.c. d|n\}\end{math} $
1) se n è primo allora $ \begin{math}D=\{1,n\}\end{math} $ e la sommatoria $ \begin{math} \sum\phi(d)\end{math} $ è uguale a $ \begin{math}\phi(1)+\phi(n)=1+(n-1)=n\end{math} $
2) se n è potenza di un primo $ \begin{math}n=p^m\end{math} $ allora $ \begin{math}D=\{1,p,p^2,...,p^m\}\end{math} $ e la sommatoria $ \begin{math} \sum\phi(d)\end{math} $ è uguale a $ \begin{math}\phi(1)+\phi(p)+\phi(p^2)+...+\phi(p^m)\end{math} $ $ \begin{math} = 1+(p-1)+(p^2-p)+...+(p^m-p^{m-1})=n\end{math} $
3) se n è generico $ \begin{math}n=p_1^{m_1}p_2^{m_2}...p_t^{m_t}\end{math} $ allora $ \begin{math}D=\{p_1^{s_1}p_2^{s_2}...p_t^{s_t}\} \mbox{ al variare di } 0\leq s_i \leq m_i \end{math} $
Notiamo che per il passo 2 si ha $ \begin{math} n=M=\prod_{i=1}^t \sum_{j=0}^{m_i} \phi(p^j) \end{math} $
Ma si può dimostrare (con una semplice doppia inclusione) che $ \begin{math} M=\sum \prod_{i=1,0 \leq s_j \leq m_i}^{t}\phi(p_i^{s_j})\end{math} $ cioè la somma di tutte le possibili disposizioni di esponenti.
Infine, ricordando che $ \begin{math}\phi\end{math} $ è moltiplicativa per coprimi, M è uguale proprio a $ \begin{math} \sum\phi(d)\end{math} $ provando così la tesi.
P.S: scusate il casino con gli indici...
Sia $ \begin{math}D=\{d \in N t.c. d|n\}\end{math} $
1) se n è primo allora $ \begin{math}D=\{1,n\}\end{math} $ e la sommatoria $ \begin{math} \sum\phi(d)\end{math} $ è uguale a $ \begin{math}\phi(1)+\phi(n)=1+(n-1)=n\end{math} $
2) se n è potenza di un primo $ \begin{math}n=p^m\end{math} $ allora $ \begin{math}D=\{1,p,p^2,...,p^m\}\end{math} $ e la sommatoria $ \begin{math} \sum\phi(d)\end{math} $ è uguale a $ \begin{math}\phi(1)+\phi(p)+\phi(p^2)+...+\phi(p^m)\end{math} $ $ \begin{math} = 1+(p-1)+(p^2-p)+...+(p^m-p^{m-1})=n\end{math} $
3) se n è generico $ \begin{math}n=p_1^{m_1}p_2^{m_2}...p_t^{m_t}\end{math} $ allora $ \begin{math}D=\{p_1^{s_1}p_2^{s_2}...p_t^{s_t}\} \mbox{ al variare di } 0\leq s_i \leq m_i \end{math} $
Notiamo che per il passo 2 si ha $ \begin{math} n=M=\prod_{i=1}^t \sum_{j=0}^{m_i} \phi(p^j) \end{math} $
Ma si può dimostrare (con una semplice doppia inclusione) che $ \begin{math} M=\sum \prod_{i=1,0 \leq s_j \leq m_i}^{t}\phi(p_i^{s_j})\end{math} $ cioè la somma di tutte le possibili disposizioni di esponenti.
Infine, ricordando che $ \begin{math}\phi\end{math} $ è moltiplicativa per coprimi, M è uguale proprio a $ \begin{math} \sum\phi(d)\end{math} $ provando così la tesi.
P.S: scusate il casino con gli indici...
"Sono il sig.Wolf, risolvo problemi."
Dato un intero $ n $, consideriamo l'insieme delle frazioni del tipo $ \displaystyle \frac{k}{n} $, con $ k $ intero tale che $ 1\leq k\leq n $, e l'insieme delle frazioni nella forma $ \displaystyle \frac{a}{b} $ , con $ b $ divisore positivo di $ n $, $ a $ intero tale che $ 1\leq a\leq b $ e che $ \left(a,b\right)=1 $.
Il secondo insieme non contiene altri che le frazioni del primo insieme ridotte ai minimi termini, dunque i due insiemi coincidono.
Con la prima scrittura abbiamo in totale $ n $ frazioni; con la seconda abbiamo $ \phi(d) $frazioni per ogni $ d $ che divide $ n $.
Per quanto dimostrato sopra, i due insiemi sono uguali, dunque $ \sum{\phi(d)}=n $.
Il secondo insieme non contiene altri che le frazioni del primo insieme ridotte ai minimi termini, dunque i due insiemi coincidono.
Con la prima scrittura abbiamo in totale $ n $ frazioni; con la seconda abbiamo $ \phi(d) $frazioni per ogni $ d $ che divide $ n $.
Per quanto dimostrato sopra, i due insiemi sono uguali, dunque $ \sum{\phi(d)}=n $.
Purtroppo no...non ne ho fatte alternative, la mia era la stessa di alessio.
Comunque quella di nicelbole, come prova elementare dovrebbe essere la più sintetica e istruttiva.Poi bò non si può mai dire ciò con certezza fino a "prova contraria"
Comunque quella di nicelbole, come prova elementare dovrebbe essere la più sintetica e istruttiva.Poi bò non si può mai dire ciò con certezza fino a "prova contraria"
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"