io la butto la\'...

valentino · Messaggio da **valentino** » 01 gen 1970, 01:33

Sia n un naturale. Definiamo phi(n) come il numero di numeri compresi fra 1 ed n che sono primi con n.
 
 Per esempio, phi(10)=4, perchè 10 è primo con 1,3,7,9. Ancora, se p è primo phi(p)=p-1.
 
 Dimostrare che la somma su tutti i divisori d di n di phi(d) è uguale a n.
 Mi spiego meglio: prendo tutti i divisori di n, calcolo su di essi la phi, e sommo i risultati. Dimostrare che ottengo proprio n.

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

Dopo essermi sprofondato in un mare di sommatorie di produttorie ne sono riemerso con quella che reputo sia la soluzione.
 Sia dato un numero naturale n e sia p1^a1*p2^a2*...*pk^ak la sua scomposizione in fattori primi.
 
 Un noto teorema dice che allora phi(n) = p1^(a1-1)*(p1-1)*p2^(a2-1)*(p2-1)*...*pk^(ak-1)*(pk-1). (a)
 Per esempio phi(18)=3^(2-1)*(3-1)*2(1-1)*(2-1)=3^1*2*2^0*1=3*2=6.
 
 Dopo queste premesse, iniziamo con la dimostrazione. Il metodo è una simil-induzione.
 
 I) La tesi è vera per il numero 2. Infatti phi(2)=1.
 
 
 II) Supponiamo che la tesi sia vera per un dato n=p1^a1*p2^a2*...*pk^ak. Consideriamo ora un qualsiasi primo q che non compaia nella scomposizione di n (possiamo porre questa condizione senza perdere in generalità). Mostriamo che la tesi è valida anche per il numero n*q^r.
 A tale scopo supponiamo che D1,D2....,Dm siano tutti e soli i divisori di n. Allora phi(D1)+phi(D2)+...+phi(Dm)=n.
 
 I divisori di n*q^r sono dunque tutti e soli i numeri D1,D2....,Dm,...., D1q,D2q,...,Dmq,....., D1q^2,D2q^2,...,Dmq^2,....., D1q^r,D2q^r,...,Dmq^r.
 
 Allora dobbiamo dimostrare che
 SUM(i=1..m)[phi(Di)] + SUM(i=1..m)[phi(Diq)] + SUM(i=1..m)[phi(Diq^2)] + .... + SUM(i=1..m)[phi(Di^r)]
 è uguale a n*q^r.
 
 Notiamo che per la (a) phi(Diq^w)=q^(w-1)*(q-1)*phi(Di).
 
 Perciò la somma precedente è uguale a:
 
 n + (q-1)*SUM(i=1..m)[phi(Di)] + q*(q-1)*SUM(i=1..m)[phi(Di)] + .... + q^(r-1)*(q-1)*SUM(i=1..m)[phi(Di)]=
 = n + (q-1)n + nq(q-1) +...+n*q^(r-1)*(q-1) =
 = n[1+q-1+q(q-1)+q^(r-1)*(q-1)]=
 = n[q+q^2-q+...+q^r-q^(r-1)]=
 = nq^r, come si voleva dimostrare.
 
 NOTA: con SUM(i=1..m)[h] si intende la sommatoria di h per i che va da 1 a m, e dunque la somma 1+2+...+h
 
 [ This message was edited by: lordgauss on 2001-10-26 13:15 ]

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

Scusate, mi sono accorto ora che nella nota che doveva essere teoricamente chiarificatrice c\'è un bell\'errore: la somma è ovviamente 1+2+...+m[addsig]

Gauss · Messaggio da **Gauss** » 01 gen 1970, 01:33

A proposito di queste funzioni aritmetiche ci sono molti problemini interessante. Tipo, trovare il numero di coppie ordinate (x,y) che risolvono l\'equazione 1/x+1/y=1/n, per un dato n naturale.[addsig]

Gauss · Messaggio da **Gauss** » 01 gen 1970, 01:33

Ecco una dimostrazione molto elegante (sempre che sia corretta) che fa uso di un minimo di teoria dei gruppi, visto che mi sono messo or ora a studiarne un po\'.
 
 Consideriamo un gruppo ciclico G di ordine n (ordine di un gruppo= cardinalità, ordine o periodo di un elemento a [o(a)]= minimo numero k per il quale a^^k=1). I suoi sottogruppi saranno tutti quelli e solo quelli di ordine d (con d che divide n) generati da a^^(n/d). Noto che il numero di generatori di un gruppo di ordine d è dato da phi(d) la somma precedente si riduce al calcolo della somma del numero di generatori di ogni sottogruppo (anche G stesso) di G.
 Ogni elemento di G è generatore di uno ed uno solo sottogruppo di G [ x è generatore di un sottogruppo di ordine d se e solo se o(x)=d, e l\'ordine di ogni elemento di G è per l\'appunto =d dove d è il solito divisore di n e per quanto detto prima tutti i sottogruppi hanno ordine tra i divisori di n; l\'unicità è banale].
 Stabilita quindi questa bigezione tra gli elementi di G ed i generatori di ogni suo sottogruppo, questi saranno in egual numero e per quato specificato prima la somma richiesta vale n.
 
 SPECIFICHE: con a^^n non intendo una potenza moltiplicativa di a, ma la potenza di a rispetto all\'operazione di gruppo (per quanto riguarda N tale operazione sarebbe l\'addizione ed a^^n significherebbe n*a) [ Questo Messaggio è stato Modificato da: Gauss il 2002-03-03 12:12 ]