A Proof of the Lifting The Exponent Lemma


Định lý 1 (Bổ đề nâng số mũ). Cho hai số nguyên lẻ a,b và số nguyên dương n. Khi đó:

(1) nếu n là số lẻ thì \displaystyle v_2(a^n-b^n)=v_2(a-b).

(2) nếu n là số chẵn thì \displaystyle v_2(a^n-b^n)=v_2\left(\frac{a^2-b^2}{2}\right)+v_2(n).

Chứng minh. (1) đúng hiển nhiên. Bây giờ ta chứng minh (2).

Viết n=2^kx với k là số nguyên dương và x là số nguyên lẻ. Ta có:

a^n-b^n=(a^x-b^x)(a^x+b^x)(a^{2x}+b^{2x})\cdots (a^{2^{k-1}x}+b^{2^{k-1}x})

và trong các thừa số ở vế phải, trừ hai thừa số đầu, tất cả các thừa số còn lại đều chia cho 4 dư 2, suy ra:

v_2(a^n-b^n)=v_2(a^{2x}-b^{2x})+k-1=v_2(a^2-b^2)+v_2(n)-v_2(2).

Định lý được chứng minh. \Box

Định lý 2 (Bổ đề nâng số mũ). Cho số nguyên tố lẻ p và hai số nguyên a,b không chia hết cho p thỏa mãn p\mid a-b. Khi đó:

\forall n\in\mathbb{N}^*,\quad v_p\left(a^n-b^n\right)= v_p\left(a-b\right)+v_p(n).

Chứng minh. Với mỗi số nguyên tố lẻ p, cố định nó. Gọi S là tập tất cả các số nguyên dương n sao cho:

v_p\left(a^n-b^n\right)= v_p\left(a-b\right)+v_p(n)

với mọi a,b thỏa mãn các giả thiết của định lý. Ta cần chứng minh S=\mathbb{N}^*.

Khẳng định 1. 1\in S.

Chứng minh. Hiển nhiên. \Box

Khẳng định 2. Với mỗi hai số nguyên dương m và n, nếu m\in S và n\in S thì mn\in S.

Chứng minh. Với m,n\in S và a,b thỏa mãn các giả thiết của định lí, ta có:

\begin{aligned} v_p(a^{mn}-b^{mn}) &=v_p((a^m)^n-(b^m)^n)\\ &=v_p(a^m-b^m)+v_p(n)\\ &=v_p(a-b)+v_p(m)+v_p(n)\\ &=v_p(a-b)+v_p(mn), \end{aligned}

suy ra mn\in S. \Box

Khẳng định 3. Nếu q là một số nguyên tố thì q\in S.

Chứng minh. Cố định số nguyên tố q và hai số nguyên a, b thỏa mãn các điều kiện của định lý. Xét hai trường hợp:

Trường hợp 1. q\not=p.

Ta có a^q-b^q=(a-b)(a^{q-1}+a^{q-2}b+\cdots+b^{q-1}) và thừa số thứ hai không chia hết cho p nên có ngay q\in S.

Trường hợp 2. q=p.

Viết a=b+p^kc với k\in\mathbb{N}^* và c là số nguyên không chia hết cho p. Theo định lí nhị thức, ta có:

a^p-b^p=p^{k+1}b^{p-1}c+C_p^2b^{p-2}p^{2k}c^2+\cdots+p^{kp}c^p.

Vì p là số nguyên tố lẻ và k\in\mathbb{N}^* nên trong tổng trên, trừ số hạng đầu, tất cả các số hạng còn lại đều chia hết cho p^{k+2}, suy ra:

v_p(a^p-b^p)=v_p(p^{k+1}b^{p-1}c)=k+1=v_p(a-b)+v_p(p),

hay q=p\in S. \Box

Từ ba khẳng định ta có S=\mathbb{N}^*. \Box

Nhận xét. Nếu p là số nguyên tố lẻ thỏa mãn a \equiv -b \not\equiv 0 \pmod p và n là số lẻ thì:

v_p(a^n + b^n) = v_p(a + b) + v_p(n).

A Proof of Beatty’s Theorem


Cho số thực \alpha. Dãy Beatty của \alpha là dãy (a_n)_{n\geq 1} xác định bởi a_n=[n\alpha],\quad \forall n\geq 1.

Định lý (Beatty). Cho hai số thực dương \alpha và \beta. Khi đó các dãy Beatty của \alpha và \beta làm thành một phân hoạch của tập các số nguyên dương khi và chỉ khi \alpha và \beta là các số vô tỷ và

\displaystyle \frac{1}{\alpha}+\frac{1}{\beta}=1.

Chứng minh. Đặt S_{\alpha}=\{[n\alpha]|n=1,2,\ldots\} và \displaystyle S_{\beta}=\{[n\beta]|n=1,2,\ldots\}.

