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 để

$\displaystyle\sum_{n=1}^r\frac{1}{1+nQ}\leq\sum_{t=1}^{K}S_{k+1}^t<1.$

Điều này không thể xảy ra do chuỗi $\displaystyle \sum_{n=1}^{+\infty}\frac{1}{1+nQ}$ là một chuỗi phân kỳ. $\Box$

Tham khảo

[1] https://nttuan.org/2018/12/30/series/

[2] https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes

Z – K[x]

Các bạn học sinh chắc rất quen thuộc với cuốn từ điển ANH – VIỆT đúng không? Hôm nay tôi sẽ giới thiệu vài trang trong cuốn từ điển SỐ NGUYÊN – ĐA THỨC. Để theo bài cho dễ dàng các bạn nên đọc lướt qua các bài sau:

[1] https://nttuan.org/2023/06/30/poly01/

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

[3] https://nttuan.org/2023/08/04/prime/

Mục đích của bài này là giới thiệu một số kết quả về đa thức tương tự với các kết quả trong số học sơ cấp (xem [2] và [3]), chẳng hạn như thuật toán chia, thuật toán Euclid, và định lí cơ bản của số học. Bởi vì chúng thực sự rất tương tự nên một số chứng minh sẽ bị bỏ qua, hoặc viết vắn tắt. Các em học sinh nên viết lại cẩn thận tất cả các chứng minh để hiểu thêm về đa thức.

Trong bài $K$ là $\mathbb{C},\mathbb{R},\mathbb{Q},$ hay $\mathbb{F}_p$ .

Định lí 1 (Thuật toán chia). Cho $f$ và $g$ là các phần tử của $K[x]$ với $g\neq 0$ . Khi đó tồn tại duy nhất cặp phần tử $(q,r)$ của $K[x]$ thỏa mãn $f=q g+r,$ và $\deg (r)<\deg(g)$ hoặc $r=0$ .

Chứng minh. Khẳng định là đúng một cách hiển nhiên nếu $f=0$ hoặc bậc của $f$ bé hơn bậc của $g.$ Bây giờ ta xét trường hợp còn lại và chứng minh nó bằng quy nạp theo bậc của $f$ .

Nếu bậc của $f$ bằng $0$ thì bậc của $g$ bằng $0$ và khẳng định là đúng. Giả sử khẳng định đúng với mọi đa thức $f$ có bậc bé hơn $m$ . Xét một đa thức $f$ có bậc $m$ và một đa thức $g$ khác không có bậc $n\leq m$ . Viết $f(x)=a_m x^m+\ldots+a_1 x+a_0$ và $g(x)=b_n x^n+\ldots+b_0.$

Xét đa thức $f_1(x)=f(x)-a_m b_n^{-1} x^{m-n} g(x).$ Ta có $f_1$ có bậc bé hơn $m$ hoặc $f_1=0$ nên theo giả thiết quy nạp, ta có thể viết $f_1=q_1 g+r,$ trong đó bậc của $r$ bé hơn $n$ hoặc $r=0$ . Từ đây ta có $f(x)=\left(q_1(x)+a_m b_n^{-1} x^{m-n}\right) g(x)+r(x).$ Bây giờ ta đi chứng minh phần còn lại, thương và dư là duy nhất. Giả sử $f=q_1 g+r_1$ và $f=q_2 g+r_2.$ Khi đó $\left(q_1-q_2\right) g=r_2-r_1.$ Nếu $q_2-q_1 \neq 0$ thì bậc của $\left(q_2-q_1)\right) g$ không bé hơn bậc của $g$ , trong khi bậc của $r_2-r_1$ bé hơn bậc của $g$ , vô lý. Vậy $q_1=q_2$ , và đương nhiên $r_1=r_2$ . $\Box$

Định nghĩa 1. Cho hai đa thức không đồng thời bằng không $f$ và $g$ với hệ số trong $K$ . Một đa thức monic $d$ với hệ số trong $K$ được gọi là ước chung lớn nhất của $f$ và $g$ nếu

(1) $d$ là một ước của $f$ và $g$ , và

(2) mỗi ước của $f$ và $g$ cũng là một ước của $d$ .

Ước chung lớn nhất của $f$ và $g$ được ký hiệu bởi $(f, g)$ . Nếu $(f, g)=1$ thì ta nói $f$ và $g$ nguyên tố cùng nhau.

Ước chung lớn nhất nếu có sẽ là duy nhất. Thật vậy, giả sử $d$ và $d_1$ cùng là ước chung lớn nhất của $f$ và $g$ . Khi đó $d \mid d_1$ và $d_1 \mid d$ , suy ra $d=a d_1$ và $d_1=b d$ , do đó $d=a b d.$ Từ đây ta có $ab=1$ , suy ra $a$ và $b$ đều có bậc không. Do đó $d_1$ bằng $d$ nhân với một đa thức hằng, nhưng chúng cùng monic nên $d=d_1$ . Định lí sau chứng tỏ ước chung lớn nhất tồn tại.

