Italian TST 2005: problema n°3

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Simo_the_wolf
Moderatore
Messaggi: 1052
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Italian TST 2005: problema n°3

Messaggio da Simo_the_wolf » 22 mag 2005, 11:11

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.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 23 mag 2005, 19:25

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.

carro bestiame
Messaggi: 77
Iscritto il: 02 mag 2005, 12:26

Messaggio da carro bestiame » 23 mag 2005, 20:43

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

Igor
Messaggi: 108
Iscritto il: 01 gen 1970, 01:00

Messaggio da Igor » 23 mag 2005, 22:20

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.

Simo_the_wolf
Moderatore
Messaggi: 1052
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 23 mag 2005, 23:14

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?

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 24 mag 2005, 08:09

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.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 24 mag 2005, 08:45

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.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 24 mag 2005, 09:42

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

$ \psi = \phi \star id $

Simo_the_wolf
Moderatore
Messaggi: 1052
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 25 mag 2005, 14:19

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) $
Ultima modifica di Simo_the_wolf il 27 mag 2005, 22:41, modificato 1 volta in totale.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

grazie, Marco, per l'arringa!

Messaggio da HiTLeuLeR » 25 mag 2005, 22:49

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ù... :mrgreen:

Rispondi