階乗に含まれる素因数の個数

方針：$a$ と $b$ の素因数分解を掛けたものが $ab$ の素因数分解になり、素因数分解がただ 1 通りであることから指数を読む。
段 1。$a=p^{v_p(a)}a'$、$b=p^{v_p(b)}b'$（$a',b'$ は $p$ で割り切れない）と書ける。掛けると $ab=p^{v_p(a)+v_p(b)}\,a'b'$ である。
段 2。$a'$ と $b'$ の素因数分解には $p$ が現れないので、$a'b'$ の素因数分解（$a'$ と $b'$ の分解を並べたもの）にも $p$ は現れない。素因数分解の一意性 により $ab$ の素因数分解はこれしかないので、$ab$ の分解での $p$ の指数は $v_p(a)+v_p(b)$ である。
段 3。$n$ 個の積は、2 個の積の場合を $n-1$ 回くり返して使えばよい。$\square$

方針：$1$ から $n$ までの各数 $m$ の上に、$m$ に含まれる $p$ の個数だけ箱を積む（図 1）。箱の総数を「数ごと（縦）」と「段ごと（横）」の 2 通りに数える。
段 1（箱の置き方）。$m=1,\dots,n$ と $k=1,2,\dots$ について、$p^k\mid m$ のとき、そしてそのときに限り、位置 $(m,k)$ に箱を 1 つ置く。
段 2（縦に数える）。数 $m$ を固定する。$p^k\mid m$ となる $k\ge1$ は、def-lgf-vp により $k=1,2,\dots,v_p(m)$ である（$p^k\mid m$ なら $p^{k-1}\mid m$ なので、割り切る $k$ は $1$ から切れ目なく並ぶ）。よって $m$ の列の箱は $v_p(m)$ 個で、箱の総数は $v_p(1)+\cdots+v_p(n)=v_p(n!)$ である（prop-lgf-product）。
段 3（横に数える）。段 $k$ を固定する。段 $k$ の箱は、$1$ 以上 $n$ 以下の $p^k$ の倍数 $m$ に 1 つずつある。その個数は $\left[\dfrac n{p^k}\right]$ である（ガウス記号と整数の個数 の定理「倍数の個数」）。よって箱の総数は $\sum_{k\ge1}\left[\dfrac n{p^k}\right]$ である。
段 4。$p^k>n$ なら $1$ 以上 $n$ 以下に $p^k$ の倍数はないので、段 $k$ は空である。したがって段 3 の和は有限個の和で、段 2 と段 3 は同じ箱を数えているので等しい。$\square$

方針：末尾の $0$ の個数は $10^e\mid n!$ となる最大の $e$ であり、それは $v_2(n!)$ と $v_5(n!)$ の小さい方である。$v_2(n!)\ge v_5(n!)$ を Legendre の公式の項ごとの比較で示す。
段 1（末尾の $0$ と割り切り）。$n!$ の末尾に $0$ がちょうど $e$ 個並ぶことは、$10^e\mid n!$ かつ $10^{e+1}\nmid n!$ と同値である（末尾の $0$ を $e$ 個取り去った数の一の位が $0$ でない、ということなので）。
段 2（$10^e\mid n!$ の条件）。$10^e=2^e5^e$ なので、素因数分解の一意性 により、$10^e\mid n!$ は $e\le v_2(n!)$ かつ $e\le v_5(n!)$ と同値である。よって末尾の $0$ の個数は $\min\bigl(v_2(n!),v_5(n!)\bigr)$ である。
段 3（比較）。各 $k$ で $2^k\le5^k$ なので $\dfrac n{2^k}\ge\dfrac n{5^k}$ で、ガウス記号は大小を保つので $\left[\dfrac n{2^k}\right]\ge\left[\dfrac n{5^k}\right]$ である。$k$ について足すと、thm-lgf-legendre により $v_2(n!)\ge v_5(n!)$ である。したがって最小値は $v_5(n!)$ である。$\square$

