The number of prime factors of a natural number

Mỗi năm, khi được mời dạy cho đội tuyển Việt Nam tham dự Olympic Toán quốc tế (IMO), tôi thường mang đến cho các em vài bài toán rất khó, và hy vọng một lời giải thanh nhã từ các thành viên của đội tuyển. Dưới đây là một bài cho đội tuyển IMO năm 2021.

Bài toán. Với mỗi số nguyên dương $n,$ gọi $\omega (n)$ là số ước nguyên tố của $n$ . Chứng minh rằng tồn tại số nguyên dương $n$ sao cho $\omega (n+1)<\omega (n+2)<\ldots <\omega (n+100).$

Lời giải. Với hai hàm $f(x)$ và $g(x)$ từ tập các số nguyên dương đến tập các số thực dương ta viết $f=o(g)$ nếu $f/g\to 0$ khi $x\to\infty$ . Thay $100$ bởi $k > 2$ . Gọi $A$ là một số nguyên dương phụ thuộc $k$ mà ta sẽ chọn sau. Giả sử $q_1<q_2<\cdots<q_m<\cdots$ là dãy tất cả các số nguyên tố lớn hơn $k$ . Với $j=1, \ldots, k$ , đặt $T_j=$ $j(j-1) / 2$ và $\displaystyle M_j=\prod_{\ell=T_j A+1}^{T_{j+1} A} q_{\ell}.$ Đặt $\displaystyle M=\prod_{j=1}^k M_j$ và gọi $N$ là số nguyên dương nhỏ nhất sao cho $M_j$ chia hết $N+j$ với mỗi $j\in [k]$ . Ta có ngay $N+k<M$ . Thật vậy, nếu không thì $N=M-i$ với $i \in [k]$ , lấy $j \in [k]\setminus \{i\}$ , ta có $M_j \mid N+j=M+(j-i)$ ; suy ra $M_j \mid j-i$ , vô lý.

Xét số $n=M \lambda+N$ , ở đây $\lambda$ là số nguyên dương mà $\lambda \in[M, 2 M]$ . Ta có

$\displaystyle n+j=M \lambda+(N+j)=M_j\left(\left(M / M_j\right) \lambda+(N+j) / M_j\right), \quad j=1, \ldots, k .$

Khi đặt $A_j=(N+j) / M_j$ và $B_j=M / M_j$ , ta có

$\displaystyle j A=T_{j+1} A-T_j A=\omega\left(M_j\right) \leq \omega(n+j) \leq j A+\omega\left(B_j \lambda+A_j\right),$

suy ra nếu $\lambda$ thỏa mãn $\displaystyle \omega\left(B_j \lambda+A_j\right)<A, \quad \forall j=1, \ldots, k-1,\quad (1)$ thì

$\displaystyle jA \leq\omega(n+j)<j A+A \leq \omega(n+j+1), \quad\forall j=1, \ldots, k-1,$

và bài toán được giải. Vậy sẽ là đủ nếu ta chỉ ra có $A$ để tồn tại $\lambda$ thỏa mãn $(1)$ .

Với mỗi $j<k$ , ta có $(A_j,B_j)=1$ . Thật vậy, xét một chỉ số $j<k$ . Ta có

$\displaystyle B_j=M / M_j=\prod_{\substack{1 \leq \ell \leq k \\ \ell \neq j}} M_{\ell}.$

Nếu có số nguyên tố $p \mid\left(A_j, B_j\right)$ , tồn tại chỉ số $\ell \neq j$ sao cho $p \mid M_{\ell}$ . Vì $M_{\ell} \mid N+\ell$ nên $p \mid N+\ell$ . Nhưng $p\left|A_j\right| N+j$ ; suy ra $p \mid(N+\ell)-(N+j)=(\ell-j)$ , và $1 \leq|\ell-j|<k$ . Do đó $p<k$ , điều này không thể xảy ra do mọi ước nguyên tố của $M$ lớn hơn $k$ .

Bổ đề. Với mỗi số nguyên dương $x$ , ký hiệu $\tau (x)$ là số ước dương của $x$ . Khi đó

$\displaystyle \sum_{\lambda \in[M, 2 M]} \tau\left(B_j \lambda+A_j\right)\leq 4 M(\ln M+1),\quad\forall j<k.$

Chứng minh. Xét một chỉ số $j<k$ . Vì $N+k <M$ nên với mỗi số nguyên $\lambda\in [M,2M]$ , ta có

$\displaystyle B_j \lambda+A_j \leq \frac{1}{M_j}(M \lambda+N+k)<\frac{2 M \lambda}{M_j} \leq \frac{4 M^2}{M_j}<M^2,$

suy ra

$\displaystyle \tau\left(B_j \lambda+A_j\right) \leq 2 \sum_{\substack{d \mid B_j \lambda+A_j \\ d \leq M}} 1.$

