Italian TST 2005: problema n°3
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Italian TST 2005: problema n°3
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.
$ \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.
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.
-
- Messaggi: 77
- Iscritto il: 02 mag 2005, 12:26
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.
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.
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
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.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....
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.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
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.
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.
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
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) $
P.S.: il prodotto tra due funzioni sugli interi è definita così:
$ \displaystyle (f\star g)(n)=\sum_{d|n} f(d)g(\frac nd) $
Ultima modifica di Simo_the_wolf il 27 mag 2005, 22:41, modificato 1 volta in totale.
grazie, Marco, per l'arringa!
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ù...
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ù...