TdN: sulle funzioni aritmetiche

[HiTLeuLeR]

Premesse: vien detta funzione aritmetica ogni generica applicazione $ f(\cdot): X_n \mapsto \mathbb{C} $, essendo $ X_n := \{k \in \mathbb{N}: k \geq n\} $, per ogni arbitrario $ n \in\mathbb{N} $. In Teoria dei Numeri, e soprattutto nella Teoria Analitica dei Numeri, le funzioni aritmetiche rivestono un ruolo di primaria importanza, come testimoniato ad esempio dai tanti mirabili risultati riguardanti l'indicatore di Eulero, il simbolo di Legendre o le funzioni dei divisori, giusto per citare alcuni esempi comuni alla massima parte dei problem solvers più "nutriti", o ancora la lambda maior di Von Mangoldt, le funzioni $ \theta(\cdot) $ e $ \psi(\cdot) $ di Chebyshev, la funzione $ \pi(\cdot) $ dei numeri primi o i caratteri di Dirichlet, andando già più sul tecnico. E a questo punto, dopo avervi suggestionati a dovere con tutti 'sti bei nomignoli altisonanti, direi ch'è il caso di procedere con le primissime presentazioni, siete d'accordo?!

L'indicatore di Eulero: è detta funzione dei totienti di Eulero, o anche indicatore di Eulero, la mappa $ \varphi(\cdot): \mathbb{N}_0 \mapsto \mathbb{C}: $ $ n \mapsto \#\{k\in\mathbb{N}_0: k \leq n\mbox{ }\wedge\mbox{ }\gcd(n,k) = 1\} $. Sic et simpliciter...

Le funzioni dei divisori: fissato $ t\in\mathbb{R} $, si assuma $ \displaystyle{\sigma_t(n) := \sum_{k \mid n} k^t} $, ove la sommatoria a secondo membro s'intende estesa a tutti e soli i divisori interi positivi di $ n $, per ogni $ n\in\mathbb{N}_0 $. Ebbene, $ \sigma_t(\cdot) $ vien detta la funzione dei divisori d'ordine $ t $.

La lambda maior di Von Mangoldt: per ogni $ n\in\mathbb{N}_0 $, si ponga $ \Lambda(n) := \log p $, s'esistono $ p\in\mathfrak{P} $ e $ k\in\mathbb{N}_0 $ t.c. $ n = p^k $; $ \Lambda(n) := 0 $, in ogni altro caso. La funzione risultante $ \Lambda(\cdot): \mathbb{N}_0 \mapsto \mathbb{C} $ è detta appunto la lambda maior di Von Mangoldt.

La funzione dei numeri primi: si definisce funzione dei numeri primi la mappa $ \pi(\cdot): \mathbb{N}_0 \mapsto \mathbb{C}: n \mapsto \#\{p\in\mathfrak{P}: p \leq n\} $.
A questa funzione, in particolare, si applica il cosiddetto teorema dei numeri primi, o di Hadamard-De La Vallée Poussin, secondo cui (qualcuno copra gli occhi ai pargoli innocenti!!!): $ \pi(n) \sim \dfrac{n}{\log n} $, per $ n\to +\infty $. Dio, quale meraviglia...

Ok, per il momento mi fermo qui, ché ho giusto da proporvi un simpatico problemi in cui sono coinvolte alcune delle funzioni appena introdotte. Se qualcuno vuole aggiungere qualcosa, beh... faccia pure! Mica son tipo che si offende, come tenta d'insinuare qualcuno...

[HiTLeuLeR]

E mo' andiamo avanti... Riprendendo le notazioni già utilizzate in seno al post precedente, diciamo che una certa funzione aritmetica $ f(\cdot): X_n\mapsto \mathbb{C} $ è moltiplicativa sse, per ogni $ x, y \in X_n $, con $ \gcd(x,y) = 1 $: $ f(xy) = f(x) f(y) $. Diciamo che $ f(\cdot) $ è poi totalmente moltiplicativa sse $ f(xy) = f(x) f(y) $, per ogni $ x, y\in X_n $. Ebbene, v'invito a dimostrare quanto segue:

