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)$ .

Từ hai cách đếm trên, ta suy ra $\displaystyle \sum_{i=1}^{+\infty} x_i = \sum_{j=1}^n v_p(a_j).$

Kết hợp với tính chất của hàm định giá, ta nhận được đẳng thức mong muốn. ∎

Min-Max Identities for the Least Common Multiple and Greatest Common Divisor

Bổ đề. Với mọi số nguyên dương $a_1, a_2, \dots, a_n$ , ta có các hệ thức

$\displaystyle [a_1, a_2, \dots, a_n] = \prod_{k=1}^n \left( \prod_{1 \le i_1 < i_2 < \dots < i_k \le n} (a_{i_1}, a_{i_2}, \dots, a_{i_k}) \right)^{(-1)^{k-1}}$

và

$\displaystyle (a_1, a_2, \dots, a_n) = \prod_{k=1}^n \left( \prod_{1 \le i_1 < i_2 < \dots < i_k \le n} [a_{i_1}, a_{i_2}, \dots, a_{i_k}] \right)^{(-1)^{k-1}}.$

Chứng minh. Gọi $\alpha_i = v_p(a_i) \ge 0$ là số mũ của $p$ trong phân tích tiêu chuẩn của $a_i$ (với $i = 1, 2, \dots, n$ ).

Ta đã biết rằng số mũ của $p$ trong bội chung nhỏ nhất $[a_{i_1}, \dots, a_{i_k}]$ là $\max(\alpha_{i_1}, \dots, \alpha_{i_k})$ , và số mũ của $p$ trong ước chung lớn nhất $(a_{i_1}, \dots, a_{i_k})$ là $\min(\alpha_{i_1}, \dots, \alpha_{i_k})$ .

Do đó, để chứng minh hai hệ thức đã cho, ta chỉ cần chứng minh hai đẳng thức về số mũ sau đây với mọi dãy số nguyên không âm $\alpha_1, \dots, \alpha_n$ :

$\displaystyle \max(\alpha_1, \dots, \alpha_n) = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} \min(\alpha_{i_1}, \dots, \alpha_{i_k}) \qquad (1)$

và

$\displaystyle \min(\alpha_1, \dots, \alpha_n) = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} \max(\alpha_{i_1}, \dots, \alpha_{i_k}). \qquad (2)$

Xét các tập hợp $A_i = \{1, 2, \dots, \alpha_i\}$ với mỗi $i = 1, \dots, n$ (nếu $\alpha_i = 0$ thì $A_i = \emptyset$ ). Số phần tử của tập hợp $A_i$ chính là $|A_i| = \alpha_i$ . Với mọi tập con các chỉ số $I = \{i_1, i_2, \dots, i_k\}$ , ta có

$\displaystyle \left| \bigcap_{j=1}^k A_{i_j} \right| = \min(\alpha_{i_1}, \dots, \alpha_{i_k})$

và

$\displaystyle \left| \bigcup_{j=1}^k A_{i_j} \right| = \max(\alpha_{i_1}, \dots, \alpha_{i_k}).$

Áp dụng Nguyên lý bù trừ cho số phần tử của tập hợp hợp, ta có

$\displaystyle \left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} \left| \bigcap_{j=1}^k A_{i_j} \right|.$

Thay các giá trị lực lượng tập hợp vào, ta lập tức thu được đẳng thức $(1)$ .

Tương tự, áp dụng Nguyên lý bù trừ dạng đối ngẫu cho số phần tử của tập hợp giao, ta có

$\displaystyle \left| \bigcap_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} \left| \bigcup_{j=1}^k A_{i_j} \right|.$

Thay các giá trị tương ứng vào, ta nhận được đẳng thức $(2)$ .

Vì số mũ của mọi số nguyên tố $p$ ở cả hai vế của các hệ thức đều bằng nhau, các hệ thức về bội chung nhỏ nhất và ước chung lớn nhất ban đầu được chứng minh hoàn toàn. $\Box$

Sum of Divisor Functions

Bổ đề. Với mỗi số nguyên dương $n$ , ta có $\displaystyle \sum_{k=1}^n \tau(k) = \sum_{k=1}^n \left[ \frac{n}{k} \right]$ và

$\displaystyle \sum_{k=1}^n \sigma(k) = \sum_{k=1}^n k \cdot \left[ \frac{n}{k} \right].$

Chứng minh. Xét đẳng thức thứ nhất. Theo định nghĩa, $\tau(k)$ là số lượng các ước số dương của $k$ , nên ta có thể viết $\tau(k) = \sum_{d|k} 1$ . Thay biểu thức này vào vế trái, ta được

$\displaystyle \sum_{k=1}^n \tau(k) = \sum_{k=1}^n \sum_{d|k} 1.$

Thay vì tính tổng theo $k$ trước, ta sẽ đổi thứ tự lấy tổng bằng cách cố định số nguyên dương $d \in \{1, 2, \dots, n\}$ . Ta cần đếm xem $d$ là ước của bao nhiêu số nguyên dương $k$ không vượt quá $n$ .

