Dunque, per salvare la mia dimostrazione sulla proprietà moltiplicativa della funzione $ \varphi(\cdot) $ di Eulero, dimostrerò ora il lemma da me sfruttato senza usare la proprietà moltiplicativa della funzione $ \varphi(\cdot) $.
Problema Bonus: Senza usare la proprietà moltiplicativa della funzione $ \varphi(\cdot) $, dimostrare la seguente formula per il calcolo della funzione $ \varphi(\cdot) $ stessa:
Se $ \displaystyle{n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}} $ con $ \displaystyle{\forall p_i\in\mathfrak{P}} $, e con $ p_i \neq p_j $, per ogni $ i, j = 1, 2, \ldots, r $ tali che $ i \neq j $, e con $ \displaystyle{\forall\alpha_i\in\mathbb{N^{*}}} $, allora:
$ \displaystyle{\varphi(n)=n\prod_{i=1}^{r} \left(1-\frac{1}{p_i}\right)} $
Premesse:
1)Principio di inclusione-esclusione: siano $ \displaystyle{A_1, A_2,\dots ,A_n} $ insiemi finiti. Allora per avere la cardinalità dell'unione dobbiamo sommare le cardinalità degli insiemi, sottrarre le cardinalità di tutte le possibili intersezioni a 2 a 2, aggiungere le cardinalità di tutte le possibili intersezioni a 3 a 3, ecc....
2)Formula per lo sviluppo dei polinomi simmetrici: per arbitrari $ \displaystyle{x_1, x_2,\dots, x_n} $, abbiamo: $ \displaystyle{(t+x_1)(t+x_2)...(t+x_n)=t^{n}+c_1 t^{n-1}+\dots +c_{n-1}t+c_n} $ dove i coefficienti $ \displaystyle{c_1, c_2,\dots , c_n} $ sono chiamati funzioni simmetriche elementari delle $ x_i $; in particolare ogni $ c_k $ è la somma dei prodotti degli $ x_i $ presi $ k $ alla volta.
Dimostrazione:
Per il teorema fondamentale dell'aritmetica è possibile scrivere ogni numero intero $ n>1 $ come:
$ \displaystyle{n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}} $
con $ \displaystyle{\forall p_i\in\mathfrak{P}} $, e con $ p_i \neq p_j $, per ogni $ i, j = 1, 2, \ldots, r $ tali che $ i \neq j $, e con $ \displaystyle{\forall\alpha_i\in\mathbb{N^{*}}} $.
Calcoliamo $ \varphi(n) $:
$ \displaystyle{\varphi(n)=\#\{x|x\in\mathbb {N^{*}}\wedge x\leq n \wedge gcd(n,x)=1\} } $
ovvero:
$ \displaystyle{\varphi(n)=n-\#\{y|y\in\mathbb {N^{*}}\wedge y\leq n \wedge gcd(n,y)>1\} } $
Ci serve calcolare dunque la cardinalità dell'insieme $ \displaystyle{\{y|y\in\mathbb {N^{*}}\wedge y\leq n \wedge gcd(n,y)>1\} } $.
Definiamo ora gli insiemi $ A(i_j) $:
$ \displaystyle{A(i_1, i_2,\dots , i_r)=\{u|u\in\mathbb {N^{*}} \wedge u\leq n \wedge p_{i_1}, p_{i_2},\dots , p_{i_r}\mid u\} } $.
Abbiamo:
$ \displaystyle{\#\{y|y\in\mathbb {N^{*}}\wedge y\leq n \wedge gcd(n,y)>1\}=\#\bigcup_{i=1}^{r} A_i } $.
Per il principio di inclusione-esclusione (si veda la premessa):
$ \displaystyle{\#\bigcup_{i=1}^{r} A_i=\#A(1)+\#A(2)+\dots +\#A(r) } $$ \displaystyle{-[\#A(1,2)+\#A(1,3)+\dots+\#A(r-1,r)] } $$ \displaystyle{+\dots +[(-1)^{r}*\#A(1,2,\dots,r)] } $
Calcoliamo, dunque, le cardinalità dei singoli $ A_{i_j} $; si tratta di calcolare quante volte i prodotti dei fattori $ p_i $ presi $ 1,2,\dots ,r $ alla volta si trovano in $ n $; quindi:
$ \displaystyle{\#A(1)=\frac {p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}}{p_1} = p_1^{\alpha_1-1}p_2^{\alpha_2}\dots p_r^{\alpha_r} } $
$ \displaystyle{\#A(2)=p_1^{\alpha_1}p_2^{\alpha_2-1}\dots p_r^{\alpha_r} } $
$ \displaystyle{\#A(r)=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r-1} } $
$ \displaystyle{\#A(1,2)=\frac {p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}}{p_1p_2} = p_1^{\alpha_1-1}p_2^{\alpha_2-1}\dots p_r^{\alpha_r} } $
$ \displaystyle{\#A(1,3)=p_1^{\alpha_1-1}p_2^{\alpha_2}p_3^{\alpha_3-1}\dots p_r^{\alpha_r} } $
$ \displaystyle{\#A(r-1,r)=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_{r-1}^{\alpha_{r-1}-1}p_r^{\alpha_r-1} } $
$ \displaystyle{\#A(1,2,\dots ,r)=p_1^{\alpha_1-1}p_2^{\alpha_2-1}p_3^{\alpha_3-1}\dots p_r^{\alpha_r-1} } $
La cardinalità dell'insieme $ \displaystile{\#\{y|y\in\mathbb {N^{*}}\wedge y\leq n \wedge gcd(n,y)>1\} } $ quindi è:
$ \displaystyle{p_1^{\alpha_1-1}p_2^{\alpha_2}\dots p_r^{\alpha_r}+p_1^{\alpha_1}p_2^{\alpha_2-1}\dots p_r^{\alpha_r}+\dots +p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r-1} } $$ \displaystyle{-(p_1^{\alpha_1-1}p_2^{\alpha_2-1}\dots p_r^{\alpha_r}+p_1^{\alpha_1-1}p_2^{\alpha_2}p_3^{\alpha_3-1}\dots p_r^{\alpha_r} } $$ \displaystyle{+\dots+p_1^{\alpha_1}p_2^{\alpha_2}\dots p_{r-1}^{\alpha_{r-1}-1}p_r^{\alpha_r-1}) } $$ \displaystyle{+\dots+((-1)^{r}p_1^{\alpha_1-1}p_2^{\alpha_2-1}p_3^{\alpha_3-1}\dots p_r^{\alpha_r-1}) } $
Ricordando che $ \displaystyle{\varphi(n)=n- } $$ \displaystile{\#\{y|y\in\mathbb {N^{*}}\wedge y\leq n \wedge gcd(n,y)>1\} } $, allora:
$ \displaystyle{\varphi(n)=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}- } $$ \displaystyle{[p_1^{\alpha_1-1}p_2^{\alpha_2}\dots p_r^{\alpha_r}+p_1^{\alpha_1}p_2^{\alpha_2-1}\dots p_r^{\alpha_r}+\dots +p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r-1} } $$ \displaystyle{-(p_1^{\alpha_1-1}p_2^{\alpha_2-1}\dots p_r^{\alpha_r}+p_1^{\alpha_1-1}p_2^{\alpha_2}p_3^{\alpha_3-1}\dots p_r^{\alpha_r} } $$ \displaystyle{+\dots+p_1^{\alpha_1}p_2^{\alpha_2}\dots p_{r-1}^{\alpha_{r-1}-1}p_r^{\alpha_r-1}) } $$ \displaystyle{+\dots+((-1)^{r}p_1^{\alpha_1-1}p_2^{\alpha_2-1}p_3^{\alpha_3-1}\dots p_r^{\alpha_r-1})] } $
Osserviamo che possiamo mettere in evidenza $ p_1^{\alpha_1-1}p_2^{\alpha_2-1}\dots p_r^{\alpha_r-1} $, ottenendo:
$ \displaystyle{\varphi(n)=p_1^{\alpha_1-1}p_2^{\alpha_2-1}\dots p_r^{\alpha_r-1}\{p_1p_2\dots p_r - } $$ \displaystyle{[(p_2p_3\dots p_r+p_1p_3\dots p_r+\dots +p_1p_2\dots p_{r-1})-} $$ \displaystyle{(p_3p_4\dots p_r+p_2p_4\dots p_r+\dots + p_1p_2\dots p_{r-2})+\dots + (-1)^{r}]\} } $
Riscriviamo questa relazione come:
$ \displaystyle{\varphi(n)=p_1^{\alpha_1-1}p_2^{\alpha_2-1}\dots p_r^{\alpha_r-1}(c_r+c_{r-1}t+\dots +c_1 t^{r-1}+t^{r}) } $
dove $ t=-1 $ e i $ c_k $ sono le somme dei prodotti degli $ p_i $ presi k alla volta. Dunque, poiché questa rappresenta la forma dei polinomi simmetrici (si veda la premessa), possiamo scrivere:
$ \displaystyle{\varphi(n)=p_1^{\alpha_1-1}p_2^{\alpha_2-1}\dots p_r^{\alpha_r-1}(p_1-1)(p_2-1)\dots (p_r-1) } $
Applicando una nota proprietà:
$ \displaystyle{\varphi(n)=\frac {p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}}{p_1p_2\dots p_r} } $$ \displaystyle{(p_1-1)(p_2-1)\dots (p_r-1)= } $$ \displaystyle{{p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}\left(1-\frac {1}{p_1}\right)\left(1-\frac {1}{p_2}\right)\dots\left(1-\frac {1}{p_r}\right)= } $
$ \displaystyle{=n\prod_{i=1}^{r}\left(1-\frac {1}{p_i}\right) } $.
Così la tesi è finalmente (

) dimostrata.
Bye,
#Poliwhirl#