方針：$\left[\dfrac n{p^j}\right]$ は「$n$ の $p$ 進法の数字の下 $j$ 桁を取り去った数」である。これを Legendre の公式に代入し、数字ごとに集めて等比数列の和を使う。
段 1（下の桁を取り去る）。$1\le j\le k$ について
$$ \frac n{p^j}=\bigl(a_kp^{k-j}+\cdots+a_{j+1}p+a_j\bigr)+\frac{a_{j-1}p^{j-1}+\cdots+a_1p+a_0}{p^j} $$
である。右辺の括弧の中は整数である。後ろの分数の分子は $0$ 以上で、各数字が $p-1$ 以下なので $(p-1)(p^{j-1}+\cdots+1)=p^j-1$ 以下であり、分数は $0$ 以上 $1$ 未満である。よって $\left[\dfrac n{p^j}\right]=a_kp^{k-j}+\cdots+a_{j+1}p+a_j$ である。$j>k$ では $n< p^{k+1}\le p^j$ なので $0$ である。
段 2（数字ごとに集める）。thm-lgf-legendre に段 1 を代入すると
$$ v_p(n!)=\sum_{j=1}^k\ \sum_{i=j}^ka_ip^{i-j} $$
である。数字 $a_i$ が現れるのは $j=1,\dots,i$ の $i$ 回で、係数は $p^{i-1},p^{i-2},\dots,1$ なので、$a_i$ についてまとめると
$$ v_p(n!)=\sum_{i=0}^ka_i\bigl(p^{i-1}+p^{i-2}+\cdots+1\bigr)=\sum_{i=0}^ka_i\,\frac{p^i-1}{p-1} $$
である（$i=0$ の項は $0$。等比数列の和の公式、等差数列と等比数列）。
段 3。右辺は $\dfrac1{p-1}\Bigl(\sum_ia_ip^i-\sum_ia_i\Bigr)=\dfrac{n-s_p(n)}{p-1}$ である。$\square$

方針：thm-lgf-digit-sum で $p=2$ とし、数字の和 $s_2(n)$ の大きさを見る。
段 1。$p-1=1$ なので $v_2(n!)=n-s_2(n)$ である。
段 2。$n\ge1$ なので、2 進法の数字には $1$ が少なくとも 1 つあり、$s_2(n)\ge1$ である。よって $v_2(n!)\le n-1< n$ で、$2^n\nmid n!$ である。
段 3。等号 $s_2(n)=1$ は、2 進法の数字に $1$ がちょうど 1 つ、つまり $n=10\cdots0_{(2)}=2^m$ のときに限る。$\square$

方針：実数 $x$ について $[2x]-2[x]$ が $0$ か $1$ であることを示し、$x=\dfrac n{p^k}$ に使う。2・3 では、和のうち $0$ でない可能性のある項を直接計算する。
段 1（$[2x]-2[x]$ は $0$ か $1$）。$x=[x]+f$（$0\le f<1$）と書くと $2x=2[x]+2f$ で、$2[x]$ は整数なので $[2x]=2[x]+[2f]$ である（ガウス記号と整数の個数 の基本性質「整数を足すと整数だけずれる」）。$0\le2f<2$ なので $[2f]$ は $0$ か $1$ であり、$[2x]-2[x]=[2f]$ も $0$ か $1$ である。
段 2（1 の証明）。段 1 を $x=\dfrac n{p^k}$ に使うと、各項は $0$ か $1$ である。$p^k>2n$ なら $\left[\dfrac{2n}{p^k}\right]=\left[\dfrac n{p^k}\right]=0$ なので項は $0$ である。$p^k\le2n$ となる $k\ge1$ は $k=1,\dots,K$（$K$ は $p^K\le2n$ となる最大の $k$。$p>2n$ なら $K=0$）なので、$v_p\dbinom{2n}n\le K$ で、$p^{v_p\binom{2n}{n}}\le p^K\le2n$ である。
段 3（2 の証明）。$n< p\le2n$ とする。$p\ge2$ と $p>n$ から $p^2\ge2p>2n$ なので、$k\ge2$ の項は $0$ である。$k=1$ の項は、$1\le\dfrac{2n}p<2$ から $\left[\dfrac{2n}p\right]=1$、$0<\dfrac np<1$ から $\left[\dfrac np\right]=0$ で、$1-0=1$ である。
段 4（3 の証明）。$p\ge3$、$\dfrac{2n}3< p\le n$ とする。$p^2\ge3p>2n$ なので $k\ge2$ の項は $0$ である。$k=1$ の項は、$2\le\dfrac{2n}p<3$ から $\left[\dfrac{2n}p\right]=2$、$1\le\dfrac np<\dfrac32$ から $\left[\dfrac np\right]=1$ で、$2-2\cdot1=0$ である。$\square$