Sommatoria e funzione phi di Eulero

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Spider
Messaggi: 147
Iscritto il: 01 gen 1970, 01:00
Località: San Cono (CT)
Contatta:

Sommatoria e funzione phi di Eulero

Messaggio da Spider »

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
Ultima modifica di Spider il 28 lug 2007, 01:09, modificato 1 volta in totale.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

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
Spider
Messaggi: 147
Iscritto il: 01 gen 1970, 01:00
Località: San Cono (CT)
Contatta:

Messaggio da Spider »

In realtà non ho capito che c'entra la somma dei divisori, ma, vista l'ora, è probabile che sia colpa mia... :wink:

Spider
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

si hai ragione infatti a quell'ora non li ho fatti i conti...
quando li faccio ti faccio sapere
Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 »

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à :P

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.
Spider
Messaggi: 147
Iscritto il: 01 gen 1970, 01:00
Località: San Cono (CT)
Contatta:

Messaggio da Spider »

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! :P

redipS
Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo »

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
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
Spider
Messaggi: 147
Iscritto il: 01 gen 1970, 01:00
Località: San Cono (CT)
Contatta:

Messaggio da Spider »

Anche questo è vero :lol:
In effetti avevo scritto anche perché speravo qualcuno trovasse una soluzione più semplice della mia 8)

Spider
Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 »

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?
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Spider
Messaggi: 147
Iscritto il: 01 gen 1970, 01:00
Località: San Cono (CT)
Contatta:

Messaggio da Spider »

enomis_costa88 ha scritto:..vero piccolo bambino sperduto che vagava per vaste aule di università, nostro leo
...eh??
cosa pensavi volesse dire il mio nick?
La maggior parte dei nick li accetto senza interrogarmi troppo sulla loro natura...

Spider
Sherlock
Messaggi: 601
Iscritto il: 24 nov 2006, 20:08
Località: Pisa & Barrafranca (Enna)

Messaggio da Sherlock »

enomis_costa88 ha scritto: Hum..ci sono persone che se ne sono accorte dopo anni e solo dopo che mi hanno conosciuto
Io scommetto che non ci sarei mai arrivato :? :? :?
Spider ha scritto:
enomis_costa88 ha scritto:..vero piccolo bambino sperduto che vagava per vaste aule di università, nostro leo
...eh??



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]
Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 »

Era un OT riferito a questo losco figuro quà :wink:
viewtopic.php?p=73126#73126
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Avatar utente
post233
Messaggi: 163
Iscritto il: 12 set 2005, 22:33
Località: Treviso

Messaggio da post233 »

Beh, diciamo che all'inizio ero convinto il suo nick fosse enormis_costa.
Poi ci siamo incontrati e mi sono detto: "Mmm... forse no."
Membro dell'EATO.
Membro della Lega Anti MM2.
Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 »

post233 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."
dicono che tu abbia inventato la formula
$ H_e\cdot N_p\rightarrow e $
dove $ ~H_e $è l'altezza di enomis e $ ~N_p $... be... indovinate :lol:
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
Rispondi