OliForum Matematico

Sia definita $ \forall n \in \mathbb{N} $ la seguente funzione:
$ \displaystyle \psi(n)=\sum_{k=1}^n (k,n) $
Dove $ (k,n) $ indixa il M.C.D. tra $ n $ e $ k $.
Dimostrare che:

(a) La funzione è moltiplicativa, cioè se $ (m,n)=1 $ allora $ \psi(mn)=\psi(m)\psi(n) $

(b) Per ogni intero $ a>0 $ l'equazione $ \psi(x)=ax $ ha almeno una soluzione.

Lemma #1: se $ m,n\in\mathbb{N}_0 $ e $ \gcd(m,n) = 1 $, la mappa $ \Phi(\cdot): \{0, 1, \ldots, m-1\} \mapsto \{0, 1, \ldots, m-1\}: j \mapsto (jn + k) \bmod m $ è iniettiva, e quindi biunivoca, per ogni $ k\in\mathbb{Z} $

Dim.: posto per comodità $ \Omega_m := \{0, 1, \ldots, m-1\} $, siano infatti $ j_1, j_2 \in\Omega_m $ tali che: $ \Phi(j_1) = \Phi(j_2) $. E allora, secondo costruzione: $ j_1n + k \equiv j_2 n + k \bmod m $, e quindi $ j_1n \equiv j_2 n \bmod m $. Del resto, per ipotesi: $ \gcd(m,n) = 1 $, sicché dalla precedente $ j_1 \equiv j_2 \bmod m $, e necessariamente $ j_1 = j_2 $, poiché $ 0 \leq |j_1 - j_2| < m $. Segue la tesi, q.e.d.

Parte a): siano $ m, n\in\mathbb{N}_0 $ primi fra loro. In tal caso: $ \displaystyle \psi(mn) := \sum_{k=1}^{mn} \gcd(mn,k) = \sum_{k=1}^{mn} \gcd(m,k)\cdot \gcd(n,k) = $ $ \displaystyle \sum_{j=0}^{m-1} \sum_{k=1}^{n} \gcd(m,jn+k)\cdot \gcd(n,jn+k) $. Di qui, sfruttando l'algoritmo di Euclide per il massimo comun divisore di due interi: $ \displaystyle\psi(mn) = \sum_{j=0}^{m-1} \sum_{k=1}^{n} \gcd(m,jn+k)\cdot \gcd(n,k) $ $ \displaystyle= \sum_{k=1}^{n} \left(\gcd(n,k)\cdot\sum_{j=0}^{m-1} \gcd(m,jn+k)\right) $. E d'altro canto, in base al lemma #1, qual che sia $ k = 1, 2, \ldots, n $, la mappa $ \Phi(\cdot): \{0, 1, \ldots, m-1\} \mapsto \{0, 1, \ldots, m-1\}: j \mapsto (jn + k) \bmod m $ è biettiva. Pertanto: $ \displaystyle\psi(mn) = \sum_{k=1}^{n} \left(\gcd(n,k)\cdot\sum_{j=0}^{m-1} \gcd(m,j)\right) = $ $ \displaystyle\left(\sum_{k=1}^{n} \gcd(n,k)\right)\left(\sum_{j=0}^{m-1} \gcd(m,j)\right) =: \psi(m) \cdot \psi(n) $, pur di considerare che $ \gcd(m,0) = \gcd(m,m) = m $. Ergo $ \psi(\cdot) $ è moltiplicativa, q.e.d.

chissà quante caterve di errori ci sono negli scritti di hitleuler e secondo me sul forum nessuno è in grado di leggere le sue scritture....

Caso b:

Dimostriamo innanzitutto che

$ \psi(p^k)=k*(p-1)*p^{k-1}+p^k $

dove p è un numero primo è k è un intero positivo.

Dobbiamo quindi 'contare' i vari gcd$ (p^k,i) $

Abbiamo un numero che apporta un gcd uguale a $ p^k $, cioè lo stesso $ p^k $

Abbiamo $ p-1 $ numeri che apportano un gcd uguale a $ p^{k-1} $, cioè i p multipli di $ p^{k-1} $ meno uno che abbiamo già contato.

Abbiamo $ p^2-p $ numeri che apportano un gcd uguale a $ p^{k-2} $, cioè i $ p^2 $ multipli di $ p^{k-2} $ meno p che abbiamo già
contato.

Più in generale abbiamo $ p^{k-t}-p^{k-t-1} $ numeri che apportano un gcd uguale a$ p^t $.

