pillole di teoria dei numeri

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

sia n un numero naturale, e siano d<sub>1</sub>, d<sub>2</sub>,..., d<sub>k</sub> i suoi divisori
<BR>dimostrare che
<BR>
<BR>- sum φ(d<sub>i</sub>)=n
<BR>
<BR>- σ(n)+φ(n)=n*d(n) se e solo se n è primo
<BR>
<BR>σ(n)=sum d<sub>i</sub> (somma dei divisori di n)
<BR>φ(n) è la solita phi di eulero
<BR>d(n)=|{d<sub>i</sub>)}| cioè il numero di divisori di n
<BR>
<BR>-----------
<BR>
<BR>riporto anche la disuguaglianza di lord, non si sa mai che a qualcuno venga un\'illuminazione
<BR>
<BR>x_i >= 1 per ogni i. Dimostrare che
<BR>sum(i=1...n) 1/(1+x_i) >= n/(1+GM(x_i)),
<BR>ove con GM(x_i) si intende la media geometrica degli n numeri x_1,...,x_n.
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: talpuz il 03-01-2004 14:12 ]
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
publiosulpicio
Messaggi: 774
Iscritto il: 01 gen 1970, 01:00

Messaggio da publiosulpicio »

Propongo un altro problema sulla phi:
<BR>calcolare sum[n=0.. +inf]: (phi(n)/2^n)
publiosulpicio
Messaggi: 774
Iscritto il: 01 gen 1970, 01:00

Messaggio da publiosulpicio »

Su, qualcuno risolva questi problemi interessanti!!
<BR>Per iniziare risolvo il primo, i|n indica i divide n e sum[i|]... indica la somma per i che divide n.
<BR>Mostro inizialmente che, p primo, si ha sum[i|p^k]: phi(i)= p^k per ogni k. E\' immediato mostrare che phi(p^k)=p^(k-1)(p-1), quindi si ha:
<BR>sum[i|p^k]: phi(i)= sum: phi(i)= 1+sum: (p^(k-1)(p-1))=1+(p-1)sum:-p^(k-1)=1+(p-1)(p^k-1)/(p-1)=p^k.
<BR>Ora è sufficiente mostrare che sum[i|(ab)]:-phi(i)=sum[i|a]:-phi(i)*sum[i|b]:-phi(i), con a e b primi fra loro, per avere la tesi. Consideriamo il membro di destra: sviluppando il prodotto si ottengono solo addendi che compaiano anche a sinistra, poiché phi(n)*phi(m)=phi(n*m) e a e b non hanno divisori comuni, quindi se v|a e t|b allora (vt)|(ab). Tuttavia anche tutti gli addendi del membro di sinistra compaiono anche a destra, poiché i divisori di un prodotto di fattori primi fra loro sono tutte le possibili coppie dei divisori dei due numeri (considerando anche 1 come divisore in modo da considerare anche i divisori di solo uno dei due, la stessa cosa anche a destra e poiché phi(1)=1 tutto va bene), sono esattamente gli stessi che si trovano dall\'altra parte, da cui segue la tesi.<BR><BR>[ Questo Messaggio è stato Modificato da: publiosulpicio il 03-01-2004 20:38 ]
oscar
Messaggi: 99
Iscritto il: 01 gen 1970, 01:00
Località: Ciriè Ciriè Eleyson

Messaggio da oscar »

cos\'é esattamente la phi di eulero?
<BR> scusate l\'ignoranza <IMG SRC="images/forum/icons/icon_cool.gif">
il vaut mieux une tête bien faite qu'une tête bien pleine --Michel Eyquem de Montaigne--
publiosulpicio
Messaggi: 774
Iscritto il: 01 gen 1970, 01:00

Messaggio da publiosulpicio »

phi(n) è la cardinalità dell\'insieme dei numeri minori di n e primi con n.
<BR>Se guardi tra gli appendici del giornalino ce n\'è uno che ne parla, da anche una formula per calcolarla e qualche piccolo teorema.
oscar
Messaggi: 99
Iscritto il: 01 gen 1970, 01:00
Località: Ciriè Ciriè Eleyson

Messaggio da oscar »

grazie, ora vado a darci un\'occhiata
il vaut mieux une tête bien faite qu'une tête bien pleine --Michel Eyquem de Montaigne--
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

dai ragazzi...
<BR>la parte sufficiente del secondo è veramente una buffonata...
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

...è <b><i>VERAMENTE</i></b> una buffonata
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
LB
Messaggi: 72
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da LB »

