组合数(数论)

下面给出了关于组合数素因子幂次的基本性质：

1. \(v_p(n!)=\sum\limits_{i=1}^\infty[\frac n{p^i}]\)

\(v_p(C_n^m)=\sum\limits_{i=1}^\infty ([\frac n{p^i}]-[\frac m{p^i}]-[\frac{n-m}{p^i}])\)

2. \(v_p(n!)=\frac{n-S_p(n)}{p-1}\)

其中 \(S_p(n)\) 表示 \(p\) 进制下 \(n\) 的数码和

\(v_p(C_n^m)=\frac{S_p(n-m)+S_p(m)-S_p(n)}{p-1}\)

直接推出 \(Kummer\) 定理： \(v_p(C_n^m)\) 恰好是 \(p\) 进制下 \(m+(n-m)\) 的进位数，或 \(n-m\) 的借位数

证明：设 \(n=(a_ka_{k-1}...a_0)_p\) ，则 \([\frac n{p^i}]=a_kp^{k-i}+a_{k-1}p^{k-i-1}+...+a_{i}\) ，则

\( \begin{aligned} \sum\limits_{i=1}^k[\frac n{p^i}] &=\sum\limits_{i=1}^k(a_kp^{k-i}+...+a_i)\\ &=\sum\limits_{j=1}^k a_j(p^{j-1}+p^{j-2}+...+1)\\ &=\sum\limits_{j=1}^k a_j\frac{p^j-1}{p-1}\\ &=\frac{n-S_p(n)}{p-1} \end{aligned} \)

3. (Lucas定理) 记 \(n=(a_ka_{k-1}...a_0)_p,m=(b_kb_{k-1}...b_0)_p,a_k>0\) ，则 \(C_n^m\equiv C_{a_k}^{b_k}C_{a_{k-1}}^{b_{k-1}}...C_{a_0}^{b_0}\:(mod~p)\)

例1

求证：对给定正整数 \(k\) ，存在无穷个正整数 \(n\) ，使得 \(\frac{(2n)!}{n!(n+k)!}\) 是整数

对每个 \(q=p^i\) ，考虑 \([\frac {2n}q]-[\frac{n}q]-[\frac {n+k}q]\) ，当 \(k<\frac q2\) 时为非负数（由 \(Hermite\) 恒等式得到 \([2x]=[x]+[x+\frac 12]\) ）

法一：只需考虑素数 \(p_1<p_2<...<p_n<2k\) 的整除关系，这时用取整函数和带余除法分析比较复杂，考虑使用 \(kummer\) 定理

\(\frac{(2n)!}{n!(n+k)!}=\frac1{k!}\cdot C_{2n}^n\cdot\frac{1}{C_{n+k}^k}\)

我们声称：对所有 \(p_i\) ，可以使 \(v_{p_i}(C_{2n}^n\cdot\frac{1}{C_{n+k}^k})\) 任意大

只需 \(n_p+n_p\) 进位尽可能多， \(n_p+k_p\) 进位尽可能少

我们设 \(p^{\alpha-1}\le k<p^\alpha\) ，可取任意 \(t\) 并令 \(n\equiv (p^t-1)p^\alpha~(mod~p^{\alpha+t})\) ，使 \((n+n)_p\) 至少产生 \(t\) 次进位，同时 \((n+k)_p\) 不产生任何进位

由 \(CRT\) 给出无穷个 \(n\) 。由于 \(t\) 可任意大，证毕

法二：考虑到对 \(p_i<2k\) ，当 \(p_i^\alpha\ge 2k\) ， \([\frac {2n}q]-[\frac{n}q]-[\frac {n+k}q]\) 是非负数

进一步地，希望是正数，补足 \(p_i^\beta<2k\) 产生的负数

我们说：可取正整数 \(n\) ，使得 \(\sum\limits_{q=p_i^j\ge 2k} ([\frac {2n}q]-[\frac{n}q]-[\frac {n+k}q])\) 任意大

本做法的关键是：用带余除法刻画 \([\frac nm]\) ，可以把 \(n(mod~m)\) 设为负数，具体地：

令 \(n\equiv -(k+1)\:(mod~p^t)\) ， \(t\) 是任意正整数

记 \(q=p_i^j> 2(k+1),j\le t\) ，可知 \([\frac {2n}q]-[\frac{n}q]-[\frac {n+k}q]=[\frac {-2(k+1)}q]-[\frac{-(k+1)}q]-[\frac {-1}q]=1\)