Định lí 2. Với các đa thức không đồng thời bằng không $f, g \in K[x]$ , ước chung lớn nhất tồn tại và có thể biểu diễn dưới dạng $(f, g)=a f+b g,$ với $a,b \in K[x]$ .

Chứng minh. Xét tập hợp $I=\{a f+b g \mid a, b \in K[x]\}.$ Tập hợp $I$ chứa ít nhất một đa thức khác không nên tồn tại đa thức monic $d$ thuộc $I$ mà có bậc nhỏ nhất. Dễ chứng minh được $d=(f, g)$ . $\Box$

Thuật toán Euclid. Cho $f, g \in K[x]$ là hai đa thức khác không. Dùng thuật toán chia ta có $f=q g+r,$ trong đó $\deg(r)<\deg(g)$ hoặc $r=0$ . Nếu $r=0$ thì $g$ chia hết $f$ , do đó $(f, g)=c g$ với $c\in K$ . Nếu không, ta có tập các ước chung của $f$ và $g$ bằng tập các ước chung của $g$ và $r$ , do đó $(f,g)=(g,r)$ . Quy trình này làm giảm bậc của đa thức nên nó phải kết thức sau hữu hạn bước, lúc đó ta tìm được $(f,g)$ . Tương tự như với số nguyên, dùng thuật toán này ta có thể tìm được các đa thức $a$ và $b$ sao cho $(f, g)=a f+b g.$

Định lí 3. Cho $f, g,h \in K[x]$ với $(h, f)=1$ và $h\mid fg$ . Khi đó $h\mid g$ .

Chứng minh. Bạn đọc tự chứng minh xem như bài tập. $\Box$

Định nghĩa 2. Một đa thức khác hằng với hệ số trong $K$ được gọi là bất khả quy trên $K$ nếu nó không thể phân tích trong $K[x]$ thành tích của hai đa thức có bậc nhỏ hơn. Nó được gọi là khả quy trên $K$ nếu có phân tích như vậy.

Ví dụ. Đa thức $x^2-x+1$ bất khả quy trên $\mathbb{R}$ nhưng khả quy trên $\mathbb{C}$ .

Tất cả những đa thức bậc $1$ là bất khả quy trên $K$ . Mỗi đa thức có bậc lớn hơn $1$ có nghiệm trong $K$ sẽ khả quy trên $K$ . Ngược lại không đúng, một đa thức khả quy vẫn có thể không có nghiệm trong $K$ . Tuy nhiên, với các đa thức bậc $2$ hay $3$ ta có kết quả sau:

Định lí 4. Một đa thức có bậc $2$ hay $3$ bất khả quy trên $K$ khi và chỉ khi nó không có nghiệm trong $K$ .

Tương tự như với số nguyên ta có các định lí sau. Bạn đọc tự chứng minh chúng xem như bài tập.

Định lí 5. Đa thức khác hằng $p \in K[x]$ bất khả quy trên $K$ khi và chỉ khi với mỗi $f,g \in K[x],$ $p\mid fg$ kéo theo $p \mid f$ hoặc $p \mid g$ .

Định lí 6. Mỗi đa thức khác hằng với hệ số trong $K$ có thể viết như là một phần tử của $K$ nhân với tích của các đa thức monic bất khả quy trên $K$ . Nếu không kể đến thứ tự của các nhân tử thì biểu diễn này là duy nhất.

Continue reading →

Perfect rulers

Giả sử ta có một cái thước kẻ dài $\displaystyle 6$ , trên đó đã đánh dấu các điểm $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 2$ , $\displaystyle 3$ , $\displaystyle 4$ , $\displaystyle 5$ , $\displaystyle 6$ . Sử dụng chiếc thước này ta có thể tạo mọi đoạn có độ dài thuộc $\displaystyle [6]$ , nhưng ta không cần đánh dấu trên thước nhiều điểm như thế để đạt được điều này. Ta có thể đánh dấu $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 4$ , $6$ là đủ (đoạn độ dài $2$ được đo giữa hai điểm $4$ và $6$ , đoạn độ dài $3$ được đo giữa $1$ và $4$ , đoạn độ dài $4$ được đo giữa $0$ và $4$ , đoạn độ dài $5$ được đo giữa $1$ và $6$ ). Vì $C_4^2=6$ nên hoàn cảnh này là hoàn hảo.

Bài toán. Cho một số nguyên $n$ lớn hơn $4$ . Chứng minh rằng không tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Lời giải. Giả sử ngược lại, tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Xét đa thức $\displaystyle A(z) = \sum_i z^{a_i}$ . Theo tính chất của các số $a_1$ , $a_2$ , $\ldots$ , $a_n$ , ta có