Problema #1: l'indicatore di Eulero è una funzione moltiplicativa, ma non totalmente moltiplicativa.

Problema #2: per ogni $ t\in\mathbb{R} $, $ \sigma_t(\cdot) $ è una funzione moltiplicativa, ma non totalmente moltiplicativa.

Problema #3: la lambda maior di Von Mangoldt non è una funzione moltiplicativa.

Problema #4: la funzione identità $ u(\cdot): \mathbb{N}_0 \mapsto \mathbb{C}: n \mapsto n $ è totalmente moltiplicativa.

[Poliwhirl]

Vediamo un pò se riesco a combinare qualcosina :
Lemma:
Se $ \displaystyle{n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}} $ con $ \displaystyle{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)} $

Problema #1: l'indicatore di Eulero è una funzione moltiplicativa, ma non totalmente moltiplicativa.
Parte I: l'indicatore di Eulero è una funzione moltiplicativa

Prendiamo due numeri $ x,y $, con $ gcd(x,y)=1 $ e consideriamo le loro scomposizioni in fattori:
$ \displaystyle{x=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}} $
$ \displaystyle{y=q_1^{\beta_1}q_2^{\beta_2}\dots q_t^{\beta_t}} $
dove i $ p $ rappresentano numeri primi tutti distinti, ciascuno elevato ad una certa potenza, e allo stesso modo, dove le $ q $ rappresentano numeri primi tutti distinti, ciascuno elevato ad una certa potenza; inoltre, poiché $ gcd(x,y)=1 $, allora $ \forall p_i\neq\forall q_i $. Abbiamo per il lemma:
$ \displaystyle{\varphi(x)=x\prod_{i=1}^{r} \left(1-\frac{1}{p_i}\right)} $
$ \displaystyle{\varphi(y)=y\prod_{i=1}^{t}\left(1-\frac{1}{q_i}\right)} $
Dunque:
$ \displaystyle{\varphi(x)\varphi(y)=xy\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right)\prod_{i=1}^{t}\left(1-\frac{1}{q_i}\right)} $
Operiamo il prodotto di x e y:
$ \displaystyle{xy=(p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r})\dot(q_1^{\beta_1}q_2^{\beta_2}\dots q_t^{\beta_t})} $
Quindi per il lemma, abbiamo:
$ \displaystyle{\varphi(xy)=xy\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right)\prod_{i=1}^{t}\left(1-\frac{1}{q_i}\right)} $
Possiamo osservare dunque che $ \varphi(xy)=\varphi(x)\varphi(y) $ e dunque concludere che l'indicatore di Eulero è una funzione moltiplicativa.

Son le 2:30 di notte e sto crollando...posto domani la dimostrazione che la funzione non è completamente moltiplicativa...

Bye,
#Poliwhirl#

EDIT: corretto secondo i suggerimenti di HiTLeuLeR da me ritenuti opportuni....

[HiTLeuLeR]

Giusto un paio di doverose puntualizzazioni, Whirl... Sta' tranquillo, non ti bastonerò come fo' solitamente con Bollazzo!

Lemma:
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 $ \displaystyle{p_1\neq p_2\neq\dots\neq p_r} $, e con $ \displaystyle{\forall\alpha_i\in\mathbb{N}} $: $ \displaystyle{\varphi(n)=n\prod_{i=1}^{r} \left(1-\frac{1}{p_i}\right)} $

Le ineguaglianze non sono relazioni transitive! Pertanto, a voler esprimere il fatto che gli interi $ p_1, p_2, \ldots, p_r $ s'intendono a coppie distinti, quella scrittura che hai tu adottato (per quanto possa rendere il senso) è comunque sbagliata. Se può giovarti, al tuo posto ci avrei messo semmai che ha da essere $ p_i \neq p_j $, per ogni $ i, j = 1, 2, \ldots, r $ tali che $ i \neq j $.