由于 \(t\) 可任意大，由 \(CRT\) 给出 \(n\) 的无穷解，证毕

例2

求所有正整数 \(n\ge 2\) 满足 \(C_n^0,C_n^1,..,C_n^n\) 的最大公倍数等于不超过 \(n\) 的所有素数的乘积

记 \(N=[C_n^0,C_n^1,..,C_n^n]\)

先记 \(n=(a_ka_{k-1}...a_0)_2\) ，若 \(a_i\) 全为 \(1\) ，由 \(Lucas\) 定理知 \(C_n^m\equiv 1\:(mod~2)\) ，这与 \(2\mid N\) 矛盾

那么存在 \(r\) ，使得 \(a_r=0,a_{r-1}=...=a_0=1\) ，现在令 \(m=(11...1)_2\) ，共 \(k\) 个 \(1\) ，则由 \(Kummer\) 定理知 \(v_2(C_n^m)=k-r\) ，又 \(v_2(N)=1,r\le k-1\) ，只能是 \(r=k-1\)

现在 \(n=2^{k+1}-1-2^{k-1}=3\cdot 2^{k-1}-1\) ，记 \(n=(b_lb_{l-1}...b_0)_3\)

由于 \(9\nmid n+1\) ，知 \(b_1\ne 2\) ，令 \(m=(222..2)_3\) ，共 \(l\) 个 \(2\) ，则 \(v_3(C_n^m)=l-2\le 1\) ，从而 \(l\le 3\) ， \(n\le 18+3+2=23\)

代入 \(k\) 到 \(n=3\cdot 2^{k-1}-1\) ，知 \(n=23,11,5,2\)

经检验 \(n=23,11,2\) 是问题的解

注：可以用恒等式 \([1,2,...,n+1]=(n+1)[C_n^0,...,C_n^n]\) 解决，通过下面提及的定理估计素因子幂次可以给出一个证明

例3

记 \(n=2^k\cdot l,l\) 为奇数 定义 \(f(n)=l^{1-k}\) ，证明： \(\prod_{r=1}^nf(r)\) 为不大于 \(n\) 的所有正奇数的最小公倍数的整数倍

回忆勒让德公式，将 \(p\) 的倍数统计一次， \(p^2\) 的倍数再统计一次，此时 \(p^2\) 的倍数就有了 \(2\) 的贡献，以此类推

现在考虑 \(\sum\limits_{m=1}^nv_p(f(m))=\sum\limits_{m=1}^n(1-k_m)v_p(m)=\sum\limits_{m=1}^nv_p(m)-\sum\limits_{m=1}^nk_mv_p(m)\)

关键是对 \(k_mv_p(m)=v_2(m)v_p(m)\) 的处理：我们可以对 \(p\) 的倍数先统计一次 \(v_2(m)\) ，再对 \(p^2\) 的倍数统计一次 \(v_2(m)\) 可以得到：

\(\sum\limits_{m=1}^nv_2(m)v_p(m)=v_2([\frac np]!)+v_2([\frac n{p^2}]!)+...=\sum\limits\limits_{k=1}^{[log_pk]}([\frac n{p^k}]-S_2([\frac n{p_k}]))\)

这里统计 \(v_2\) 是为了使用公式 \(v_p(n!)=\frac{n-S_p(n)}{p-1}\) 从而抵消 \([\frac n{p^k}]\) ，带回原式得

\(\sum\limits_{m=1}^nv_p(m)-\sum\limits_{m=1}^nk_mv_p(m)=\sum\limits\limits_{k=1}^{[log_pk]}S_2([\frac n{p^k}])\ge [log_pk]\)

勒让德公式的直接推论是： \(\frac np-1<v_p(n!)<\frac n{p-1}\)

并且根据 \([\frac {a+b}c]-[\frac ac]-[\frac bc]\in \{0,1\}\) ，还有 \(p^{v_p(C_n^k)}\le n\)

例4

设 \(S_n=1!+2!+...+n!\) ，证明：存在正整数 \(n\) 使得 \(S_n\) 有超过 \(10^{2012}\) 的素因子

我们设所有不超过 \(10^{2012}\) 的素数是 \(p_1<p_2<...<p_k\)

下面定义：

