Legendre公式和Kummer定理

Legendre公式

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

显然有

v p ( n ! ) = ∑ i = 1 ∞ ⌊ n p i ⌋ v_p(n!) = \sum\limits_{i = 1}^{\infty} \lfloor \frac{n}{p^i} \rfloor vp​(n!)=i=1∑∞​⌊pin​⌋

令函数 s p ( n ) sp(n) sp(n)为 n n n在 p p p进制下的数位和

有：

v p ( n ! ) = n − s p ( n ) p − 1 v_p(n!) = \frac{n - s_p(n)}{p - 1} vp​(n!)=p−1n−sp​(n)​

证明：

设 n = ∑ i = 0 ∞ c i p i n= \sum\limits_{i = 0}^{\infty}c_i p^i n=i=0∑∞​ci​pi

v p ( n ! ) = ∑ i = 1 ∞ ⌊ n p i ⌋ = ∑ i = 1 ∞ ∑ j = i ∞ c j p j − i = ∑ j = 1 ∞ c j ∑ i = 0 j − 1 p i = ∑ j = 1 ∞ c j ( p j − 1 ) p − 1 = 1 p − 1 ( ∑ i = 0 ∞ c i p i − ∑ i = 0 ∞ c i ) = n − s p ( n ) p − 1 \begin{aligned} v_p(n!)&=\sum_{i = 1}^{\infty} \lfloor\frac{n}{p^i} \rfloor\\ &= \sum_{i = 1}^{\infty} \sum_{j = i}^{\infty} c_j p^{j - i}\\ &= \sum_{j = 1}^{\infty} c_j \sum_{i = 0}^{j - 1} p^i\\ &= \sum_{j = 1}^{\infty} \frac{c_j(p^j - 1)}{p - 1}\\ &= \frac{1}{p - 1} (\sum_{i = 0}^{\infty} c_i p^i - \sum_{i = 0}^{\infty} c_i)\\ &= \frac{n - s_p(n)}{p - 1}\\ \end{aligned} vp​(n!)​=i=1∑∞​⌊pin​⌋=i=1∑∞​j=i∑∞​cj​pj−i=j=1∑∞​cj​i=0∑j−1​pi=j=1∑∞​p−1cj​(pj−1)​=p−11​(i=0∑∞​ci​pi−i=0∑∞​ci​)=p−1n−sp​(n)​​

Kummer定理

设 m m m， n n n为正整数， p p p为素数，则 ( m + n n ) {m+n\choose n} (nm+n​)含 p p p的幂次等于 m + n m+n m+n在 p p p进制下的进位次数。

v p ( ( n m ) ) = v p ( ( m + n ) ! n ! m ! ) = v p ( ( m + n ) ! ) − v p ( n ! ) − v p ( m ! ) = ∑ i = 0 ∞ ⌊ m + n p i ⌋ − ∑ i = 0 ∞ ⌊ n p i ⌋ − ∑ i = 0 ∞ ⌊ m p i ⌋ = ∑ i = 0 ∞ ⌊ m + n p i ⌋ − ⌊ n p i ⌋ − ⌊ m p i ⌋ \begin{aligned} v_p\bigg({n\choose m}\bigg)&=v_p\bigg(\frac{(m+n)!}{n!m!}\bigg)\\ &=v_p((m+n)!)-v_p(n!)-v_p(m!)\\ &=\sum_{i=0}^{\infty}\lfloor\frac{m+n}{p^i}\rfloor-\sum_{i=0}^{\infty}\lfloor\frac{n}{p^i}\rfloor-\sum_{i=0}^{\infty}\lfloor\frac{m}{p^i}\rfloor\\ &=\sum_{i=0}^{\infty}\lfloor\frac{m+n}{p^i}\rfloor-\lfloor\frac{n}{p^i}\rfloor-\lfloor\frac{m}{p^i}\rfloor\\ \end{aligned} vp​((mn​))​=vp​(n!m!(m+n)!​)=vp​((m+n)!)−vp​(n!)−vp​(m!)=i=0∑∞​⌊pim+n​⌋−i=0∑∞​⌊pin​⌋−i=0∑∞​⌊pim​⌋=i=0∑∞​⌊pim+n​⌋−⌊pin​⌋−⌊pim​⌋​