OliForum Matematico

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

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

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

Spider

si hai ragione infatti a quell'ora non li ho fatti i conti...
quando li faccio ti faccio sapere

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.

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

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

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

Spider

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?

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

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

Era un OT riferito a questo losco figuro quà
viewtopic.php?p=73126#73126

Beh, diciamo che all'inizio ero convinto il suo nick fosse enormis_costa.
Poi ci siamo incontrati e mi sono detto: "Mmm... forse no."

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