Giả sử S_{\alpha} và S_{\beta} làm thành một phân hoạch của tập các số nguyên dương. Ta thấy ngay \alpha và \beta lớn hơn 1, suy ra hai dãy Beatty của hai số này là các dãy tăng. Ta sẽ sử dụng phương pháp mật độ trong lý thuyết số giải tích.

Với mỗi số nguyên dương k, cố định nó. Xét một số nguyên dương n, ta có

\displaystyle [n\alpha]\leq k\Leftrightarrow n\alpha < k+1\Leftrightarrow n < \dfrac{k+1}{\alpha}.

Suy ra |S_{\alpha}\cap \{1, 2, \ldots, k\}|=\left[\dfrac{k+1}{\alpha}\right] hoặc \left[\dfrac{k+1}{\alpha}\right]-1 tùy theo \dfrac{k+1}{\alpha} không nằm trong hay nằm trong \mathbb{Z}. Chứng minh tương tự ta có \displaystyle |S_{\beta}\cap \{1, 2, \ldots, k\}|=\left[\dfrac{k+1}{\beta}\right] hoặc \left[\dfrac{k+1}{\beta}\right]-1 tùy theo \dfrac{k+1}{\beta} không nằm trong hay nằm trong \mathbb{Z}.

Mà |S_{\alpha}\cap \{1, 2, \ldots, k\}|+|S_{\beta}\cap \{1, 2, \ldots, k\}|=k, suy ra

\displaystyle -2+\left[\dfrac{k+1}{\alpha}\right]+\left[\dfrac{k+1}{\beta}\right]\leq k\leq \left[\dfrac{k+1}{\alpha}\right]+\left[\dfrac{k+1}{\beta}\right].

Kết hợp với định nghĩa phần nguyên ta được

\displaystyle -4+\dfrac{k+1}{\alpha}+\dfrac{k+1}{\beta} < k\leq \dfrac{k+1}{\alpha}+\dfrac{k+1}{\beta}.

Chia các vế cho k và cho k\to+\infty ta có \dfrac{1}{\alpha}+\dfrac{1}{\beta}=1. Nếu \alpha là số hữu tỷ thì từ đẳng thức này ta có \beta cũng là số hữu tỷ. Viết \displaystyle \alpha=\dfrac{p}{q},\quad \beta=\dfrac{r}{s}, với p, q, r, và s là các số nguyên dương. Ta thấy S_{\alpha}\cap S_{\beta}\not=\emptyset, chẳng hạn pr thuộc cả hai tập này, suy ra vô lý. Bởi vậy \alpha là số vô tỷ, và \beta cũng thế.

Bây giờ giả sử ngược lại, \alpha và \beta là các số vô tỷ và \dfrac{1}{\alpha}+\dfrac{1}{\beta}=1. Ta thấy ngay \alpha và \beta lớn hơn 1, suy ra hai dãy Beatty của hai số này là các dãy tăng. Nếu S_{\alpha}\cap S_{\beta}\not=\emptyset thì tồn tại các số nguyên dương k,m và n sao cho k=[m\alpha]=[n\beta]. Suy ra

\displaystyle k\leq m\alpha < k+1,\quad k\leq n\beta < k+1.

Vì \alpha và \beta là các số vô tỷ nên

\displaystyle k < m\alpha < k+1,\quad k < n\beta < k+1,

suy ra

\displaystyle \frac{k}{\alpha} < m < \frac{k+1}{\alpha},\quad \frac{k}{\beta} < n < \frac{k+1}{\beta},

cộng theo vế ta có k < m+n < k+1, vô lý. Như vậy S_{\alpha}\cap S_{\beta}=\emptyset.

Nếu tồn tại số nguyên dương l sao cho l\not\in S_{\alpha}\cup S_{\beta} thì tồn tại các số nguyên không âm p và q sao cho

\displaystyle [p\alpha] < l < [(p+1)\alpha], \quad [q\beta] < l < [(q+1)\beta].

Vì l là số nguyên nên từ các bất đẳng thức trên ta suy ra p\alpha < l, đồng thời [(p+1)\alpha] \geq l+1 kéo theo (p+1)\alpha \geq l+1. Lập luận tương tự cho \beta, ta được

\displaystyle p\alpha < l < l+1\leq (p+1)\alpha,\quad q\beta < l < l+1\leq (q+1)\beta.

Vì \alpha,\beta là các số vô tỷ nên

\displaystyle p\alpha < l < l+1 < (p+1)\alpha,\quad q\beta < l < l+1 < (q+1)\beta.

Chia các vế cho \alpha,\beta và cộng lại ta có

\displaystyle p+q < l < l+1 < p+q+2,

điều này không thể xảy ra (do khoảng mở (p+q, p+q+2) có độ dài bằng 2 nên chỉ chứa đúng một số nguyên là p+q+1). \blacksquare

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