$\displaystyle A(z) \cdot A\left(\frac{1}{z}\right)=\sum_{k=-C_n^2}^{C_n^2} z^k+n-1,\quad \forall z\in\mathbb{C}\setminus \{0\}.$

Continue reading →

Pell’s equation

Trong bài này chúng tôi sẽ giới thiệu một số định lí của Dirichlet về xấp xỉ số thực bởi số hữu tỉ, và áp dụng các định lí đó vào lý thuyết phương trình Pell.

Định lí 1 (Dirichlet). Cho số thực $\theta$ và số nguyên dương $Q$ . Khi đó có số nguyên dương $q$ và số nguyên $a$ thỏa mãn $q\leq Q$ và $\displaystyle \left|\theta-\frac{a}{q}\right|\leq\dfrac{1}{q(Q+1)}.$

Chứng minh. Phân hoạch nửa đoạn $[0;1)$ thành $Q+1$ nửa đoạn

$\displaystyle I_k=\left[\frac{k}{Q+1};\frac{k+1}{Q+1}\right),\quad k=0,1,\ldots,Q.$

Xét $Q$ số $\{1.\theta\},\{2.\theta\},\ldots,\{Q.\theta\}$ .

Nếu $I_0$ chứa ít nhất một số trong dãy trên, chẳng hạn $\{m.\theta\}$ , ta chọn $q=m$ . Nếu $I_{Q}$ chứa ít nhất một số trong dãy trên, chẳng hạn $\{n.\theta\}$ , ta chỉ cần chọn $q=n$ . Nếu hai khoảng trên không chứa số nào thì tồn tại một khoảng $I_i$ chứa ít nhất hai số $\{j.\theta\},$ $\{k.\theta\}$ $(j<k)$ trong dãy, ta chọn $q=k-j$ . $\Box$

Như vậy mọi số thực có thể được xấp xỉ bởi một số hữu tỉ có mẫu bị chặn với độ chính xác phụ thuộc vào chặn trên của mẫu. Sau đây là một áp dụng đẹp đẽ của định lí trên:

Hệ quả. Mọi số nguyên tố dạng $4k+1$ có thể viết thành tổng của hai số chính phương.

Chứng minh. Theo định lí Wilson, tồn tại số nguyên dương $c$ sao cho $c^2+1\equiv 0\pmod{p}.$ Theo định lí Dirichlet, tồn tại các số nguyên $a,b$ sao cho $1\leq b\leq [\sqrt{p}]$ và

$\displaystyle \left|\frac{c}{p}-\frac{a}{b}\right|\leq\frac{1}{b([\sqrt{p}]+1)}<\frac{1}{b\sqrt{p}}. \quad (*)$

Từ $(*)$ ta có $|cb-ap|<\sqrt{p}$ , suy ra $0<(cb-ap)^2+b^2<2p$ , mà $(cb-ap)^2+b^2\equiv b^2(c^2+1)\equiv 0\pmod{p},$ suy ra $(cb-ap)^2+b^2=p.$ $\Box$

Định lí 2 (Dirichlet). Cho số vô tỷ $\alpha$ . Khi đó có vô hạn số hữu tỷ $\displaystyle\frac{a}{q}$ sao cho $q>0$ và $\displaystyle \left|\alpha-\frac{a}{q}\right|<\frac{1}{q^2}.$ Hơn nữa ta có thể chọn $q$ lớn tùy ý.

Chứng minh. Ta sẽ xây dựng dãy hữu tỷ thỏa mãn bằng quy nạp.

Với số nguyên $Q\geq 1$ bất kỳ, theo định lí 1, tồn tại phân số $\displaystyle\frac{a}{q}$ sao cho $1\leq q\leq Q$ và

$\displaystyle \left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q(Q+1)}.$

Bằng cách thu gọn $\displaystyle\frac{a}{q}$ nếu cần, ta có thể xem phân số này tối giản. Do $Q+1>q$ nên từ bất đẳng thức trên ta có

$\displaystyle \left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q(Q+1)}<\frac{1}{q^2}.$

Giả sử ta đã xây dựng được dãy các phân số tối giản đôi một khác nhau $\displaystyle\frac{a_1}{q_1},\frac{a_2}{q_2},\ldots,\frac{a_m}{q_m}$ thỏa mãn bất đẳng thức trong định lí. Vì $\alpha$ là số vô tỷ nên $|\alpha-a_i/q_i|>0\,\forall i$ , bởi thế nên ta có thể chọn được số nguyên dương $Q$ để $Q>\max \{|\alpha-a_i/q_i|^{-1}\}.$ Dùng định lí 1 cho số $Q$ này ta tìm được phân số tối giản $\displaystyle\frac{a_{m+1}}{q_{m+1}}$ sao cho $1\leq q_{m+1}\leq Q$ và