Day: August 11, 2010

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