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 \]
$\sum_{d\mid n}{\varphi(d)}=n$
$\sum_{d\mid n}{\varphi(d)}=n$
The only goal of science is the honor of the human spirit.
Re: $\sum_{d\mid n}{\varphi(d)}=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
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
"Bene, ora dobbiamo massimizzare [tex]\dfrac{x}{(x+100)^2}[/tex]: come possiamo farlo senza le derivate? Beh insomma, in zero fa zero... a $+\infty$ tende a zero... e il massimo? Potrebbe essere, che so, in $10^{24}$? Chiaramente no... E in $10^{-3}$? Nemmeno... Insomma, nella frazione c'è solo il numero $100$, quindi dove volete che sia il massimo se non in $x=100$..?" (da leggere con risatine perfide e irrisorie in corrispondenza dei puntini di sospensione)
Maledetti fisici! (cit.)
Maledetti fisici! (cit.)
Re: $\sum_{d\mid n}{\varphi(d)}=n$
Sì, giusta; qualche altra dimostrazione che non usi l'induzione?
The only goal of science is the honor of the human spirit.
Re: $\sum_{d\mid n}{\varphi(d)}=n$
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$ ?
$$\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$ ?
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: $\sum_{d\mid n}{\varphi(d)}=n$
C'è anche una soluzione "combinatorica"...
Testo nascosto:
Re: $\sum_{d\mid n}{\varphi(d)}=n$
Un suggerimento semplice: quanti sono i generatori di $C_d$?
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: $\sum_{d\mid n}{\varphi(d)}=n$
Scusa l'ignoranza: cos'è $C_d$? Su google esce solo "compact disk" xd
The only goal of science is the honor of the human spirit.
Re: $\sum_{d\mid n}{\varphi(d)}=n$
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.