课程目录
本页目录
上课用的是 potp(n),这里统一写成更常见的 vp(n),两者含义相同。
定义
给定素数 p,若 pm∥n,即 pm∣n 且 pm+1∤n,则记
vp(n)=m.
对有理数 a/b,定义
vp(ba)=vp(a)−vp(b).
基本性质
- vp(mn)=vp(m)+vp(n);
- vp(nk)=kvp(n)。
例子:
v3(54)=v3(33×2)=v3(33)+v3(2)=3v3(3)+0=3.
定理 1
设 p 是素数,pk⩽n<pk+1,则
vp(n!)=⌊pn⌋+⌊p2n⌋+⋯+⌊pkn⌋=i=1∑k⌊pin⌋.
证明
由 vp 的可加性,
vp(n!)=j=1∑nvp(j).
在 1∼n 中,只有 p 的倍数对和有贡献,这样的数共有 ⌊n/p⌋ 个。把每个 pj 写成 p⋅j,得
vp(n!)=j=1∑⌊n/p⌋vp(pj)=j=1∑⌊n/p⌋(vp(j)+1)=vp(⌊pn⌋!)+⌊pn⌋.
对 ⌊n/p⌋! 重复同样的操作。因为
⌊p⌊n/p⌋⌋=⌊p2n⌋,
所以
vp(n!)=⌊pn⌋+⌊p2n⌋+vp(⌊p2n⌋!).
继续下去,直到 pk⩽n<pk+1,此时 ⌊n/pk+1⌋=0,于是
vp(n!)=i=1∑k⌊pin⌋.□
推论:
n!=i=1∏spiai=i=1∏spi∑j⩾1⌊n/pij⌋.
定理 2
设 0<r<n,则
(rn)=r!(n−r)!n!
是整数。
证明
设
n!=i=1∏spiai,r!=i=1∏spibi,(n−r)!=i=1∏spici,
其中 ai,bi,ci⩾0。由定理 1,
ai=j⩾1∑⌊pijn⌋,bi=j⩾1∑⌊pijr⌋,ci=j⩾1∑⌊pijn−r⌋.
对每个 j,由 n=r+(n−r) 及 ⌊x+y⌋⩾⌊x⌋+⌊y⌋,有
⌊pijn⌋⩾⌊pijr⌋+⌊pijn−r⌋.
对 j 求和得 ai⩾bi+ci。因此分母的每个素因子幂次都不超过分子,故
(rn)=r!(n−r)!n!
是整数。□