\(\large f(n)=i,i\in\{1,2,...,k\} \text{ s.t. } p_i^{v_{p_i}(S_n)}\text{ is the maximal}\)

\(\large g(n)=p_{f(n)}^{v_{p_{f(n)}}(S_n)}\)

对充分大 \(n\) ，考虑 \(\{n,n+1,...,n+k\}\) ，根据抽屉原理存在 \(f(n)=f(m)\) ，于是

\(\min \{g(n),g(m)\}\mid S_m-S_n=n!(n+1+(n+1)(n+2)+...+(n+1)(n+2)...m)\)

记 \(p=p_{f(n)}\) ，令 \(p^t\le n<p^{t+1}\) ，由于

\(n+1+(n+1)(n+2)+...+(n+1)(n+2)...m<p^{t+1}\cdot k<p^{t+C}\)

\(\large v_p(n!)<\frac n{p-1}\)

于是 \(v_p(S_m-S_n)<\frac{n}{p-1}+t+C<\frac n{p-1}+\log n+C\)

所以

\(\large p^{\frac n{p-1}+\log n+C}\ge g(n)\ge S_n^{\frac 1k}>\sqrt[k]{n!}>n^{\frac{n}{2k}}\)

对充分大 \(n\) 显然矛盾，证毕。

例5

求正整数 \(x,y\) 使得 \(x!-y!=x^{2007}-y^{2007}\)

我们将证明 \(x=y\) 的平凡解是问题的所有答案。

如果 \(y=1\) ， \(x!=x^{2007}\) ，很显然无解

不妨 \(x>y\) ，如果 \(y>1\) ，取 \(p\mid y\) ，于是 \(p\mid x!-y!\) ，然后 \(p\mid x\) ，这给出 \(x-y\ge p\ge 2\)

更进一步，我们看到 \(v_p(x!)>v_p(y!)\) ，所以 \(v_p(y!)=v_p(x!-y!)= v_p(x^{2007}-y^{2007})\ge 2007\) ，从而 \(\frac y{p-1}\ge 2007\)

若 \(y\) 含有不是 \(2\) 的素因子，那么 \(y\ge 4014\) 。我们下面证明对 \(x\ge 4014\) 问题无解，因为

\(x!-y!=y!(x(x-1)...(y+1)-1)>y!x(x-1)...(y+2)y\)

根据 \(y<x-1,y>1\) 有

\((x!-y!)^2\ge (x\cdot 1)[(x-1)\cdot 2]...[(x-y-1)y]...(1\cdot x)>x^x\ge x^{4014}>x^{2007}-y^{2007}\)

接下来 \(y\) 只能含有 \(2\) 的素因子，于是 \(y=2048,x<4014\) ，所以 \(v_p(x)<v_p(y)\)

分析两边 \(2\) 的幂次， \(v_2(y!)=2047\) ，而 \(v_2(x^{2007}-y^{2007})=v_2(x^{2007})=2007k\) ，矛盾！

证毕。

例6

对 \(x\in R\) 定义 \(||x||\) 表示 \(x\) 与最近的整数的距离，证明：若 \(a,b\) 是正整数，则存在素数 \(p\) 与正整数 \(k\) 使得 \(||\frac a{p^k}||+||\frac b{p^k}||+||\frac {a+b}p^k||=1\)

记 \(x=\frac a{p^k},y=\frac b{p^k}\)

很显然 \(||x||=|x-[x+\frac 12]|\)

希望是 \(\pm(x-[x+\frac 12])\pm (y-[y+\frac 12])\pm (x+y-[x+y+\frac 12])=1\) ，注意由于三个数都不超过 \(\frac 12\) ，如果对一种符号选择成立，说明这是 \(8\) 种里面和最大的一种，也就是绝对值对应的情况

选择 \(+,+,-\) ，并且知道 \([2x]-[x]=[x+\frac 12]\) ，所以要找到 \([2(x+y)]-[2x]-[2y]-([x+y]-[x]-[y])=1\) ，如果取 \(p\) 是 \(C_{2(x+y)}^{2x}/C_{x+y}^x\) 最简形式分子的素因子，就一定能找到对应的 \(k\)

这是显然的，强制展开就可以找到。

例7

设 \(a,b\) 是正整数，满足 \(a\) 被任何素数 \(p\) 除的余数不超过 \(b\) 被同一个素数 \(p\) 除的余数。证明： \(a=b\)