Sommatoria e funzione phi di Eulero
Sommatoria e funzione phi di Eulero
Dimostrare che, per ogni naturale $ n>1 $:
$ \sum a = \frac{1}{2}n\varphi(n) $
dove la somma si intende estesa a tutti gli interi $ a $ relativamente primi con $ n $ e minori di $ n $.
Mi scuso nel caso il problema sia già stato trattato su questo forum.
Saluti,
Spider
EDIT: errorino, grazie jordan
$ \sum a = \frac{1}{2}n\varphi(n) $
dove la somma si intende estesa a tutti gli interi $ a $ relativamente primi con $ n $ e minori di $ n $.
Mi scuso nel caso il problema sia già stato trattato su questo forum.
Saluti,
Spider
EDIT: errorino, grazie jordan
Ultima modifica di Spider il 28 lug 2007, 01:09, modificato 1 volta in totale.
guarda, è facile..
ti scrivi n (e non m!!!) come produttoria di p i alla alfa i (non so usare latex scusate). phi di n la sai trovare. e la somma dei divisori di n anche (cioe la produttoria di p alla (alfa+1) -1 tutto fratto produttoria di p-1). in questa somma è incluso anche 1 che quindi devi togliere. la somma che cerchi è quindi n-(somma divisori)+1. a questo punto devi solo sostituire, identità algebrica..
ciao ciao good night
ti scrivi n (e non m!!!) come produttoria di p i alla alfa i (non so usare latex scusate). phi di n la sai trovare. e la somma dei divisori di n anche (cioe la produttoria di p alla (alfa+1) -1 tutto fratto produttoria di p-1). in questa somma è incluso anche 1 che quindi devi togliere. la somma che cerchi è quindi n-(somma divisori)+1. a questo punto devi solo sostituire, identità algebrica..
ciao ciao good night
- enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Induzione sul numero di fattori primi.
Nel passo base si scrive la somma dei numeri fino a p^k si tolgono i multipli di p si butta dentro al testo e si ottiene un'identità
Sia $ f(n)=\frac{1}{2}n\varphi(n) $
voglio dimostrare che: $ f(n p^k)=f(n)(p^{2k}-p^{2k-1}) $
Lemmino: La somma dei numeri coprimi con n da 1 a $ p^kn $ è $ f(n)p^{2k} $
Considero ciascun intervallo (kn,(k+1)n] la somma dei numeri coprimi con n in esso sarà $ f(n)+\varphi(n)kn $
ovvero sarà uguale alla somma nel primo intervallo ma in cui ciascun numero coprimo con n è stato "alzato di kn".
Scrivendo la somma su tutti quegli intervallini ottengo quindi:
$ f(n)+\dots +(f(n)+\varphi(n)(p^k-1)n)= $$ n p^kf(n)+\frac{1}{2}n\varphi(n)p^k(p^k-1) $$ =f(n)p^{2k} $
Dove nell'ultima uguaglianza ho usato l'ipotesi induttiva.
Io voglio sapere quanto è la somma dei numeri coprimi con e minori di $ np^k $.
Questa somma sarà data dai numeri coprimi con n e minori di $ np^k $ a cui tolgo i numeri multipli di p coprimi con n (e minori di $ np^k $).
La somma dei multipli di p coprimi con n in quell'intervallo sarà la somma dei numeri coprimi con n più piccoli di $ np^{k-1} $ moltiplicata per p.
Infatti ho diviso per p ciascun numero e moltiplicato per p la somma.
Quindi per il lemmino ottengo:
$ f(np^k)=f(n)(p^{2k}-p^{2k-1}) $ da cui la tesi.
Nel passo base si scrive la somma dei numeri fino a p^k si tolgono i multipli di p si butta dentro al testo e si ottiene un'identità
Sia $ f(n)=\frac{1}{2}n\varphi(n) $
voglio dimostrare che: $ f(n p^k)=f(n)(p^{2k}-p^{2k-1}) $
Lemmino: La somma dei numeri coprimi con n da 1 a $ p^kn $ è $ f(n)p^{2k} $
Considero ciascun intervallo (kn,(k+1)n] la somma dei numeri coprimi con n in esso sarà $ f(n)+\varphi(n)kn $
ovvero sarà uguale alla somma nel primo intervallo ma in cui ciascun numero coprimo con n è stato "alzato di kn".
Scrivendo la somma su tutti quegli intervallini ottengo quindi:
$ f(n)+\dots +(f(n)+\varphi(n)(p^k-1)n)= $$ n p^kf(n)+\frac{1}{2}n\varphi(n)p^k(p^k-1) $$ =f(n)p^{2k} $
Dove nell'ultima uguaglianza ho usato l'ipotesi induttiva.
Io voglio sapere quanto è la somma dei numeri coprimi con e minori di $ np^k $.
Questa somma sarà data dai numeri coprimi con n e minori di $ np^k $ a cui tolgo i numeri multipli di p coprimi con n (e minori di $ np^k $).
La somma dei multipli di p coprimi con n in quell'intervallo sarà la somma dei numeri coprimi con n più piccoli di $ np^{k-1} $ moltiplicata per p.
Infatti ho diviso per p ciascun numero e moltiplicato per p la somma.
Quindi per il lemmino ottengo:
$ f(np^k)=f(n)(p^{2k}-p^{2k-1}) $ da cui la tesi.
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Ok, enomis, anche se hai dimenticato di scrivere che stai supponendo che $ p $ non divide $ n $ in tutto il testo. Io avevo impostato l'induzione in questo modo:
1) La tesi è vera per ogni primo
2) Se la tesi è vera per $ n $ e $ p $ è un primo, allora è vera per $ pn $
che forse viene un pelo più lungo perché nella seconda parte si deve distinguere se $ p | n $ o no.
PS: per la prima volta mi sono accorto che il tuo nick si può leggere al contrario!
redipS
1) La tesi è vera per ogni primo
2) Se la tesi è vera per $ n $ e $ p $ è un primo, allora è vera per $ pn $
che forse viene un pelo più lungo perché nella seconda parte si deve distinguere se $ p | n $ o no.
PS: per la prima volta mi sono accorto che il tuo nick si può leggere al contrario!
redipS
Beh mi pare ci sia una soluzione piu' semplice.. Se a e' primo con n allora lo e' anche n-a. Quindi possiamo "accopiare" i numeri primi con n per fare coppie che fanno somma n (non ne esistono di spaiati, perche', essendo n>2, palesemente n/2 non e' primo con n, se intero). Il numero di queste coppie e' ovviamente $ \frac{\phi (n)}{2} $, quindi la somma e' $ \frac{n \phi (n)}{2} $
NOTA: questo dimostra anche che $ \phi (n) $ e' pari per tutti gli n maggiori di due
NOTA: questo dimostra anche che $ \phi (n) $ e' pari per tutti gli n maggiori di due
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
- enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Davvero phiga la soluzione di denis!!!
Hum..ci sono persone che se ne sono accorte dopo anni e solo dopo che mi hanno conosciuto..vero piccolo bambino sperduto che vagava per vaste aule di università, nostro leo cosa pensavi volesse dire il mio nick?
Hum..ci sono persone che se ne sono accorte dopo anni e solo dopo che mi hanno conosciuto..vero piccolo bambino sperduto che vagava per vaste aule di università, nostro leo cosa pensavi volesse dire il mio nick?
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Io scommetto che non ci sarei mai arrivatoenomis_costa88 ha scritto: Hum..ci sono persone che se ne sono accorte dopo anni e solo dopo che mi hanno conosciuto
Spider ha scritto:...eh??enomis_costa88 ha scritto:..vero piccolo bambino sperduto che vagava per vaste aule di università, nostro leo
Quoto
[b]Membro Club Nostalgici[/b]
Catania 10/10/07
Io: Perché vuoi fare il matematico?
Lui: Se sei un dottore e qualcuno sta male ti svegliano la notte, se sei un ingegnere e crolla un ponte ti rompono ma se sei un matematico [b]CHI TI CERCA???[/b]
Catania 10/10/07
Io: Perché vuoi fare il matematico?
Lui: Se sei un dottore e qualcuno sta male ti svegliano la notte, se sei un ingegnere e crolla un ponte ti rompono ma se sei un matematico [b]CHI TI CERCA???[/b]
- enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Era un OT riferito a questo losco figuro quà
viewtopic.php?p=73126#73126
viewtopic.php?p=73126#73126
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
dicono che tu abbia inventato la formulapost233 ha scritto:Beh, diciamo che all'inizio ero convinto il suo nick fosse enormis_costa.
Poi ci siamo incontrati e mi sono detto: "Mmm... forse no."
dove $ ~H_e $è l'altezza di enomis e $ ~N_p $... be... indovinate$ H_e\cdot N_p\rightarrow e $
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]