• 数学竞赛

  >

  简单数论

  >

  简单数论

略

因为$$p^{j}=(p-1)p^{j-1}+(p-1)p^{j-2}+\cdots+(p-1)p+p,$$所以$$\displaystyle \sum\limits_{i<j}(p-1)p^{i}=p^{j}-1,$$从而\[\dfrac{n}{p^{j}}=\sum\limits_{i<j}d_{i}p^{i-j}+\sum\limits_{i=j}^{s}d_{i}p^{i-j}\leqslant \dfrac{p^{j}-1}{p^{j}}+\sum\limits_{i=j}^{s}d_{i}p^{i-j},\]即得 $\displaystyle \left[\dfrac{n}{p^{j}}\right]=\sum\limits_{i=j}^{s}d_{i}p^{i-j}$．

• 数学竞赛

  >

  简单数论

  >

  简单数论

略

若$$p^{\alpha}\mid n! , p^{\alpha+1}\nmid n!,$$则记 $\alpha(p,n)=\alpha$．
以 $p=2$，$n=20$ 为例，不难算得\[\alpha(2,20)=\left[\dfrac{20}{2}\right]+\left[\dfrac{20}{4}\right]+\left[\dfrac{20}{8}\right]+\left[\dfrac{20}{16}\right]=18.\]一般地，关于 $\alpha(p,n)$ 不难得出如下公式：$$\displaystyle \alpha(p,n)=\sum\limits_{i=1}^{s}\left[\dfrac{n}{p^{i}}\right].$$由第 $(1)$ 小问得\[\left[\dfrac{n}{p^{j}}\right]=\sum\limits_{i=j}^{s}n_{i}p^{i-j}, \left[\dfrac{a}{p^{j}}\right]=\sum\limits_{i=j}^{s}a_{i}p^{i-j}, \left[\dfrac{b}{p^{j}}\right]=\sum\limits_{i=j}^{s}b_{i}p^{i-j}.\]令 $c_{i}=a_{i}+b_{i},i=0,1,2,\cdots,s$，则
结论1：$\displaystyle \left[\dfrac{n}{p^{j}}\right]=\left[\sum\limits_{i<j}c_{i}p^{i-j}\right]+\left[\dfrac{a}{p^{j}}\right]+\left[\dfrac{b}{p^{j}}\right]$，$0\leqslant j\leqslant s$．
事实上，\[\begin{split}\dfrac{n}{p^{j}}&=\sum\limits_{i<j}c_{i}p^{i-j}+\sum\limits_{i=j}^{s}c_{i}p^{i-j},\\ \left[\dfrac{n}{p^{j}}\right]&=\left[\sum\limits_{i<j}c_{i}p^{i-j}\right]+\sum\limits_{i=j}^{s}a_{i}p^{i-j}+\sum\limits_{i=j}^{s}b_{i}p^{i-j}\\&=\left[\sum\limits_{i<j}c_{i}p^{i-j}\right]+\left[\dfrac{a}{p^{j}}\right]+\left[\dfrac{b}{p^{j}}\right].\end{split}\]结论2：若存在 $l$，$0\leqslant l\leqslant s$，$l\in\mathbb N^{*}$，有 $\displaystyle \sum\limits_{i<l}c_{i}p^{i}=\sum\limits_{i<j}n_{i}p^{i}$，而 $n_{l}\ne c_{l}$，则存在正整数 $u$，$1\leqslant u\leqslant s-l$，有\[c_{i}=\begin{cases}n_{l}+p,&i=l,\\ n_{i}+p-1,&l<i<l+u,\\ n_{l+u}-1,&i=l+u.\end{cases}\]证明：因为 $a+b=n$，所以$$\displaystyle \sum\limits_{i=0}^{s}(c_{i}-n_{i})p^{i}=0.$$又由$$\displaystyle \sum\limits_{i<j}c_{i}p^{i}=\sum\limits_{i<l}n_ip^{i},$$即得\[(c_{l}-n_{l})p^{l}=-\sum\limits_{i=l+1}^{s}(c_{i}-n_{i})p^{i}=p^{l+1}\sum\limits_{i=l+1}^{s}(n_{i}-c_{i})p^{i-(l+1)},\]所以 $p\mid (c_{l}-n_{l})$．
因为 $0\leqslant n_{l}\leqslant p-1$，$0\leqslant c_{l}\leqslant 2(p-1)$，所以$$c_{l}=n_{l}+p,$$进而\[(c_{l}-n_{l})p^{l}=pp^{l}=(n_{l+1}-c_{l+1})p^{l+1}+p^{l+2}\sum\limits_{i=l+2}^s(n_{i}-c_{i})p^{i-l-2},\]所以 $p\mid(1+c_{l+1}-n_{l+1})$．
若 $1+c_{l+1}-n_{l+1}=0$，则$$c_{l+1}=n_{l+1}-1,$$即 $u=1$．
若 $1+c_{l+1}-n_{l+1}=p$，则$$c_{l+1}=n_{l+1}+(p-1),$$由于\[p^{l+1}+(c_{l+1}-n_{l+1})p^{l+1}=p^{l+1}+(p-1)p^{l+1}=p^{l+2},\]所以\[p^{l+2}=(n_{l+2}-c_{l+2})p^{l+2}+p^{l+3}\sum\limits_{i=l+3}^{s}(n_{i}-c_{i})p^{i-l-3},\]从而 $p\mid(1+c_{l+2}-n_{l+2})$．
所以 $c_{l+2}=n_{l+2}-1$，即 $u=2$．否则又有 $c_{l+2}=n_{l+2}+(p-1)$，$\cdots$．
由于$$\displaystyle \sum\limits_{i=0}^sc_{i}p^{i}=\sum\limits_{i=0}^{s}n_{i}p^{i},$$所以一定存在正整数 $u$，$1\leqslant u\leqslant s-l$ 使得$$1+c_{l+u}-n_{l+u}=0,$$即 $c_{l+u}=n_{l+u}-1$，结论2证毕．
相对于 $n$ 的 $p$ 进制表示，称 $\displaystyle \sum\limits_{i=0}^{s}c_{i}p^{i}$ 中的一段 $\displaystyle \sum\limits_{i=l}^{l+u}c_{i}p^{i}$ 为长度为 $u$ 的一个下段移，记为 $(l,u)$．
显然，$\displaystyle \sum\limits_{i=l}^{l+u}c_{i}p^{i}=\sum\limits_{i=l}^{l+u}n_{i}p^{i}$，从而有$$\displaystyle \sum\limits_{i=0}^{l+u}c_{i}p^{i}=\sum\limits_{i=0}^{l+u}n_{i}p^{i},$$此即结论2的条件．
因此当 $i>l+u$ 时，若有 $n_{i}\ne c_{i}$，则必然有 $c_{i}=n_{i}+p$，存在另一个下移段．
由上述讨论知，若 $\{c_{i}\mid i=0,1,\cdots,s-1\}$ 中有 $t$ 个 $c_{i}=n_{i}+p$，则 $\displaystyle \sum\limits_{i=0}^{s}c_{i}p^{i}$ 中存在 $t$ 个下移段 $(l_{k},u_{k}),k=1,2,\cdots,t$．
若 $j\not\in [l_{k},l_{k}+u_{k}]$，$k=1,2,\cdots,t$，显然有 $n_{j}=c_{j}$，且\[\sum\limits_{i<j}c_{i}p^{i}=\sum\limits_{i<j}n_{i}p^{i}.\]若 $j=l_{k}$，$k=1,2,\cdots,t$，$c_{j}=n_{j}+p$，仍然有\[\sum\limits_{i<j}c_{i}p^{i}=\sum\limits_{i<j}n_{i}p^{i}.\]上述两种情况均有\[\sum\limits_{i<j}c_{i}p^{i}=\sum\limits_{i<j}n_{i}p^{i},\]所以由结论1及第 $(1)$ 小问知\[\left[\dfrac{n}{p^{j}}\right]=\left[\dfrac{a}{p^{j}}\right]+\left[\dfrac{b}{p^{j}}\right].\]对任一 $k$，$1\leqslant k\leqslant t$，当 $j\in [l_{k}+1,l_{k}+u_{k}]$，记 $M=\left[\dfrac{n}{p^{j}}\right]-\left[\dfrac{a}{p^{j}}\right]-\left[\dfrac{b}{p^{j}}\right]$，则由结论1知，\[\begin{split}M&= \left[\dfrac{n}{p^{j}}\right]-\left[\dfrac{a}{p^{j}}\right]-\left[\dfrac{b}{p^{j}}\right]\\&=\left[\dfrac{1}{p^{j}}\sum\limits_{i<j}c_{i}p^{i}\right]\\&=\left[\dfrac{1}{p^{j}}\sum\limits_{i<j}n_{i}p^{i}+\dfrac{1}{p^{j}}(pp^{l_{k}}+(p-1)p^{l_{k}+1}+\cdots+(p-1)p^{j-1})\right]\\&=\left[\dfrac{p^{j}-1}{p^{j}}+\dfrac{p^{j}}{p^{j}}\right]=1.\end{split}\]综上所述，即得\[\alpha(p,n)=\sum\limits_{i=1}^{s}\left[\dfrac{n}{p^{i}}\right]=\sum\limits_{i=1}^{s}\left[\dfrac{a}{p^{i}}\right]+\sum\limits_{i=1}^{s}\left[\dfrac{b}{p^{i}}\right]+\sum\limits_{k=1}^{t}u_{k}.\]令 $\displaystyle \sum\limits_{k=1}^tu_{k}=\beta$，则\[\alpha(p,n)=\alpha(p,a)+\alpha(p,b)+\beta.\]从而有\[\begin{split}p^{\beta}\mid {\dfrac{n!}{a!b!}}, p^{\beta+1}\nmid{\dfrac{n!}{a!b!}}&\Leftrightarrow \alpha(p,n)=\alpha(p,a)+\alpha(p,b)+\beta\\&\Leftrightarrow \beta =|\{i|c_{i}>n_{i},i=0,1,2,\cdots,s\}|.\end{split}\]