LEMMA 1: σ(p^e) + φ(p^e) <= p^e*d(p^e) con p primo e e >= 1, con uguaglianza se e solo se e = 1
<BR>Supponimao che n = p^e.
<BR>
<BR>Allora possimo riscrivere la tesi come
<BR>sum(0 <= j <= e) p^j + (p^e - p^(e - 1)) <= p^e * (e + 1)
<BR>
<BR>Se e = 1, vale l\'uguaglianza
<BR>
<BR>Altrimenti la tesi diventa
<BR>sum(0 <= j <= e - 2) p^j + p^e + p^(e - 1) + (p^e - p^(e - 1)) = p^e * (e + 1)
<BR>sum(0 <= j <= e - 2) p^j >= p^e * (e - 1)
<BR>sum(0 <= j < e - 1) p^e - p^j >= 0
<BR>
<BR>Ma vale sempre p^e > p^j, quindi se la sommatoria ha almeno un elemento, ossia se e - 1 > 0, ovvero e >= 2, vale la disuguglianza stretta.
<BR>
<BR>
<BR>LEMMA 2: Se σ(m) + φ(m) <= m*d(m), allora σ(m * p^e) + φ(m * p^e) < m * p^e * d(m * p^e) con p primo e e >= 1
<BR>Per il lemma 1, σ(p^e) + φ(p^e) <= p^e*d(p^e).
<BR>
<BR>Per la moltiplicativita\' di tutte le funzioni, σ(m * p^e) + φ(m * p^e) < m * p^e * d(m * p^e) e\' equivalente a
<BR>σ(m) * σ(p^e) + φ(m) * φ(p^e) < m*d(m) * p^e*d(p^e).
<BR>σ(m) * σ(p^e) + φ(m) * φ(p^e) < (σ(m) + φ(m)) * (σ(p^e) + φ(p^e)) <= m*d(m) * p^e*d(p^e)
<BR>0 < φ(m) * σ(p^e) + σ(m) * φ(p^e)
<BR>
<BR>Sapendo che φ(k) >= 1 per k >= 1 e σ(k) >= 1 per k >= 1, questo risulta vero.
<BR>
<BR>
<BR>SOLUZIONE:
<BR>Se n = 1, la tesi è falsa.
<BR>Se n contiene un primo, la tesi vale se e solo se n è primo per il lemma 1.
<BR>Se n contiene due primi, la tesi è falsa applicando il lemma 2 usando il lemma 1 come ipotesi.
<BR>Possiamo dimostrare per induzione per la tesi è falsa per due o più primi: la proposizione precedente stabilisce il caso base e il lemma 2 è il passo induttivo.
<BR>
<BR>Dunque la tesi è vera se e solo se n è primo.
<BR>
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

rincaro:
<BR>
<BR>φ(d)*φ(ab)=d*φ(a)*φ(b)
<BR>
<BR>con d=MCD(a,b)
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
LB
Messaggi: 72
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da LB »

Si noti che p, a, b, l, g hanno \"k\" come indice, sebbene esso sia stato omesso per migliorare la leggibilità.
<BR>
<BR>La tesi è equivalente a:
<BR>prod(k) φ(p^d)*φ(p^(a + b))/(p^d *φ(p^a)*φ(p^b)) = 1
<BR>
<BR>Sia l = min(a, b) e g = max(a, b); allora
<BR>
<BR>prod(k) φ(p^l)*φ(p^(l + g))/(p^l * φ(p^l)*φ(p^g)) = 1
<BR>
<BR>prod(k) φ(p^(l + g))/(p^l * φ(p^g)) = 1
<BR>
<BR>Se l = 0 e g = 0, il termine diventa
<BR>φ(1)/(1 * φ(1)) = 1
<BR>
<BR>Se l = 0 e g > 0, il termine diventa
<BR>φ(p^g)/(φ(p^g)) = 1
<BR>
<BR>Se l > 0 e g > 0, il termine diventa
<BR>φ(p^(l + g))/(p^l * φ(p^g)) =
<BR>= p^(l + g) (1 - 1/p)/(p^l * (p^g) (1 - 1/p)) = 1
<BR>
<BR>dunque il termine vale sempre 1 e quindi anche la produttoria vale 1.
<BR>
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

beh, che dire...
<BR>tanti complimenti!! <IMG SRC="images/forum/icons/icon_razz.gif"> <IMG SRC="images/forum/icons/icon_razz.gif">
<BR>se ne trovo altri li posto
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-01-03 14:33, publiosulpicio wrote:
<BR>Propongo un altro problema sulla phi:
<BR>calcolare sum[n=0.. +inf]: (phi(n)/2^n)
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>anzi, c\'è ancora questo in attesa di risposta
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-01-05 01:11, LB wrote:
<BR>
<BR>Per la moltiplicativita\' di tutte le funzioni
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>beh, visto che sinceramente questa non la sapevo
<BR>
<BR>----
<BR>
<BR>dimostrare che le funzioni σ(n) e d(n) sono moltiplicative
<BR>[se MCD(a,b)=1 ==> f(ab)=f(a)*f(b)]
<BR>
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

questo è un pò + difficile:
<BR>
<BR>d(n)=numero di divisori di n
<BR>d_i = divisore di n (i da 1 a d(n))
<BR>
<BR>sum (d(d_i))^3 = (sum d(d_i) )^2
<BR>
<BR> <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR>
<BR>
<BR>Spero di aver scritto bene<BR><BR>[ Questo Messaggio è stato Modificato da: Simo_the_wolf il 08-01-2004 22:10 ]
Bloccato