Dimostrazione di un teorema.
Salve,
sto cercando una dimostrazione COMPLETA del seguente teorema.
Indicando con Vp(n) la potenza alla quale un primo p divide n
il teorema è :
Vp(n!) = somma per k>= 1 del floor(n / p^k)
Qualcuno può indicarmi magari l'indirizzo di un paper....che contiene tale teorema.
sto cercando una dimostrazione COMPLETA del seguente teorema.
Indicando con Vp(n) la potenza alla quale un primo p divide n
il teorema è :
Vp(n!) = somma per k>= 1 del floor(n / p^k)
Qualcuno può indicarmi magari l'indirizzo di un paper....che contiene tale teorema.
Risposte
FINALMENTE MI SON CONVINTO.
Il problema è che ho sbagliato nel valutare la lunghezza (quella portante) della sommatoria infinita. Prima avevo dimostrato che quella sommatoria infinita in realtà può finire in Vp(n!) dando lo stesso risultato....ma adesso ho dimostrato ke quella sommatoria può finire anche dopo (sempre ottenendo lo stesso risultato), ovvero in ceiling(logaritmo in base p di n!).
A quel punto possiamo scrivere che :
per k > ceiling(logaritmo in base p di n!) si ha che:
p^k > p ^ ceiling(logaritmo in base p di n!)>=n! > n
Per questo il teorema funziona.
Il problema è che ho sbagliato nel valutare la lunghezza (quella portante) della sommatoria infinita. Prima avevo dimostrato che quella sommatoria infinita in realtà può finire in Vp(n!) dando lo stesso risultato....ma adesso ho dimostrato ke quella sommatoria può finire anche dopo (sempre ottenendo lo stesso risultato), ovvero in ceiling(logaritmo in base p di n!).
A quel punto possiamo scrivere che :
per k > ceiling(logaritmo in base p di n!) si ha che:
p^k > p ^ ceiling(logaritmo in base p di n!)>=n! > n
Per questo il teorema funziona.
Fatto sta che ancora non riesco a convincermi che se i > Vp(n!) allora p ^ i > n. 
O meglio....intuitivamente lo immagino....in quanto p ^ Vp(n!) sarà molto più grande di n....ma non è quantizzato in maniera rigorosa.
O meglio....intuitivamente lo immagino....in quanto p ^ Vp(n!) sarà molto più grande di n....ma non è quantizzato in maniera rigorosa.
"nochipfritz":
scusa la mia ignoranza...
Non scusarti di nulla, son io che ci ho messo un fattoriale di troppo!
faccio 1 esempio :
V2(5!) = 3 perchè 5! = 120 = (2^3) * 3 * 5
ora 2 ^ (V2(5!) + 1) = 2 ^ 4 = 16 < 120 = 5!
V2(5!) = 3 perchè 5! = 120 = (2^3) * 3 * 5
ora 2 ^ (V2(5!) + 1) = 2 ^ 4 = 16 < 120 = 5!
scusa la mia ignoranza....
se i > Vp(n!) siamo entrambi convinti che p^ i > p ^ Vp(n!)
ma p ^ Vp(n!) non è n! (ciò lo sarebbe se Vp fosse la funzione logaritmo in base p) . Ma poichè qui stiamo lavorando su interi p ^ i è minore o uguale a n!
se i > Vp(n!) siamo entrambi convinti che p^ i > p ^ Vp(n!)
ma p ^ Vp(n!) non è n! (ciò lo sarebbe se Vp fosse la funzione logaritmo in base p) . Ma poichè qui stiamo lavorando su interi p ^ i è minore o uguale a n!
"nochipfritz":
Soprattutto non capisco perchè per ogni i>Vp(n!) si ha esattamente che floor(n / (p ^ i)) = 0.
Se $i > v_p(n!)$, allora $p^i > n$, per la definizione stessa di $v_p(n!)$, e perciò $0 \le \frac{n}{p^i} < 1$. Dunque viene da sé che floor$(n/p^i) = 0$.
EDIT: ci stava un fattoriale di troppo!
Noi informatici usiamo floor e ceiling per denotare rispettivamente le approssimazioni per difetto e per eccesso
Grazie Hilbert. La tua dimostrazione è pressochè simile a quello che leggo in un testo :
This follows immediately from the observation that the numbers
1, 2, . . . , n include exactly floor(n/p) multiplies of p, floor(n/(p^2)) multiplies of p^2,
and so on.
Ma non riesco a convincermi di questo fatto!
Soprattutto non capisco perchè per ogni i>Vp(n!) si ha esattamente che floor(n / (p ^ i)) = 0.
Grazie Hilbert. La tua dimostrazione è pressochè simile a quello che leggo in un testo :
This follows immediately from the observation that the numbers
1, 2, . . . , n include exactly floor(n/p) multiplies of p, floor(n/(p^2)) multiplies of p^2,
and so on.
Ma non riesco a convincermi di questo fatto!
Soprattutto non capisco perchè per ogni i>Vp(n!) si ha esattamente che floor(n / (p ^ i)) = 0.
"eafkuor":
Ti giuro che non lo sapevo, il mio libro di testo usa quel simbolo per indicare la parte intera di x
Ti credo. Brucia il tuo libro.
Ti giuro che non lo sapevo, il mio libro di testo usa quel simbolo per indicare la parte intera di x
"eafkuor":
ah, allora è meglio indicarla con $[x]$
...veramente $[x]$, nella notazione standard, denota l'intero più vicino ad $x$ (click)
ah, allora è meglio indicarla con $[x]$
"nochipfritz":
Salve,
sto cercando una dimostrazione COMPLETA del seguente teorema.
Indicando con Vp(n) la potenza alla quale un primo p divide n
il teorema è :
Vp(n!) = somma per k>= 1 del floor(n / p^k)
Qualcuno può indicarmi magari l'indirizzo di un paper....che contiene tale teorema.
Sia $\alpha_k$ il quoziente della divisione intera di $n$ per $p^k$, qualunque sia $k \in \mathbb{N}$. Questo significa che, per ogni $k = 1, 2, ...$, esistono esattamente $\alpha_k$ interi positivi $\le n$ tali che $p^k$ | $n!$. E allora $v_p(n!) = \sum_{k=1}^\infty \alpha_k$, dove soltanto finiti termini della serie a secondo membro sono ovviamente $\ne 0$. Senonché $\alpha_k = $floor$(n/p^k)$, per ogni $k \in \mathbb{N}$. Ne segue la tesi, q.e.d.
il floor è l'approssimazione per difetto.
per esempio:
floor(3) = 3
floor(3,2)=3
floor(3,8)=3
per esempio:
floor(3) = 3
floor(3,2)=3
floor(3,8)=3
Cosa è il floor?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo