\(\S 1\) 数论函数 \(v_p(n)\)
上课用的是 \(\operatorname{pot}_p(n)\)，但是 \(v_p(n)\) 是更常用的用法（虽然可能有歧义），但两者含义完全相同，所以笔者下面全部用 \(v_p(n)\)，望见谅。
定义
对于一给定素数 \(p\)，设 \(p^m \parallel n\)，即 \(p^m \mid n,\ p^{m+1} \nmid n\)，则记 \(v_p(n)=m\)
对于有理数 \(\displaystyle\frac a b\)，有 \(\displaystyle v_p\!\left(\frac a b\right)=v_p(a)-v_p(b)\)
基本性质
- \(v_p(mn)=v_p(m)+v_p(n)\)
- \(v_p(n^k)=k\cdot v_p(n)\)
例子：
\[
\begin{aligned}
v_3(54) &= v_3(3^3\times 2) \\
&= v_3(3^3)+v_3(2) \\
&= 3v_3(3)+0 \\
&= 3
\end{aligned}
\]
定理 1
\[
\text{设 } p^k \le n \le p^{k+1},\ p \text{ 是素数},\ \text{则有 } v_p(n!) = \left\lfloor \frac n p \right\rfloor + \left\lfloor \frac n {p^2} \right\rfloor + \cdots + \left\lfloor \frac{n }{p^k} \right\rfloor
\]
证明
根据函数性质 \(v_p(n!)=v_p(1)+v_p(2)+\cdots+v_p(n)\)
对于 \(1\le k \le n\)，若 \(\gcd(k,p)=1\)，\(v_p(k)=0\)，则只剩下 \(p\) 倍数对应的 \(v_p(k)\)
同时 \(1,2,\cdots,n\) 中包含 \(\left\lfloor \frac n p \right\rfloor\) 个 \(p\) 的倍数，据此可得
\[
\begin{equation}
v_p(n!) = v_p(p)+v_p \left( 2p \right)+\cdots + v_p\left(\left\lfloor \frac n p \right\rfloor p\right)
\end{equation}
\]
又
\[
\begin{equation*}
v_p \left( kp \right) = v_p(k)+v_p(p) = v_p(k)+1,\quad k=1,2,\cdots, \left\lfloor \frac n p \right\rfloor
\end{equation*}
\]
所以就有
\[
\begin{aligned}
v_p(n!) &= \sum_{i=1}^{\left\lfloor \frac n p \right\rfloor} v_p(i) + 1 \cdot \left\lfloor \frac n p \right\rfloor \\
&= v_p(\left\lfloor \frac n p \right\rfloor !)+\left\lfloor \frac n p \right\rfloor
\end{aligned}
\]
类似地，我们对 \(v_p \left( \frac n p \right)\) 执行式 \((1)\) 的类似操作：
也就是说将 \(\left\lfloor \frac n p \right\rfloor\) 看作新的 n，那么在 \(1 \sim \left\lfloor \frac n p \right\rfloor\) 中，有
\[
\left\lfloor \frac{\left\lfloor \frac{n}{p} \right\rfloor}{p} \right\rfloor = \left\lfloor \frac{n}{p^2} \right\rfloor
\]
这里是由于 \(\left\lfloor \frac{n}{p} \right\rfloor \sim \frac n p\) 之间没有 \(p\) 的倍数
\[
\begin{equation}
v_p(n!)=\left\lfloor \frac n p \right\rfloor + \left\lfloor \frac{n }{p^2} \right\rfloor + \sum_{i=1}^{\left\lfloor \frac{n }{p^2} \right\rfloor } v_p(i)
\end{equation}
\]
以此类推：
\[
\begin{equation}
v_p(n!) = \left\lfloor \frac n p \right\rfloor +\left\lfloor \frac n {p^2} \right\rfloor + \cdots + \left\lfloor \frac n {p^k} \right\rfloor + \sum_{i=1}^{\left\lfloor \frac n {p^k } \right\rfloor} v_p(i)
\end{equation}
\]
因为 \(p^k \le n < p^{k+1}\)，所以
\[
\begin{equation*}
v_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \frac{n }{p^i} \right\rfloor \quad \square
\end{equation*}
\]
推论：
\[ n!=\prod_{i=1}^{s } p_i^{a_i} = \prod_{i=1}^{s } p_i^{\sum\limits_{j=1 }^{\infty} \left\lfloor \frac{n}{p_i^j} \right\rfloor} \]
定理2
\[
\text{设 } 0 < r < n,\ \text{ 则 } \begin{pmatrix}
n \\
r
\end{pmatrix} = \frac{n!}{r!(n-r)!} \text{ 是一个整数}
\]
证明
\[
\text{设 } n!=p_1^{a_1}\cdots p_s^{a_s},\ r!=p_1^{b_1}\cdots p_s^{b_s},\ (n-r)!=p_1^{c_1}\cdots p_s^{c_s}
\]
\[
a_i,b_i,c_i \ge 0,\quad i=1,2,\cdots,s
\]
\[
n!= \prod_{i=1}^{s } p_i^{\sum\limits_{j=1 }^{\infty} \left\lfloor \frac{n}{p_i^j} \right\rfloor},\
r!= \prod_{i=1}^{s } p_i^{\sum\limits_{j=1 }^{\infty} \left\lfloor \frac{r}{p_i^j} \right\rfloor},\
(n-r)!= \prod_{i=1}^{s } p_i^{\sum\limits_{j=1 }^{\infty} \left\lfloor \frac{n-r}{p_i^j} \right\rfloor}
\]
\[
\begin{equation*}
r!(n-r)!=\prod_{i=1}^{s } p_i^{\sum\limits_{j=1}^{\infty} \left\lfloor {\frac{r }{p_i^j }}\right\rfloor+\sum\limits_{j=1}^{\infty} \left\lfloor {\frac{n-r }{p_i^j }} \right\rfloor }
\end{equation*}
\]
\[
\because n = r+n-r \implies \frac{n }{p_i^j}=\frac{r }{p_i^j }+\frac{n-r }{p_i^j }
\]
\[
\therefore \left\lfloor \frac{n }{p_i^j } \right\rfloor \ge \left\lfloor \frac{r }{p_i^j } \right\rfloor+\left\lfloor \frac{n-r }{p_i^j } \right\rfloor
\]
\[
\therefore \sum_{j=1}^{\infty} \left\lfloor \frac{n }{p_i^j } \right\rfloor \ge \sum_{j=1}^{\infty} \left\lfloor \frac{r }{p_i^j } \right\rfloor +\sum_{j=1}^{\infty} \left\lfloor \frac{n-r }{p_i^j } \right\rfloor
\]
\[
\therefore p_i^{\sum_{j=1}^{\infty} \left\lfloor \frac{r }{p_i^j } \right\rfloor+\sum_{j=1}^{\infty} \left\lfloor \frac{n-r }{p_i^j } \right\rfloor} \mid p_i^{\sum_{j=1}^{\infty} \left\lfloor \frac{n }{p_i^j } \right\rfloor}
\]
\[
\therefore \begin{pmatrix}
n \\
r
\end{pmatrix} = \frac{n!}{r!(n-r)!} \text{ 是一个整数}\quad \square
\]