搜下勒让德定理的证明

勒让德定理
1) Vp(n!)=∑(k=0 to ∝)[n/p^k]
2) Vp(n!)=(n-Sp(n))/(p-1).
这两个都是(两个？各有好处)
2)的证明如下：
证法1：设n=nkp^k+n(k-1)p^(k-1)+n(k-2)p^(k-2)+…+n0，0≤ni<n
则n的p进制=(nkn(k-1)…a0)_p
Sp(n)=nk+n(k-1)+…+n0 (k,k-1,…,0都是下标)
因为Vp(n!)=[n/p]+[n/p^2]+…+[n/p^k]
[n/p]=nkp^(k-1)+n(k-1)p^(k-2)+…+n1
[n/p^2]=nkp^(k-2)+n(k-1)p^(k-3)+…+n2
…
[n/p^k]=nk
上面k个式子相加得
Vp(n!)=nk[(p^k-1)/(p-1)]+n(k-1)[(p^(k-1)-1)/(p-1)]+…+n2[(p^2-1)/(p-1)]+n1[(p-1)/(p-1)]
=(n-Sp(n))/(p-1)
证毕.
证法2:
设n=nkp^k+n(k-1)p^(k-1)+n(k-2)p^(k-2)+…+n0，0≤ni<n
易知ni=[n/p^i]-p[n/p^(i+1)] (代n入验证即可)
那么Sp(n)=n0+n1+…+nk
=∑(j=0 to k)[n/p^j]-p∑(j=1 to k+1)[n/p^j]
通过简单的化简得 (这里[n/p^(k+1)]=0)
=n+(1-p)∑(j=1 to k)[n/p^j]
所以(n-Sp(n))/(p-1)=∑(j=1 to k)[n/p^j]=Vp(n!)
证毕.
好了，我笔记来的..

n=nkp^k+…+n1p+n0
则n/p=nkp^(k-1)+…+n1+n0/p
n0/p是小数或者是0，所以取整的时候去掉n0/p.
同理(n1p+n0)/p^2也是小数或0.

这个是高中的数论吗