Các số $k$ nhận $d$ làm ước chính là các bội số của $d$ , bao gồm: $d, 2d, 3d, \dots, md$ . Vì $k \le n$ nên ta phải có $md \le n$ , tương đương với $m \le \frac{n}{d}$ . Số lượng các bội số thỏa mãn điều kiện này chính là phần nguyên của $\frac{n}{d}$ , ký hiệu là $\left[ \frac{n}{d} \right]$ .

Vì mỗi bội số $k$ đóng góp $1$ đơn vị vào tổng chung tương ứng với ước $d$ , ta có:

$\displaystyle \sum_{k=1}^n \tau(k) = \sum_{d=1}^n \sum_{\substack{k=1 \\ d|k}}^n 1 = \sum_{d=1}^n \left[ \frac{n}{d} \right].$

Chỉ cần đổi tên biến chạy $d$ thành $k$ , ta thu được đẳng thức thứ nhất.

Hoàn toàn tương tự đối với đẳng thức thứ hai. Nhớ lại định nghĩa hàm tổng các ước $\sigma(k) = \sum_{d|k} d$ , ta viết lại vế trái:

$\displaystyle \sum_{k=1}^n \sigma(k) = \sum_{k=1}^n \sum_{d|k} d .$

Lại tiến hành đổi thứ tự lấy tổng, ta cố định ước $d \in \{1, 2, \dots, n\}$ . Mỗi khi $k$ là một bội số của $d$ (và $k \le n$ ), số $d$ sẽ xuất hiện một lần trong biểu thức của $\sigma(k)$ .

Như đã lập luận ở phần trước, trong đoạn từ $1$ đến $n$ có đúng $\left[ \frac{n}{d} \right]$ bội số của $d$ . Mỗi lần xuất hiện, ước này đóng góp một giá trị bằng $d$ vào tổng chung. Do đó, tổng giá trị đóng góp của riêng số $d$ đối với toàn bộ hệ thống là $d \cdot \left[ \frac{n}{d} \right]$ .

Lấy tổng tất cả các đóng góp này khi $d$ chạy từ $1$ đến $n$ , ta nhận được

$\displaystyle \sum_{k=1}^n \sigma(k) = \sum_{d=1}^n d \cdot \left[ \frac{n}{d} \right].$

Một lần nữa, thay đổi tên biến chạy $d$ thành $k$ , ta lập tức có được đẳng thức thứ hai. $\Box$

An Upper Bound for the Divisor Function (2)

Bài viết hôm nay sẽ đề cập đến một kết quả quan trọng trong lý thuyết số giải tích, liên quan đến tốc độ tăng của hàm số các ước $\tau(n)$ . Chúng ta sẽ cùng xem xét và chứng minh định lý sau:

Định lý. Với mọi số thực dương $\epsilon$ , tồn tại một hằng số dương $C_{\epsilon}$ sao cho $\tau(n) \le C_{\epsilon} \cdot n^{\epsilon}$ với mọi số nguyên dương $n$ .

Chứng minh. Giả sử $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ là phân tích tiêu chuẩn của $n$ ra các thừa số nguyên tố, với $p_i$ là số nguyên tố và $a_i$ là các số nguyên dương. Ta cần tìm chặn trên cho tỉ số:

$\displaystyle\frac{\tau(n)}{n^{\epsilon}} = \prod_{i=1}^k \frac{a_i+1}{p_i^{a_i\epsilon}}.$

Xét hàm số $f(p, a) = \frac{a+1}{p^{a\epsilon}}$ với $p$ là số nguyên tố và $a \ge 1$ . Ta sẽ chia các số nguyên tố $p$ thành hai nhóm để đánh giá, dựa vào hằng số $\epsilon$ .

Nhóm 1: Các số nguyên tố $p \ge 2^{1/\epsilon}$

Điều kiện này tương đương với $p^\epsilon \ge 2$ . Với mọi số nguyên dương $a \ge 1$ , ta có $\displaystyle p^{a\epsilon}\ge 2^a$ . Vì ta luôn có $2^a \ge a+1$ với mọi $a \in \mathbb{Z}^+$ nên với các số nguyên tố thuộc nhóm này thì

$\displaystyle f(p, a) = \frac{a+1}{p^{a\epsilon}} \le \frac{a+1}{2^a} \le 1.$

Nhóm 2: Các số nguyên tố $p < 2^{1/\epsilon}$

Với một $\epsilon > 0$ cố định, chỉ có hữu hạn các số nguyên tố thỏa mãn $p < 2^{1/\epsilon}$ . Cố định một số nguyên tố $p$ thuộc nhóm này, xét giới hạn của $f(p, a)$ khi $a \to \infty$ . Vì $p^\epsilon > 1$ nên $\displaystyle\lim_{a \to +\infty} \frac{a+1}{p^{a\epsilon}} = 0.$

Vì dãy số hội tụ về $0$ , giá trị của $f(p, a)$ sẽ bị chặn trên. Tức là tồn tại một giá trị lớn nhất cho $\frac{a+1}{p^{a\epsilon}}$ khi $a$ chạy trên tập số nguyên dương. Bây giờ ta chọn:

