mcm e funzioni aritmetiche

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Igor
Messaggi: 108
Iscritto il: 01 gen 1970, 01:00

mcm e funzioni aritmetiche

Messaggio da Igor »

Ho postato questo problema prendendo spunto da un recente Topic di Simo the wolf...viva l'originalità :oops:

Sia definita la seguente funzione $ \forall n\in \mathbb{N}\displaystyle $,:

$ \displaystyle \tau(n)=\sum_{i=1}^{n}{mcm(n,i)} $
dove mcm(x,y) è il minimo comune multiplo tra x e y.

Dimostrare che, posto $ n=p^k $, con $ p $ primo e $ k $ intero positivo, allora:

$ \displaystyle \tau(n)=\frac{p^{3k+1}+p^{k+1}+2p^{k}}{2p+2}\displaystyle $
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Se $ k = 1 $, la tesi è banale, ché $ \displaystyle \tau(p) := \sum_{i=1}^p \mbox{mcm}(i,p) = \sum_{i=1}^{p-1} ip + p = $ $ \displaystyle\frac{p^2(p-1)}{2}+p=\left(\frac{p^{3k+1}+p^{k+1}+2p^k}{2(p+1)}\right)_{k=1} $. Assumendone quindi la consistenza per un generico $ k\in\mathbb{N}_0 $, osserviamo che: $ \displaystyle \tau(p^{k+1}) := \sum_{i=1}^{p^{k+1}} \mbox{mcm}(i,p^{k+1}) = $ $ \displaystyle\sum_{t=0}^{p^k-1} \sum_{i=1}^{p-1} \mbox{mcm}(pt + i,p^{k+1}) $ $ \displaystyle + \sum_{i=1}^{p^k} \mbox{mcm}(pi, p^{k+1}) = $ $ \displaystyle p^{k+1}\cdot \sum_{t=0}^{p^k-1} \sum_{i=1}^{p-1} (pt + i) + p \cdot \tau(p^k) $. Di qui, per l'ipotesi di induzione: $ \displaystyle \tau(p^{k+1}) = p^{k+1}\cdot p(p-1)\cdot \frac{(p^k-1)p^k}{2} + $ $ \displaystyle p^{2k+1}\cdot \frac{p(p-1)}{2} + p \cdot \frac{p^{3k+1} + p^{k+1} + 2p^k}{2(p+1)} = $ $ \displaystyle p^{3k+1}\cdot \frac{p(p-1)}{2} + \frac{p^{3k+2} + p^{k+2} + 2p^{k+1}}{2(p+1)} $ $ = \displaystyle\frac{p^{3(k+1) + 1} + p^{(k+1)+1} + 2p^{k+1}}{2(p+1)} $. Ne seguita l'asserto, q.e.d.
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Per inciso, si osservi che la tesi resta valida pure per $ k = 0 $.
Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info »

Scrivo anche la mia sol che non utilizza l'induzione... Ragiono su un generico p^k... osserviamo che (k,p^k) =k*p^k se p non divide k.... Quindi inizio con il sommare:

p^k * Si= p^2k(p^k+1)/2

Così però abbiamo aumentato l'mcm reale dei numeri che dividono p... Per eliminare quest'eccesso seguiamo questo algoritmo: contiamo i multipli di p e li dividiamo ognuno per p. Per ogni numero la differenza tra tra il numero orignario e quello dopo la divisione rappresenta un eccesso di p^k contati nella sommatoria iniziale (si provi con k=2 e p=3 e si capisce perchè funzia). Si esegue lo stesso per i multipli di p che si sono ottenuti (che prima della divisione erano multipli di p^2) e così via, fino a p^k. Matematicamente, togliamo:

(p-1)/2*p^k * p^(k-1)*(p^(k-1)+1)+
(p-1)/2*p^k * p^(k-2)*(p^(k-2)+1)+
...
(p-1)/2*p^k * p^(0)*(p^(0)+1)

esprimendo il tutto come sommatoria:

(p-1)/2*p^k *S[p^(i-1)*(p^(i-1)+1)]

che riconosciute le dovute serie geometriche

(p-1)/2*p^k*[(p^2k-1)/(p^2-1)+(p^k-1)/(p-1)]

questo è il fattore da togliere alla somma fatta inizialmente. Eseguendo la differenza sbuca fuori, dopo svariati errori di calcolo, proprio la formula di Igor... dato che ho saltato vari passaggi, se qualcosa non è chiaro, chiedete pure, eh!
Igor
Messaggi: 108
Iscritto il: 01 gen 1970, 01:00

Messaggio da Igor »

Molto buone entrambe le soluzioni.Io ho seguito un ragionamento simile a quello di
info, anche perchè, non conoscendo a priori la formula, non potevo dimostrarla per
induzione.
Rispondi