Công thức Legendre

**Bước 1: Viết $v_p(n!)$ thành tổng theo từng thừa số.** Theo định nghĩa $n! = 1\cdot 2\cdots n$, nên $v_p(n!) = \sum_{k=1}^{n} v_p(k)$, tổng định giá $p$-adic của mọi số nguyên từ $1$ đến $n$.

**Bước 2: Viết lại mỗi $v_p(k)$ thành một phép đếm.** Với mỗi $k$, $v_p(k) = \sum_{i=1}^{\infty} [p^i \mid k]$ (dùng ký hiệu Iverson, $1$ nếu đúng, $0$ nếu sai), vì $k$ chia hết cho $p^i$ đúng với $v_p(k)$ giá trị $i$ (cụ thể $i=1,\dots,v_p(k)$).

Bước 3: Đổi thứ tự tổng. Thay vào, $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]$, đổi thứ tự tổng kép (hữu hạn nên hợp lệ).

**Bước 4: Đếm trực tiếp bội của $p^i$.** Tổng trong $\sum_{k=1}^n [p^i \mid k]$ đếm có bao nhiêu số nguyên từ $1$ đến $n$ là bội của $p^i$, đúng bằng $\left\lfloor \frac{n}{p^i} \right\rfloor$ (các bội là $p^i, 2p^i, \dots, \lfloor n/p^i\rfloor \cdot p^i$).

Bước 5: Kết luận. Thay lại, $v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$, hữu hạn vì $\lfloor n/p^i \rfloor = 0$ khi $p^i > n$, hoàn tất chứng minh.