$\displaystyle C_{\epsilon} = \prod_{p < 2^{1/\epsilon}} \max\left(1, \sup_{a \ge 1} \frac{a+1}{p^{a\epsilon}}\right).$

Quay lại tỉ số ban đầu, ta tách tích các thừa số nguyên tố của $n$ ra thành hai phần tương ứng với hai nhóm trên:

$\displaystyle \frac{\tau(n)}{n^{\epsilon}} = \left( \prod_{p_i < 2^{1/\epsilon}} \frac{a_i+1}{p_i^{a_i\epsilon}} \right) \cdot \left( \prod_{p_i \ge 2^{1/\epsilon}} \frac{a_i+1}{p_i^{a_i\epsilon}} \right).$

Áp dụng các bất đẳng thức đã thiết lập ta có $\tau(n) \le C_{\epsilon} \cdot n^{\epsilon}$ với mọi số nguyên dương $n$ . $\Box$

The Parity of Divisor Functions

Bổ đề. Xét một số nguyên dương $n$ . Khi đó
(1) $\tau(n)$ là số lẻ khi và chỉ khi $n$ là một số chính phương.
(2) $\sigma(n)$ là số lẻ khi và chỉ khi $n$ hoặc $n/2$ là số chính phương.

Chứng minh. Giả sử phân tích tiêu chuẩn ra thừa số nguyên tố của số nguyên dương $n$ là:

$n = 2^{\alpha} \cdot p_1^{\alpha_1} \cdot p_2^{\alpha_2} \dots p_k^{\alpha_k}$ .

trong đó $p_1, p_2, \dots, p_k$ là các số nguyên tố lẻ phân biệt, và $\alpha, \alpha_1, \alpha_2, \dots, \alpha_k$ là các số tự nhiên (các số mũ này có thể bằng $0$ nếu thừa số đó không xuất hiện trong $n$ ).

(1) Số lượng các ước dương của $n$ được tính bởi:

$\tau(n) = (\alpha + 1)(\alpha_1 + 1)(\alpha_2 + 1) \dots (\alpha_k + 1)$ .

Một tích các số nguyên là số lẻ khi và chỉ khi tất cả các nhân tử trong tích đều là số lẻ. Do đó, $\tau(n)$ là số lẻ tương đương với việc $\alpha + 1$ và $\alpha_i + 1$ (với mọi $i = 1, \dots, k$ ) đều là các số lẻ.

Điều này xảy ra khi và chỉ khi $\alpha$ và tất cả các $\alpha_i$ đều là số chẵn. Khi các số mũ trong phân tích thừa số nguyên tố đều chẵn, $n$ chính là bình phương của một số nguyên dương. Vậy $\tau(n)$ là số lẻ khi và chỉ khi $n$ là một số chính phương.

(2) Tổng các ước dương của $n$ được tính bởi:

$\sigma(n) = (1 + 2 + 2^2 + \dots + 2^{\alpha}) \prod_{i=1}^k (1 + p_i + p_i^2 + \dots + p_i^{\alpha_i})$ .

Để $\sigma(n)$ là số lẻ, điều kiện cần và đủ là mỗi nhân tử trong tích trên đều là số lẻ.

Đầu tiên ta xét nhân tử $S_0 = 1 + 2 + 2^2 + \dots + 2^{\alpha}$ . Nếu $\alpha = 0$ thì $S_0 = 1$ (là số lẻ). Nếu $\alpha \ge 1$ thì $S_0 = 1 + 2(1 + 2 + \dots + 2^{\alpha-1})$ , luôn là một số lẻ bất chấp tính chẵn lẻ của $\alpha$ . Do đó, số mũ $\alpha$ không bị ràng buộc điều kiện để tổng này lẻ.

Bây giờ xét nhân tử ứng với các số nguyên tố lẻ $p_i$ ( $i = 1, 2, \dots, k$ ):

$S_i = 1 + p_i + p_i^2 + \dots + p_i^{\alpha_i}$ .

Tổng $S_i$ bao gồm $\alpha_i + 1$ số hạng. Vì $p_i$ là số lẻ nên lũy thừa $p_i^j$ luôn là số lẻ với mọi $j$ . Một tổng gồm các số lẻ sẽ nhận giá trị lẻ khi và chỉ khi số lượng các số hạng tham gia vào tổng là một số lẻ.
Suy ra $\alpha_i + 1$ phải là số lẻ, tương đương với $\alpha_i$ phải là số chẵn với mọi $i = 1, 2, \dots, k$ .

Từ đó, ta có thể viết lại $n$ dưới dạng $n = 2^{\alpha} \cdot \left(p_1^{\frac{\alpha_1}{2}} p_2^{\frac{\alpha_2}{2}} \dots p_k^{\frac{\alpha_k}{2}}\right)^2 = 2^{\alpha} \cdot M^2$ , trong đó $M$ là một số nguyên dương lẻ.