A questo punto dobbiamo aggiungere $ \varphi(p^k) = (p-1)(p^{k-1}) $ numeri che portano un gcd uguale a 1.

Dunque

$ \psi(p^k)=p^k+(p^{k-1})(p-1)+\ldots+p(p^{k-1}-p^{k-2})+\varphi(p^k) $
$ =k*p^k-(k-1)*p^{k-1}+(p-1)*p^{k-1}=k*(p-1)*p^{k-1}+p^k $

come volevamo dimostrare.

Ora, se poniamo p=2 e quindi $ x=2^k $ , l'equazione

$ \psi(x)=ax $ diventa

$ k*2^{k-1}+2^k=a*2^k $

da cui ricaviamo

$ k=2(a-1) $.

Quindi per ogni $ a > 0 $, $ x=2^{2(a-1)} $ è soluzione dell'equazione e questo conclude la dimostrazione.

Ora, per chi conosce un po' di teoria dei numeri + avanzata, ogni funzione moltiplicativa $ f(n) $ è tale che anche $ \displaystyle \sum_{d|n} f(d) $ è moltiplicativa. Ora, si riesce ad esprimere questa $ \psi(n) $ in forma di funzioni già conosciute?

carro bestiame ha scritto:chissà quante caterve di errori ci sono negli scritti di hitleuler e secondo me sul forum nessuno è in grado di leggere le sue scritture....

Non ti credere! Di solito ne fa molti meno del previsto, se non alcuno. Semmai, ha il vizio di esprimersi in maniera un po'... involuta.

La stessa medesima idea la puoi trovare nella dimostrazione che ho scritto io, solo che la forma è... come dire... un pelo più scorrevole.

-------------------

Siano m e n coprimi.

Fatto 1: Il Teorema Cinese del Resto permette di stabilire una corrispondenza biunivoca tra le coppie (i,j), con i e j interi, 1<=i<=m e 1<=j<=n e gli interi k 1<=k<=mn, in modo tale che k corrisponde a (i,j) sse

(**) $ i \equiv k \pod m; j \equiv k \pod n $.

Fatto 2: Per ogni k intero, (k,mn) = (k,m)(k,n). Questo si può dimostrare ad esempio considerando la fattorizzazione unica di k.

Fatto 3: se $ k \equiv k' \pmod m $, allora (k,m) = (k',m). Questo è una ben nota proprietà del MCD.

Allora

$ $ \psi(mn) = \sum_{k=1}^{mn} (k,mn) = $

per il F2

$ $ = \sum_{k=1}^{mn} (k,m)(k,n) = $

per il F1

$ $ = \sum_{k=1}^{mn} (i,m)(j,n), $

dove i e j sono come in (**).

Permutando gli addendi e sfruttando il F3, posso scrivere

$ $ = \sum_{i=1}^m \sum_{j=1}^n (i,m)(j,n),= \psi(m) \psi(n). $

Questo chiude la dimostrazione di (a). []

Ciao. M.

ok, a questo punto...
usiamo i cannoni: si può scrivere
$ \psi(n) = n\sum_{d|n} \frac{\varphi(d)}{d} $, e da questo la moltiplicatività segue in maniera relativamente facile...
per quanto riguarda quell'uguaglianza, basta osservare che ci sono $ \varphi(d) $ elementi che abbiano massimo comun divisore esattamente $ \frac{n}{d} $ con $ n $, et le jeux sont fait.

... e allora facciamoci del male fino in fondo osservando che MaGo ci ha appena detto che

$ \psi = \phi \star id $

Si ok, infatti era a questo che volevo arrivare... Come ha detto il buon marco (quello che ha preso la medaglia alle IMO, non l'altro...) La nostra $ \psi $ è il prodotto tra due funzioni moltiplicative e quindi è anch'essa una funzione moltiplicativa.

P.S.: il prodotto tra due funzioni sugli interi è definita così:
$ \displaystyle (f\star g)(n)=\sum_{d|n} f(d)g(\frac nd) $

Sia dunque laude a Dirichlet e alla sua convoluzione... Il punto è che quell'identità andrebbe un attimino dimostrata, no?!?

Ma qualche secondino più tardi...

Deh, ci ha già pensato il poliproteico ma_gò... Forse che si dovrebbero tributare lodi anche a costui, per questo? Uh, certi accostamenti mi paiono oltremodo azzardati, lasciam perdere, eeessù...