Un'altra considerazione riguarda il fatto che, vista la tesi del lemma enunciato, l'esponente $ \alpha_i $ con cui $ p_i $ figura nella decomposizione in primi di $ n $, per ogni $ i = 1, 2, \ldots, r $, ha da essere un intero positivo, ché altrimenti $ p_i $ non interviene nella produttoria a secondo membro della relazione $ \displaystyle{\varphi(n)=n\prod_{i=1}^{r} \left(1-\frac{1}{p_i}\right)} $. Ne segue pertanto che la tesi del lemma anzidetto, così come formulata e tenuto conto delle correzioni che ti ho indicato, è valida solo per gli interi $ n > 1 $.

Anche l'uso del quantificatore universale (i.e., il "per ogni") lascia qua e là a desiderare: meglio spendere qualche parola in più e risultare "logorroici" (Boll... ) che tagliar corto ed essere sommari. Vabbe', ma forse mi sbaglio...

Infine una domanda: se usi quel lemma per provare la proprietà moltiplicativa della $ \varphi(\cdot) $ di Eulero, mi spieghi un po' in che modo per l'appunto dimostri il lemma?! Sai, la questione diventa un po' problematica...

[Boll]

Problema #4: la funzione identità $ u(\cdot): \mathbb{N}_0 \mapsto \mathbb{C}: n \mapsto n $ è totalmente moltiplicativa.

Uhm.... Ma è davvero la banalità che penso???? Devo aver misinterpretato

$ u(n)=n $, $ \forall n\in \mathbb{N}_0 $
$ u(mn)=mn=u(m)u(n) $ $ \forall m,n\in\mathbb{N}_0 $

[HiTLeuLeR]

Sì, Bollazzo, è esattamente la banalità che pensi!!! Ed è banale, perdonami, che tu l'abbia osservato...

[Boll]

$ \displaystyle n=\prod_{i=1}^{k}{p_i}^{e_i} $
$ \displaystyle{\phi(n)=n\prod_{i=1}^{k} \left(1-\frac{1}{p_i}\right)} $

Dimostrerò il Lemma di Poliwhirl per salvarlo dalle grinfie di HiTLeuLeR...:D

Step 1 La $ \phi(\cdot) $ è moltiplicativa, ma non strettamente.

Prendiamo una quaterna di interi positivi $ a,b,x,y $. Perchè $ a $ e $ b $ siano coprimi a $ xy $, $ a $ e $ b $ devono essere coprimi sia ad $ x $ che a $ y $. Ciò dimostra che la funzione è moltiplicativa. Per dimostrarne la non moltiplicatività stretta basta osservare che:
$ \phi(2)=|\{1\}|=1 $
$ \phi(6)=|\{1,5\}|=2 $
$ \phi(12)=|\{1,5,7,11\}|=4\neq 2 $

Step 2 Siano $ p\in \mathfrak{P},k\in \mathbb{N}_0 $, allora $ \phi(p^k)=p^k-p^{k-1} $
Il problema risulta essere di combinatoria elementare. Si prende il numero di tutti i numeri minori o uguali a $ p^k $, cioè a $ p^k $. Poichè gli unici numeri non coprimi a $ p^k $ sono i multipli di $ p $ essi vanno sottratti. Il loro numero sarà $ \displaystyle \frac{p^k}{p}=p^{k-1} $, da cui la tesi e, raccogliendo, potremo dire che $ \displaystyle \phi(p^k)=p^k\left(1-\frac{1}{p}\right) $

Sfruttando la moltiplicatività si dimostra quindi agilmente l'asserto di Poliwhirl.

[Poliwhirl]

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#

[Poliwhirl]

Lemma:
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)} $

Problema #1: l'indicatore di Eulero è una funzione moltiplicativa, ma non totalmente moltiplicativa.
Parte II: l'indicatore di Eulero non è una funzione totalmente moltiplicativa

