[N base] Divisori: conta e somma

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

Ciao. Un vecchio evergreen per i più giovani, con due formuline che ogni tanto servono...:
 
 Conoscendo la scomposizione in fattori primi di N, si dica
 i) quanti divisori ha N;
 ii) quanto vale la somma dei divisori di N.
 
 -------
 
 Se volete divertirvi, qual\'è il più piccolo N che ha 2004 divisori? La cui somma dei divisori è 2004? [confesso che non ho fatto i conti. Se con 2004 è troppo difficile, boh, fate con 12...]
 
 Ciao.
 
 M.[addsig]

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

Ma la domanda è di dimostrare le formule delle due funzioni o semplicemente di enunciarle??? (credo la 2, ma la domanda è malposta)

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

Mah, la parte interessante è dimostrarle, non certo enunciarle... cmq, fate vobis.
 
 La prossima volta che posto un pb. metterò la solita postilla: \"si tenga presente che non verranno accettate come corrette soluzioni in cui le affermazioni enunciate non vengano adeguatamente dimostrate\" <IMG SRC="images/forum/icons/icon_wink.gif">
 
 Ciao. M.

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

Bene, bene, come pensavo, allora ci provo...
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 Conoscendo la scomposizione in fattori primi di N, si dica
 i) quanti divisori ha N;
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 i) Definiamo funzione sigma0(n) la funzione che associa ad ogni numero naturale la cardinalità dell\'insieme D, dove D:={x€N/ x | n}, ovviamente è una funzione perchè per ogni numero naturale esiste uno e un solo numero di divisori.
 
 Step 1 Dimostriamo che se n=pk dove p è un primo naturale e k un intero positivo, allora sigma0(n)=k+1
 Dimostrazione: Tutti e soli i divisori di n saranno le potenze di p minori o uguali a k, poichè contiamo anche lo 0 avremo la tesi.
 
 Step 2 Dimostriamo che sigma0(-) è moltiplicativa.
 Dimostrazione: f(a)*f(b)=f(ab) MCD(a,b)=1.
 Per \"produrre\" tutti i divisori di dovremo moltiplicare tutti i divisori di a per tutti i divisori di b, poichè in tal modo otterremo tute le possibili permutazioni dei fattori primi di a,b, poichè, per ipotesi, non ne hanno di comuni.
 
 Conclusione:
 Quando n è un numero naturale della forma p1e1p2e2...pkekLa funzione sigma0(n)=prodi=1,k(ei+1)
 
 Ora facciamo il problemino con il 12<IMG SRC="images/forum/icons/icon_razz.gif"><IMG SRC="images/forum/icons/icon_razz.gif">:
 12=prodi=1,k(ei+1)
 quindi gli esponenti possono essere
 2,1,1
 3,2
 5,1
 11
 facendo i conti mettendo sempre il maggiore degli esopntenti con 2, il secondo con 3 ecc si ottiene che il più piccolo numero siffatto è 60 [ Questo Messaggio è stato Modificato da: Boll il 13-12-2004 15:49 ]

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

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-13 15:47, Boll wrote:
 Step 2 Dimostriamo che sigma0(-) è moltiplicativa.
 Dimostrazione: f(a)*f(b)=f(ab) MCD(a,b)=1.
 Per \"produrre\" tutti i divisori di dovremo moltiplicare tutti i divisori di a per tutti i divisori di b, poichè in tal modo otterremo tute le possibili permutazioni dei fattori primi di a,b, poichè, per ipotesi, non ne hanno di comuni.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Ok. Tutto giusto. Provo a ridire meglio il passo citato:
 
 Se a e b sono coprimi, i divisori di ab sono tutti e soli i numeri della forma xy, con x | a e y | b. Inoltre, se z | ab, gli x e y come sopra sono unici.
 
 [si può dimostrare considerando la scomposizione unica in f.primi, oppure con un simpatico lemmino: se u e v sono coprimi e u | vw , allora u | w].
 
 Ciao. M.
 [addsig]

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

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 Conoscendo la scomposizione in fattori primi di N, si dica
 ii) quanto vale la somma dei divisori di N.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Chiamiamo sigma(n) la funzione che associa ad ogni naturale la somma dei suoi divisori, è chiaramente una funzione perchè ogni numero ha un solo insieme di divisori e quindi una sola somma di essi. sigma(1)=1 per convenzione
 
 Step 1Osserviamo che se n è un numero della forma pk con p primo naturale e k intero positivo, allora sigma(n)=sumi=1,k(pi), poichè i soli divisori di n sono le potenze di p minori o uguali a n.
 
 Step 2 Dimostriamo che la funzione sigma(n) è moltiplicativa.
 Dimostrazione:f(ab)=f(a)f(b), MCD(a,b)=1
 sigma(a)=1+a+a1+...+ak
 sigma(b)=1+b+b1+...+bk
 dove ai è l\'i-esimo divisore di a e bi è l\'i-esimo divisore di b.
 Per ciò dimostrato da me nello Step 2 della precedente dimostrazione e riscritto \"umanamente\" da marco in seguito avremo che il prodotto di tali numeri è effettivamente la somma di tutti e soli i divisori primi di a e b, poichè è il prodotto di tutti i divisori di a per tutti i divisori di b.
 
 Conclusione
 Quando n è un numero naturale della forma p1e1p2e2...pkekLa funzione sigma(n)=prodi=1,k(suml=0,ei(pil))
 La formula si può ridurre ulteriormente utilizzando le progressioni geometriche, ma non saprei dire quanto convenga e scrivere un\'altra formula con queste tag mi pare improbo... spero si capisca almeno quella sopra...
 
 Quindi ora il problemino con il 12:
 11 non è somma di potenze perfette di primi, 1 nemmeno, allora non rimangono che 3 e 2, da cui si risale al numero 6. [ Questo Messaggio è stato Modificato da: Boll il 14-12-2004 06:55 ]

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

Ok. Sette punti per il Boll.