ルジャンドルの公式

**ステップ1:$v_p(n!)$ を各因数にわたる和として書く。** 定義により $n! = 1\cdot 2\cdots n$ なので、$v_p(n!) = \sum_{k=1}^{n} v_p(k)$、すなわち $1$ から $n$ までのすべての整数の $p$進付値の和である。

**ステップ2:各 $v_p(k)$ を数え上げとして書き換える。** 各 $k$ について、$v_p(k) = \sum_{i=1}^{\infty} [p^i \mid k]$(アイバーソン記法、真なら $1$、偽なら $0$)である、なぜなら $k$ がちょうど $v_p(k)$ 個の $i$ の値(すなわち $i=1,\dots,v_p(k)$)について $p^i$ で割り切れるからである。

ステップ3:和の順序を入れ替える。 代入すると $v_p(n!) = \sum_{k=1}^n \sum_{i=1}^{\infty} [p^i \mid k] = \sum_{i=1}^{\infty} \sum_{k=1}^n [p^i \mid k]$、(有限なので正当な)二重和を入れ替える。

**ステップ4:$p^i$ の倍数を直接数える。** 内側の和 $\sum_{k=1}^n [p^i \mid k]$ は $1$ から $n$ までの整数のうち $p^i$ の倍数がいくつあるかを数え、それはちょうど $\left\lfloor \frac{n}{p^i} \right\rfloor$ である(倍数は $p^i, 2p^i, \dots, \lfloor n/p^i\rfloor \cdot p^i$)。

ステップ5:結論。 代入し戻すと $v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$ となり、$p^i > n$ となれば $\lfloor n/p^i \rfloor = 0$ なので有限であり、証明が完了する。