io la butto la\'...

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
valentino
Messaggi: 13
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

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.
<BR>
<BR>Per esempio, phi(10)=4, perchè 10 è primo con 1,3,7,9. Ancora, se p è primo phi(p)=p-1.
<BR>
<BR>Dimostrare che la somma su tutti i divisori d di n di phi(d) è uguale a n.
<BR>Mi spiego meglio: prendo tutti i divisori di n, calcolo su di essi la phi, e sommo i risultati. Dimostrare che ottengo proprio n.
----------------
Valentino

lordgauss
Messaggi: 478
Iscritto il: 01 gen 1970, 01:00
Località: Brunswick

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.
<BR>Sia dato un numero naturale n e sia p1^a1*p2^a2*...*pk^ak la sua scomposizione in fattori primi.
<BR>
<BR>Un noto teorema dice che allora phi(n) = p1^(a1-1)*(p1-1)*p2^(a2-1)*(p2-1)*...*pk^(ak-1)*(pk-1). (a)
<BR>Per esempio phi(18)=3^(2-1)*(3-1)*2(1-1)*(2-1)=3^1*2*2^0*1=3*2=6.
<BR>
<BR>Dopo queste premesse, iniziamo con la dimostrazione. Il metodo è una simil-induzione.
<BR>
<BR>I) La tesi è vera per il numero 2. Infatti phi(2)=1.
<BR>
<BR>
<BR>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.
<BR>A tale scopo supponiamo che D1,D2....,Dm siano tutti e soli i divisori di n. Allora phi(D1)+phi(D2)+...+phi(Dm)=n.
<BR>
<BR>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.
<BR>
<BR>Allora dobbiamo dimostrare che
<BR>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)]
<BR>è uguale a n*q^r.
<BR>
<BR>Notiamo che per la (a) phi(Diq^w)=q^(w-1)*(q-1)*phi(Di).
<BR>
<BR>Perciò la somma precedente è uguale a:
<BR>
<BR>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)]=
<BR>= n + (q-1)n + nq(q-1) +...+n*q^(r-1)*(q-1) =
<BR>= n[1+q-1+q(q-1)+q^(r-1)*(q-1)]=
<BR>= n[q+q^2-q+...+q^r-q^(r-1)]=
<BR>= nq^r, come si voleva dimostrare.
<BR>
<BR>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
<BR>
<BR><BR><BR><font size=1>[ This message was edited by: lordgauss on 2001-10-26 13:15 ]</font>

lordgauss
Messaggi: 478
Iscritto il: 01 gen 1970, 01:00
Località: Brunswick

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
Messaggi: 233
Iscritto il: 01 gen 1970, 01:00
Località: Siena
Contatta:

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]
<html>
I can smile... and kill while i smile.
</html>

Gauss
Messaggi: 233
Iscritto il: 01 gen 1970, 01:00
Località: Siena
Contatta:

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\'.
<BR>
<BR>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.
<BR>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].
<BR>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.
<BR>
<BR>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) <BR><BR><font size=1>[ Questo Messaggio è stato Modificato da: Gauss il 2002-03-03 12:12 ]</font>
<html>
I can smile... and kill while i smile.
</html>

Bloccato