Prendiamo due numeri $ x,y $, con $ gcd(x,y)>1 $ e consideriamo le loro scomposizioni in fattori:
$ \displaystyle{x=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}} $
$ \displaystyle{y=q_1^{\beta_1}q_2^{\beta_2}\dots q_t^{\beta_t}} $
dove i $ p $ rappresentano numeri primi tutti distinti, ciascuno elevato ad una certa potenza, e allo stesso modo, dove le $ q $ rappresentano numeri primi tutti distinti, ciascuno elevato ad una certa potenza; ma poiché $ gcd(x,y)>1 $, allora esiste un $ p_i $ uguale a un $ q_i $: supponiamo allora $ p_1=q_1 $. Per il lemma:
$ \displaystyle{\varphi(x)=x\prod_{i=1}^{r} \left(1-\frac{1}{p_i}\right)} $
$ \displaystyle{\varphi(y)=y\prod_{i=1}^{t}\left(1-\frac{1}{q_i}\right)} $
Dunque:
$ \displaystyle{\varphi(x)\varphi(y)=xy\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right)\prod_{i=1}^{t}\left(1-\frac{1}{q_i}\right)} $
Operiamo il prodotto di x e y:
$ \displaystyle{xy=(p_1^{\alpha_1+\beta_1}p_2^{\alpha_2}\dots p_r^{\alpha_r})\dot(q_2^{\beta_2}q_3^{\beta_3}\dots q_t^{\beta_t})} $
Quindi per il lemma, abbiamo:
$ \displaystyle \varphi(xy)=xy\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right)\prod_{i=2}^{t}\left(1-\frac{1}{q_i}\right) $
Quindi osserviamo che $ \displaystyle\varphi(x)\varphi(y) $ ha in più, rispetto a $ \displaystyle\varphi(xy) $, il fattore $ \displaystyle\left(1-\frac{1}{q_1}\right) $; tale fattore non influisce sulla produttoria se e solo se è uguale a $ 1 $:
$ \displaystyle\left(1-\frac{1}{q_1}\right)=1 $
da cui:
$ \displaystyle q_1=-1 $
che è impossibile giacché $ \displaystyle q_1\in\mathfrak{P} $; quindi $ \displaystyle\left(1-\frac{1}{q_1}\right) $ è sempre diverso da 1 e influisce sempre sulla produttoria. Possiamo concludere:
$ \displaystyle\varphi(xy)\neq\varphi(x)\varphi(y) $
e dunque l'indicatore di Eulero non è una funzione totalmente moltiplicativa c.v.d..

Bye,
#Poliwhirl#

EDIT: Corretto secondo i suggerimenti di HiTLeuLeR.

[Poliwhirl]

Proviamo con:
Problema #3: la lambda maior di Von Mangoldt non è una funzione moltiplicativa.

