Legendre公式和Kummer定理

Legendre公式

对于质数$p$，函数$v_p(n)$为$n$标准分解后$p$的次数

显然有

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

令函数$s_p(n)$为$n$在$p$进制下的数位和

有:

\[v_p(n!) = \frac{n - s_p(n)}{p - 1}\]

证明:

设$n = \sum\limits_{i = 0}^{\infty} c_i p^i$，

有$v_p(n!) = \sum\limits_{i = 1}^{\infty} \lfloor \frac{n}{p^i} \rfloor$

$= \sum\limits_{i = 1}^{\infty} \sum\limits_{j = i}^{\infty} c_j p^{j - i}$

$= \sum\limits_{j = 1}^{\infty} c_j \sum\limits_{i = 0}^{j - 1} p^i$

$= \sum\limits_{j = 1}^{\infty} \frac{c_j(p^j - 1)}{p - 1}$

$= \frac{1}{p - 1} (\sum\limits_{i = 0}^{\infty} c_i p^i - \sum\limits_{i = 0}^{\infty} c_i)$

$= \frac{n - s_p(n)}{p - 1} $

二项式系数

\[v_p(\binom{n}{m}) = \frac{s_p(m) + s_p(n - m) - s_p(n)}{p - 1}\]

同时也等于在$p$进制下运算$n - m$时退位的次数

多项式系数

$\binom{n}{m_1, \cdots, m_k} = \frac{n!}{m_1! \cdots m_k!}$

\[v_p(\binom{n}{m_1, \cdots, m_k}) = \frac{\sum\limits_{i = 1}^k s_p(m_i) - s_p(n)}{p - 1}\]