初等数论题目证明n个连续整数乘积一定被n!整除

Question

初等数论题目
证明n个连续整数乘积一定被n!整除

Answer 1

比如说m>n,要证明,m!/(n!(m-n)!)是整数,
也就是,对于任何一个质数p,p在m!中的重数
（就是出现的次数,比如说p^r整除a,但是p^(r+1)不整除a,那么p在a中出现的重数就是r,记作p(a),也就是p(a)=r）
比p在n!(m-n)!中出现的重数大,或者相等.
即要证明p(m!)>=p(n!(m-n)!)=p(n!)+p((m-n)!).
现在不难证明（请自己证明）p(n!)=[n/p]+[n/(p^2)]+[n/(p^3)]+…,其中[x]表示不超过x的最大整数.这个式子的右边,对于固定的n和p来讲,是有限项的和：当p^r>n的时候,[n/(p^r)]=0；所以这个式子中只有有限项是正的,其余都是0.
那么
p(m!)-p(n!)-p((m-n)!)
=[m/p] + [m/(p^2)] + [m/(p^3)]+…
-([n/p] + [n/(p^2)] + [n/(p^3)]+…)
-([(m-n)/p] + [(m-n)/(p^2)] + [(m-n)/(p^3)] + …)
=([m/p]-[n/p]-[(m-n)/p]) + ([m/(p^r)]-[n/(p^2)]-[(m-n)/(p^2)]) + …,
而[m/(p^r)]-[n/(p^r)]-[(m-n)/(p^r)]总是不小于0的（容易证明,如果a和b都不小于0,那么[a+b]-[a]-[b]>=0）,所以
p(m!)-p(n!)-p((m-n)!)>=0,
那么任何一个质数p在m!中出现的重数多不少于在n!(m-n)!中出现的重数.所以m!/(n!(m-n)!)是整数,也就是说连续n个自然数的乘积m!/(m-n)!可以被n!整除.