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

Algebra, Number theory 3 Minutes

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

Unknown's avatar

Published by Nguyen Trung-Tuan

A math teacher.

Published

Leave a comment