本帖最后由 hbghlyj 于 2023-4-28 20:30 编辑
Wikipedia
引用了下面这篇短文: Proof based on generating functions. This proof is due to Nathan Fine.[2]
Binomial Coefficients Modulo a Prime, N. J. Fine (JSTOR)
noTXT.pdf
(355.26 KB, 下载次数: 0)
用ghostscript把每页的页脚的“downloaded from...”文本去掉了.处理第3页时报错“Error: Ignoring spurious ET operator. Output may be incorrect.”但是我看了一下输出的文件应该没出什么问题
THEOREM 1. Let $p$ be a prime, and let
\begin{array}{cl}
M=M_{0}+M_{1} p+M_{2} p^{2}+\cdots+M_{k} p^{k} & \left(0 \leqq M_{r}< p\right) \\
N=N_{0}+N_{1} p+N_{2} p^{2}+\cdots+N_{k} p^{k} & \left(0 \leqq N_{r}< p\right)
\end{array}
Then
$$
\left(\begin{array}{c}
M \\
N
\end{array}\right) \equiv\left(\begin{array}{c}
M_{0} \\
N_{0}
\end{array}\right)\left(\begin{array}{c}
M_{1} \\
N_{1}
\end{array}\right)\left(\begin{array}{c}
M_{2} \\
N_{2}
\end{array}\right) \cdots\left(\begin{array}{c}
M_{k} \\
N_{k}
\end{array}\right)(\bmod p) .
$$
We offer a short proof of the above theorem:
\begin{aligned}
\sum_{N=0}^{M}\left(\begin{array}{c}
M \\
N
\end{array}\right) x^{N} &=(1+x)^{M}=\prod_{r=0}^{k}\left\{(1+x)^{p^r}\right\}^{M_r} \\
& \equiv \prod_{r=0}^{k}\left(1+x^{p^{r}}\right)^{M_{r}}(\bmod p) \\
&=\prod_{r=0}^{k}\left\{\sum_{s_{r}=0}^{M_{r}}\left(\begin{array}{c}
M_{r} \\
s_{r}
\end{array}\right) x^{s_r p^r}\right\} \\
&=\sum_{N=0}^{M}\left\{\prod_{r=0}^{k}\left(\begin{array}{c}
M_{r} \\
s_{r}
\end{array}\right)\right\} x^{N}
\end{aligned}
where the inner sum is taken over all sets $\left(s_{0}, s_{1}, \cdots, s_{k}\right)$ such that $\sum_{r=0}^{k} s_{r} p^{r}=N$. But $0 \leqq s_{r} \leqq M_{r}< p$, so there is at most one such set, given by $s_{r}=N_{r}(0 \leqq r \leqq k)$ if every $N_{r} \leqq M_{r}$; if not, the sum is zero. The theorem follows by equating coefficients of $x^{N}$, since
$$
\left(\begin{array}{c}
M_{r} \\
N_{r}
\end{array}\right)=0 \quad \text { for } \quad N_{r}>M_{r}
$$$\Box$
THEOREM 2. Let $T(M)$ be the number of integers $N$ not exceeding $M$ for which
$$
\left(\begin{array}{c}
M \\
N
\end{array}\right) \not \equiv 0(\bmod p) .
$$
Then
$$
T(M)=\prod_{r=0}^{k}\left(M_{r}+1\right)
$$
Proof: Since $M_{r}< p$, there are $M_{r}+1$ values of $N_{r}$, given by $0 \leqq N_{r} \leqq M$, for which
$$
\left(\begin{array}{c}
M_{r} \\
N_{r}
\end{array}\right) \not \equiv 0(\bmod p)
$$
and these are the only ones. $\Box$
THEOREM 3. A necessary and sufficient condition that all the binomial coefficients
$$
\left(\begin{array}{l}
M \\
N
\end{array}\right), \quad 0< N< M
$$
be divisible by $p$ is that $M$ be a power of $p$.
Proof: The function $T(M)$ takes the value 2 if and only if one of the $M_{r}$ is 1 and all the others are 0. $\Box$
In the opposite direction, we may ask for what values of $M$ none of the binomial coefficients
$$
\left(\begin{array}{l}
M \\
N
\end{array}\right), \quad 0 \leqq N \leqq M,
$$
are divisible by $p$.
THEOREM 4. A necessary and sufficient condition that none of the binomial coefficients of order $M$, with
$$
M=M_{0}+M_{1} p+\cdots+M_{k} p^{k} \quad\left(0 \leqq M_{\tau}< p ; M_{k}>0\right)
$$
be divisible by $p$ is that $M_{r}=p-1$ for $r< k$.
Proof: Let $M^{*}=M-M_{k} p^{k}$. Suppose first that $T(M)=M+1$. Then
\begin{aligned}
M_{k} p^{k}+M^{*}+1 &=M+1=T(M)=\left(M_{k}+1\right) T\left(M^{*}\right) \leqq\left(M_{k}+1\right)\left(M^{*}+1\right) \\
&=M_{k}\left(M^{*}+1\right)+M^{*}+1 \leqq M_{k} p^{k}+M^{*}+1
\end{aligned}
From this chain of inequalities it follows that $M^{*}=p^{k}-1$. Conversely, if $M^{*}=p^{k}-1$, then
$$
T(M)=\left(M_{k}+1\right) p^{k}=M_{k} p^{k}+M^{*}+1=M+1 .
$$$\Box$
Our last theorem deals with the "probability" that a binomial coefficient chosen "at random" will be divisible by $p$. More precisely, consider the $\frac{1}{2}(m+1)(m+2)$ binomial coefficients
$$
\left(\begin{array}{l}
M \\
N
\end{array}\right), \quad 0 \leqq N \leqq M \leqq m,
$$
and let $Q(p ; m)$ be the fraction of these which are not divisible by $p$.
THEOREM 5. For every prime $p, \lim _{m \rightarrow \infty} Q(p ; m)=0$.
Proof: For $k \geqq 0$, let
$$
G(k)=\frac{1}{2} p^{k}\left(p^{k}+1\right) Q\left(p ; p^{k}-1\right)=\sum_{M=0}^{p k-1} T(M)
$$
Clearly $G(0)=1$. Using the notation introduced in the proof of the preceding theorem, we have
$$
\begin{aligned}
G(k+1) &=\sum_{M=0}^{p^{k+1}-1} T(M) \\
&=\sum_{M_{k}=0}^{p-1} \sum_{M^{*}=0}^{p k-1}\left(M_{k}+1\right) T\left(M^{*}\right)\\
&=\left\{\sum_{M_{k}=0}^{p-1}\left(M_{\dot{k}}+1\right)\right\}\left\{\sum_{M^{*}=0}^{p^{k}-1} T\left(M^{*}\right)\right\} \\
&=\frac{1}{2} p(p+1) G(k)
\end{aligned}
$$
It follows immediately that $G(k)=\left(\frac{1}{2} p(p+1)\right)^{k}$. Now suppose that $p^{k} \leqq m< p^{k+1}$. Then
\begin{aligned}
Q(p ; m) & \leqq \frac{2}{(m+1)(m+2)} G(k+1)<2 p^{-2 k} G(k+1)=2 p^{-2 k}\left(\frac{1}{2} p(p+1)\right)^{k+1} \\
&=p(p+1)\left(\frac{1+1 / p}{2}\right)^{k}
\end{aligned}
which tends to 0 with increasing $m$.
By an obvious extension it follows that, given an arbitrary finite set of primes, it is "virtually certain" that a binomial coefficient chosen at random will be divisible by all the primes in the set. $\Box$ | 
realnumber
发表于 2013-11-7 20:25
hbghlyj
发表于 2022-9-14 11:30
