Lemma for Legendre’s Formula

Bổ đề. Cho $a_1, a_2, \dots, a_n$ là các số nguyên khác $0$ và $p$ là một số nguyên tố. Với mỗi chỉ số $i$ , gọi $x_i$ là số lượng các số là bội của $p^i$ trong dãy $a_1, a_2, \dots, a_n$ . Khi đó

$\displaystyle v_p \left( \prod_{j=1}^n a_j \right) = \sum_{i=1}^{+\infty} x_i.$

Chứng minh. Xét tập hợp $\displaystyle S = \{ (i, j) \mid i \in \mathbb{Z}^+, 1 \le j \le n, p^i \mid a_j \}$ .

Ta đếm số phần tử của tập hợp $S$ theo hai cách.

Cách 1: Với mỗi số nguyên dương $i$ cố định, số lượng các chỉ số $j$ ( $1 \le j \le n$ ) sao cho $a_j$ chia hết cho $p^i$ chính là $x_i$ . Do đó khi cho $i$ chạy qua tất cả các giá trị nguyên dương, tổng số phần tử của $S$ là $\displaystyle |S| = \sum_{i=1}^{+\infty} x_i$ .
Cách 2: Với mỗi chỉ số $j$ cố định ( $1 \le j \le n$ ), số lượng các số nguyên dương $i$ sao cho $a_j$ chia hết cho $p^i$ đúng bằng lũy thừa lớn nhất của $p$ là ước của $a_j$ , tức là bằng $v_p(a_j)$ . Khi cho $j$ chạy từ $1$ đến $n$ , tổng số phần tử của $S$ là $\displaystyle |S| = \sum_{j=1}^n v_p(a_j)$ .