Siano dati due numeri $ \displaystyle x,y\in\mathbb{N^{*}} $ tali che $ gcd(x,y)=1 $ e tali che $ \displaystyle\Lambda(x)\neq 0 $ e $ \displaystyle\Lambda(y)\neq 0 $; allora per la definizione della funzione $ \displaystyle \Lambda(\cdot) $ di Von Mangoldt, abbiamo:
$ \displaystyle\Lambda(x)=\log p $, per tutti i $ \displaystyle p\in\mathfrak{P} $ tali che $ \displaystyle p^{k}=x $ per qualche $ \displaystyle k\in\mathbb{N^{*}} $.
$ \displaystyle\Lambda(y)=\log q $, per tutte le $ \displaystyle q\in\mathfrak{P} $ tali che $ \displaystyle q^{t}=y $ per qualche $ \displaystyle t\in\mathbb{N^{*}} $.
Poiché $ \displaystyle gcd(x,y)=1 $, sarà $ \displaystyle p\neq q $; dunque $ \displaystyle xy=p^{k}q^{t} $.
Sempre per la definizione della funzione $ \displaystyle \Lambda(\cdot) $ di Von Mangoldt, abbiamo:
$ \displaystyle\Lambda(xy)=\log a $ per tutti gli $ \displaystyle a\in\mathfrak{P} $ tali che $ \displaystyle a^{r}=xy $ per qualche $ \displaystyle r\in\mathbb{N^{*}} $.
Quindi sarebbe $ \displaystyle a^{r}=p^{k}q^{t} $ ma questa relazione è impossibile nel nostro caso, giacché $ \displaystyle k,t,r\in\mathbb{N^{*}} $ e $ \displaystyle p,q,a\in\mathfrak{P} $ (l'impossibilità della relazione deriva anche dal fatto che $ \displaystyle gcd(x,y)=1 $ e quindi $ \displaystyle p\neq q $); per definizione segue che $ \displaystyle \Lambda(xy)=0 $ giacché non esistono $ \displaystyle a\in\mathfrak{P} $ tali che $ \displaystyle a^{r}=p^{k}q^{t} $.
Ricordando ancora una volta che $ \displastyle p,q\in\mathfrak{P} $ e quindi sono diversi da $ \displaystyle 1 $, abbiamo:
$ \displaystyle\Lambda(x)\Lambda(y)=\log p \log q\neq 0 $.
Da qui possiamo concludere che:
$ \displaystyle\Lambda(xy)\neq\Lambda(x)\Lambda(y) $
e dunque la funzione lambda maior di Von Mangoldt non è moltiplicativa c.v.d..

Bye,
#Poliwhirl#

[HiTLeuLeR]

Per il teorema fondamentale dell'aritmetica è possibile scrivere ogni numero $ n $ 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^{*}}} $.

D'accordo, purché i numeri di cui si discute siano degli interi $ > 1 $... Leva via inoltre il primo di quei quantificatori universali, è del tutto fuori luogo!

$ \displaystyle{\#\{y|y\in\mathbb {N^{*}}\wedge y\leq n \wedge gcd(n,y)>1\}=\#\{A(1)\cup A(2)\cup\dots\cup A(r)\} } $.

Levaci quelle parentesi graffe: così com'è scritto, il secondo membro rappresenta la cardinalità non dell'unione degli insiemi $ A(1), A(2), \ldots, A(r) $, bensì dell'insieme il cui unico elemento è appunto $ A(1)\cup A(2)\cup\dots\cup A(r) $, e come tale è chiaramente pari ad 1.

Per il principio di inclusione-esclusione (si veda la premessa):
$ \displaystyle{\#\{A(1)\cup A(2)\cup\dots\cup A(r)\}= $ [...]

Stesso discorso fatto sopra... Il resto direi ch'è piuttosto meritevole, molto bravo!!!

P.S.: prendi la sana abitudine d'usare il comando "\gcd" quando ti serve scrivere in LaTeX del massimo comun divisore di due o più interi o di qualunque altra robaccia ti passi per le mani... Inoltre sta' pur certo che il mio intende essere un consiglio, di sicuro non un ordine...

[HiTLeuLeR]

Problema #1: l'indicatore di Eulero è una funzione moltiplicativa, ma non totalmente moltiplicativa.
Parte II: l'indicatore di Eulero non è una funzione totalmente moltiplicativa

Prendiamo due numeri $ x,y $, con $ gcd(x,y)>1 $ e consideriamo le loro scomposizioni in fattori: [...]
$ \displaystyle{x=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}} $
$ \displaystyle{y=q_1^{\beta_1}q_2^{\beta_2}\dots q_t^{\beta_t}} $
dove i $ p $ rappresentano numeri primi tutti distinti, ciascuno elevato ad una certa potenza, e allo stesso modo, dove le $ q $ rappresentano numeri primi tutti distinti, ciascuno elevato ad una certa potenza; [...]

I' ci avrei scritto esponente, piuttosto che potenza, ma vabbe'...

[...] ma poiché $ gcd(x,y)>1 $, allora esiste almeno un $ p_i $ uguale a un $ q_i $: supponiamo allora $ p_1=q_1 $. Per il lemma: [...]
$ \displaystyle \varphi(xy)=xy\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right)\prod_{i=2}^{t}\left(1-\frac{1}{q_i}\right) $

Siccome hai scelto di renderti la vita difficile, bada allora che la relazione qui sopra indicata vale se gli unici fattori comuni alle scomposizioni canoniche euclidee degli interi $ x $ ed $ y $, ambedue (per ipotesi) maggiori di 1, sono appunto $ p_1 $ e $ q_1 $. Diversamente potrebbero esserci problemi, non ti pare?! Sarai pertanto concorde con me sul fatto che quel tuo "almeno" costituisce - se non altro - una brutta stonatura...

[HiTLeuLeR]

Il tuo proof del fatto che la lambda maior di Von Mangoldt non è una funzione moltiplicativa è del tutto corretto, Poliwhirl. Soltanto accetta un suggerimento: quando ti serve provare che una proprietà non è valida in generale, puoi risparmiarti tanta fatica e limitarti ad esebire un esempio (costruito) ad hoc che ne dimostri l'inconsistenza. Questo discorso nulla vuol togliere ai tuoi sforzi, sia ben chiaro, assolutamente degni di lode! Semmai tenta d'essere un pudico consiglio per la tua carriera di problem solver, e non solo... Tutto qui!!!

[HiTLeuLeR]

Dimostrerò il Lemma di Poliwhirl per salvarlo dalle grinfie di HiTLeuLeR...:D

Step 1 La $ \phi(\cdot) $ è moltiplicativa, ma non strettamente.

Prendiamo una quaterna di interi positivi $ a,b,x,y $. Perchè $ a $ e $ b $ siano coprimi a $ xy $, $ a $ e $ b $ devono essere coprimi sia ad $ x $ che a $ y $. Ciò dimostra che la funzione è moltiplicativa.

Caspiterina, dici sul serio?! Uhmmm... Siccome sono un tantinello stupidino, non ti scoccia se ti chiedo maggiori dettagli in proposito e di mostrarmi come, da' tuoi argomenti, faccia magicamente seguito l'agognata uguaglianza $ \varphi(xy) = \varphi(x)\varphi(y) $, vero?!?

[Vasya]

Problema #2: per ogni $ t\in\mathbb{R} $, $ \sigma_t(\cdot) $ è una funzione moltiplicativa, ma non totalmente moltiplicativa.

OK. Non sembra troppo difficile, anche se la mia soluzione è tutt'altro che elegante.
Siano $ a_1,a_2, \dots , a_n $ i divisori di x e siano $ b_1,b_2, \dots ,b_m $ i divisori di y , con $ a_1,b_1=1 $ e $ a_n=x,b_m=y $ allora $ \displaystyle \sigma_t(x)=\sum_{k \mid x}k^t=(a_1^t+a_2^t+ \dots +a_n^t) $ e $ \displaystyle \sigma_t(y)=\sum_{k \mid y}k^t=(b_1^t+b_2^t+ \dots +b_m^t) $.
Visto che $ gcd(x,y)=1 $ (vale a dire che x ed y sono coprimi) tutti i divisori di xy sono della forma $ a_ib_j $ ($ 1 \le i \le n , 1 \le j \le m $ se proprio vogliamo essere formali), e viceversa ogni elemento del tipo $ a_ib_j $ è un divisore di xy .
Ora faccendo il seguente prodotto :$ (a_1^t+a_2^t+ \dots +a_n^t)(b_1^t+b_2^t+ \dots +b_m^t) $ otteniamo appunto la somma di tutti i possibili elementi del tipo $ a_ib_j $ (alla t ) che per definizione è proprio la funzione dei divisori di xy di ordine t.
Per far vedere che non è totalmente moltiplicativa basta esibire un controesempio:
$ \sigma_1(2) \sigma_1(4) = (1+2)(1+2+4) = 21 \neq 15 = (1+2+4+8) = \sigma_1(8) $.
Un paio di parole sul perché se due numeri non sono coprimi la funzione dei divisori non è moltiplicativa: se due numeri non sono coprimi allora hanno un divisore in comune diverso da 1, questo divisore appare una volta nella sommatoria che definisce la funzione per x e una volta nella sommatoria per y, quando poi viene fatto il prodotto delle sommatorie questo elemento viene contato due volte, il che fa eccedere il prodotto della funzione sigma rispetto alla funzione sigma del prodotto.