The Chinese Remainder Theorem and Its Generalization

Định lý (Định lý phần dư Trung Hoa). Cho các số nguyên dương $r$ ; $n_1$ , $n_2$ , $\ldots$ , $n_r$ thỏa mãn $(n_i,n_j)=1$ với mọi chỉ số khác nhau $i$ và $j$ . Khi đó hệ phương trình đồng dư

$\displaystyle x\equiv a_1\pmod{n_1},x\equiv a_2\pmod{n_2},\ldots,x\equiv a_r\pmod{n_r}$

có nghiệm duy nhất modulo $\prod n_i$ với mỗi $r$ số nguyên $a_1$ , $a_2$ , $\ldots$ , $a_r$ .

Chúng tôi giới thiệu hai chứng minh của định lí này.

Chứng minh thứ nhất. Phần duy nhất là đơn giản, sau đây ta chứng minh phần tồn tại. Với mỗi $i$ , tồn tại số nguyên $k_i$ để

$\displaystyle x_i:=k_i\prod _{j\not =i}n_j\equiv 1\pmod{n_i}.$

Ta thấy $x=\sum a_ix_i$ là một nghiệm của hệ. $\blacksquare$

Chứng minh thứ hai. Đặt $N=\prod n_i$ . Dễ thấy ánh xạ

$\displaystyle x \pmod N\mapsto (x\pmod{n_1}, x\pmod{n_2}, \ldots, x\pmod{n_r})$

là một song ánh từ tập các lớp $\pmod N$ đến bộ các lớp $\pmod{n_i}$ . $\blacksquare$

Hệ quả. Cho các số nguyên dương $r$ ; $n_1$ , $n_2$ , $\ldots$ , $n_r$ và các số nguyên $a_1,$ $a_2,$ $\ldots,$ $a_r$ . Khi đó hệ phương trình đồng dư

$\displaystyle x\equiv a_1\pmod{n_1},x\equiv a_2\pmod{n_2},\ldots,x\equiv a_r\pmod{n_r}$

có nghiệm khi và chỉ khi $(n_i,n_j)\mid a_i-a_j$ với mọi cách chọn hai chỉ số phân biệt $i$ và $j$ .

Chứng minh. Điều kiện cần là hiển nhiên, ta chứng minh $(n_i,n_j)\mid a_i-a_j$ với mọi $i < j$ là điều kiện đủ để hệ có nghiệm.

Nếu $\prod n_i=1$ thì khẳng định đúng, nếu không, gọi $p_1,p_2,\ldots,p_k$ là các ước nguyên tố của $\prod n_i$ . Với mỗi $i$ , gọi $j(i)$ là chỉ số thỏa mãn

$\displaystyle s_i:=v_{p_i}(n_{j(i)})=\max (v_{p_i}(n_1),v_{p_i}(n_2),\ldots,v_{p_i}(n_r)).$

Theo định lý phần dư Trung Hoa, tồn tại số nguyên $x$ sao cho

$\displaystyle x\equiv a_{j(i)}\pmod{p_i^{s_i}}$

với mọi $i$ . Dễ thấy $x$ là nghiệm của hệ phương trình đồng dư đã cho. $\blacksquare$

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$

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ẻ.