Do đó

$\displaystyle \sum_{\lambda \in[M, 2 M]} \tau\left(B_j \lambda+A_j\right)$

$\displaystyle \leq 2 \sum_{\lambda \in[M, 2 M]} \sum_{\substack{d \mid B_j \lambda+A_j \\ d \leq M}} 1 = 2 \sum_{d \leq M} \sum_{\substack{\lambda \in[M, 2 M] \\ B_j \lambda+A_j \equiv 0 \\ (\bmod d)}} 1$

$\leq 2 \sum_{d \leq M}\left(\left\lfloor\left.\frac{M}{d} \right\rvert\,+1\right) \leq 4 M \sum_{d \leq M} \frac{1}{d}\right. \leq 4 M(\ln M+1) .$ $\Box$

Continue reading →

The fundamental theorem of arithmetic

Trong bài này chúng ta sẽ nói một ít về số nguyên tố, trình bày chứng minh định lí cơ bản của số học, và giới thiệu một số kết quả sơ cấp về số nguyên tố. Đây cũng là bài đọc cho các học sinh lớp 9 và các học sinh ôn thi chọn HSG QG tại T’s Lab. Để theo dõi cho dễ dàng bạn đọc nên xem lại bài viết sau:

[1] https://nttuan.org/2023/07/14/divisibility/

Một số nguyên tố là một số nguyên $n$ lớn hơn $1$ có đúng hai ước dương là $1$ và $n$ . Một số nguyên lớn hơn $1$ được gọi là hợp số nếu nó không phải là số nguyên tố. Các số $2,3,$ và $5$ là các số nguyên tố. Các số $4,15,$ và $18$ là các hợp số.

Định lí 1. Mỗi số nguyên lớn hơn $1$ có thể biểu diễn như là tích của các số nguyên tố.
Chứng minh. Giả sử $n$ là một số nguyên lớn hơn $1$ . Nếu $n$ là số nguyên tố thì nó là tích với một thừa số nguyên tố. Nếu không thì $n=n_1 n_2$ , trong đó $n_1$ và $n_2$ là các số nguyên lớn hơn $1$ và bé hơn $n$ . Nếu $n_1$ là một số nguyên tố, ta không làm gì; nếu không thì viết $n_1$ thành tích của hai số nguyên lớn hơn $1$ và bé hơn $n_1$ ; thao tác tương tự với $n_2$ . Tiếp tục thao tác như thế trên các thừa số mới. Quá trình này phải dừng vì không có dãy giảm nghiêm ngặt gồm vô hạn số nguyên dương, khi đó ta có một cách biểu diễn $n$ như là tích của các số nguyên tố. $\Box$

Từ dịnh lí trên, vì các thừa số nguyên tố không nhất thiết phải phân biệt nên mọi số nguyên $n$ lớn hơn $1$ có thể viết được dưới dạng $n=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r},$
trong đó $p_1, p_2, \cdots, p_r$ là các số nguyên tố phân biệt và $\alpha_1, \alpha_2, \cdots, \alpha_r$ là các số nguyên dương. Biểu diễn này được gọi là phân tích chính tắc của $n$ thành các lũy thừa nguyên tố. Ta sẽ chứng minh rằng biểu diễn này là duy nhất theo nghĩa: đối với mỗi $n$ , bất kỳ biểu diễn nào khác chỉ là sự sắp xếp lại các thừa số.

Continue reading →

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 sum of the reciprocals of the primes

Với mỗi số nguyên dương $n$ , ký hiệu $p_n$ là số nguyên tố thứ $n$ trong dãy tăng tất cả các số nguyên tố. Như vậy $p_1=2$ , $p_2=3$ , $p_3=5$ ,…

Trong bài này chúng tôi sẽ giới thiệu một chứng minh của kết quả sau:

Định lý. Chuỗi $\displaystyle \frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}+\ldots$ là một chuỗi phân kỳ.

Chứng minh. Giả sử ngược lại, khi đó với mỗi số nguyên dương $k$ , chuỗi $\displaystyle\sum_{m=k}^{+\infty}\frac{1}{p_m}$ là một chuỗi hội tụ, gọi $S_k$ là tổng của nó. Vì $\lim S_k=0$ nên tồn tại số nguyên $k$ sao cho $\displaystyle S_{k+1}<\frac{1}{2}$ . Đặt $Q=p_1p_2\ldots p_k$ và xét các số $1+nQ\, (n=1,2,\ldots)$ . Mỗi số trong dãy này đều không có ước nguyên tố thuộc $\{p_1, p_2, \ldots, p_k\}$ , do đó với mỗi số nguyên dương $r$ , tồn tại số nguyên dương $K$ đủ lớn để