Farey sequence


Trong mục này tôi sẽ trình bày về phân số Farey và một số vấn đề liên quan.

Các phân số trong bài được xem là có mẫu dương.

1) Định nghĩa và một số tính chất

Định nghĩa 1. Cho số nguyên dương \displaystyle n. Phân số tối giản \displaystyle \dfrac{p}{q}\in [0;1] được gọi là phân số Farey bậc \displaystyle n nếu \displaystyle q\leq n. Dãy tăng tất cả các phân số Farey bậc \displaystyle n được gọi là dãy Farey bậc \displaystyle n,  ký hiệu là \displaystyle F_n.

Ví dụ 1.

\displaystyle F_1:\,\frac{0}{1};\frac{1}{1}.

\displaystyle F_2:\,\frac{0}{1};\frac{1}{2};\frac{1}{1}.

\displaystyle F_3:\,\frac{0}{1};\frac{1}{3};\frac{1}{2};\frac{2}{3};\frac{1}{1}.

\displaystyle F_4:\,\frac{0}{1};\frac{1}{4};\frac{1}{3};\frac{1}{2};\frac{2}{3};\frac{3}{4};\frac{1}{1}.

Ví dụ 2. Với mỗi số nguyên dương \displaystyle n, dãy \displaystyle F_n có đúng \displaystyle 1+\sum_{k=1}^n\varphi (k) số hạng.

Định lý 1. Cho các số tự nhiên \displaystyle a,b,c\displaystyle d thỏa mãn \displaystyle 0\leq \frac{a}{b}<\frac{c}{d}\leq 1\displaystyle bc-ad=1. Khi đó \displaystyle \frac{a}{b},\frac{c}{d} là hai số hạng liên tiếp của dãy \displaystyle F_n, ở đây \displaystyle n là số nguyên dương thỏa mãn \displaystyle \max\{b,d\}\leq n\leq b+d-1.

Chứng minh. Từ \displaystyle bc-ad=1 ta có \displaystyle \frac{a}{b},\frac{c}{d} là hai phân số tối giản, mà \displaystyle \max\{b,d\}\leq n, suy ra chúng là các số hạng của dãy \displaystyle F_n. Nếu chúng không phải là hai số hạng liên tiếp của \displaystyle F_n thì tồn tại phân số Farey bậc \displaystyle n, ký hiệu \displaystyle \dfrac{h}{k} thỏa mãn \displaystyle \displaystyle \frac{a}{b}<\frac{h}{k}<\frac{c}{d}.\displaystyle ck-dh\geq 1\displaystyle bh-ak\geq 1 nên

\displaystyle b+d-1\geq n\geq k=(bc-ad)k=b(ck-dh)+d(bh-ak)\geq b+d, đây là điều không thể xảy ra. Định lý được chứng minh. \Box

Với các số tự nhiên \displaystyle a,b,c\displaystyle d thỏa mãn \displaystyle 0\leq \frac{a}{b}<\frac{c}{d}, phân số \dfrac{a+c}{b+d} được gọi là phân số trung gian của hai phân số \displaystyle \dfrac{a}{b}\displaystyle \dfrac{c}{d}. Từ chứng minh trên ta có:

Định lý 2. Cho các số tự nhiên \displaystyle a,b,c\displaystyle d thỏa mãn \displaystyle 0\leq \frac{a}{b}<\frac{c}{d}\leq 1\displaystyle bc-ad=1. Khi đó nếu \displaystyle \dfrac{h}{k} là phân số trung gian của hai phân số \displaystyle \dfrac{a}{b}, \dfrac{c}{d} thì \displaystyle \frac{a}{b}<\frac{h}{k}<\frac{c}{d}\displaystyle bh-ak=1,\quad ck-dh=1.

Định lý 3. Với mọi số nguyên dương \displaystyle n ta có

1) Dãy \displaystyle F_{n+1} có được từ dãy \displaystyle F_n bằng cách viết vào giữa hai số hạng liên tiếp của \displaystyle F_n có tổng các mẫu không vượt quá \displaystyle n+1 phân số trung gian của chúng;

2) Nếu \displaystyle \dfrac{a}{b}<\dfrac{c}{d} là hai số hạng liên tiếp của \displaystyle F_n thì \displaystyle bc-ad=1.

Chứng minh. Ta sẽ chứng minh bằng quy nạp theo \displaystyle n.

Rõ ràng khẳng định đúng với $n=1$. Giả sử khẳng định đúng với các số nguyên dương bé hơn \displaystyle n\, (n\geq 2), ta sẽ chứng minh khẳng định đúng với \displaystyle n.

Từ định lý 2 và giả thiết quy nạp ta có nếu \displaystyle \dfrac{a}{b}<\dfrac{c}{d} là hai số hạng liên tiếp của \displaystyle F_n thì \displaystyle bc-ad=1.

Sau khi viết vào giữa hai số hạng liên tiếp của \displaystyle F_n có tổng các mẫu không vượt quá \displaystyle n+1 phân số trung gian của chúng ta thu được dãy con \displaystyle F'_n của \displaystyle F_{n+1}. Nếu trong \displaystyle F_{n+1} có phân số \displaystyle \dfrac{h}{k} không thuộc \displaystyle F'_n thì tồn tại hai số hạng liên tiếp \displaystyle \dfrac{a}{b}<\dfrac{c}{d} của \displaystyle F'_n sao cho \displaystyle \dfrac{a}{b}<\dfrac{h}{k}<\dfrac{c}{d}. Vì \displaystyle \dfrac{h}{k} không thuộc \displaystyle F'_n nên nó cũng không thuộc \displaystyle F_n, suy ra \displaystyle k>n, kết hợp với \displaystyle k\leq n+1 ta có \displaystyle k=n+1.

Từ chứng minh của định lý 1 suy ra \displaystyle k=n+1\geq b+d\Rightarrow \displaystyle \dfrac{a}{b}<\dfrac{c}{d} là hai phân số liên tiếp của \displaystyle F_n, mà \displaystyle b+d\leq n+1, suy ra chúng không thể là hai số hạng liên tiếp của \displaystyle F'_n, vô lý. \displaystyle \Box

Chú ý 1. Dùng định lý Pick (bạn đọc có thể xem thêm về định lý Pick ở địa chỉ https://nttuan.org/2017/03/18/topic-872/) ta có một chứng minh khác của 2).

Trong mặt phẳng tọa độ \displaystyle Oxy, xét các điểm \displaystyle M(1;0)\displaystyle N(1;1). Mỗi số hạng \displaystyle \dfrac{h}{k} của \displaystyle F_n ta cho tương ứng với điểm nguyên có tọa độ \displaystyle (k;h). Khi quay tia \displaystyle OM ngược chiều kim đồng hồ đến tia \displaystyle ON ta “gặp” mỗi điểm nguyên không quá một lần và không gặp đồng thời hai điểm nguyên (ta quan tâm đến các điểm nguyên tương ứng với các số hạng của \displaystyle F_n). Xét hai số hạng liên tiếp \displaystyle \dfrac{a}{b}<\dfrac{c}{d} của \displaystyle F_n và hai điểm \displaystyle X(b;a),Y(d;c) lần lượt tương ứng với chúng. Theo trên ta thấy tam giác \displaystyle OXY không chứa điểm nguyên nào bên trong cũng như trên biên trừ ba đỉnh của nó, suy ra \displaystyle S_{OXY}=\dfrac{1}{2}\Rightarrow bc-ad=1. \displaystyle \Box

2) Dãy Stern-Brocot

Trong phần này tôi sẽ giới thiệu một dãy tương tự như dãy Farey, tên chúng là dãy Stern-Brocot, có tên gọi này vì chúng được tìm ra một cách độc lập bởi Moritz Stern (1858) và Achille Brocot (1861). Stern là một nhà Toán học Đức còn Brocot là một nhà thiết kế đồng hồ người Pháp.

Trong định nghĩa dưới đây, \displaystyle \dfrac{1}{0} là số hữu tỷ hình thức, ta xem như nó lớn hơn mọi số hữu tỷ thực sự.

Định nghĩa 2. Dãy Stern-Brocot thứ \displaystyle n\, (n\in\mathbb{N}), ký hiệu \displaystyle SB_n, được xác định như sau: \displaystyle SB_0 là dãy \displaystyle \frac{0}{1},\frac{1}{0} và với mỗi số nguyên dương \displaystyle n, \displaystyle SB_n được tạo ra bằng cách chép lại toàn bộ (giữ nguyên thứ tự) các số hạng của \displaystyle SB_{n-1} và chèn vào giữa hai số hạng liên tiếp phân số trung gian ở dạng tối giản của chúng.

Chú ý 2. Theo mục trước thì các phân số trung gian là tối giản mà không cần phải thu gọn.

Ví dụ 3. Một số dãy Stern-Brocot:

\displaystyle SB_0:\frac{0}{1},\frac{1}{0}.

\displaystyle SB_1:\frac{0}{1},\frac{1}{1},\frac{1}{0}.

\displaystyle SB_2:\frac{0}{1},\frac{1}{2},\frac{1}{1},\frac{2}{1},\frac{1}{0}.

Dễ thấy rằng với mỗi số tự nhiên \displaystyle n, \displaystyle SB_n là một dãy tăng gồm \displaystyle 2^n+1 số hữu tỷ không âm, và hai số cách đều số ở giữa là nghịch đảo của nhau.

Ví dụ 4 (Cây Stern-Brocot). Ta có thể nhúng các dãy Stern-Brocot vào một cây như hình dưới đây, gọi là cây Stern-Brocot. Ta thấy mỗi số hữu tỷ không âm có mặt đúng một lần trong cây. Thật vậy, vì mỗi dãy Stern-Brocot là một dãy tăng nên mọi số hữu tỷ không âm xuất hiện nhiều nhất một lần trong cây, bây giờ ta chứng minh mọi số hữu tỷ không âm đều xuất hiện trong cây. Xét một số hữu tỷ không âm ở dạng tối giản \displaystyle \dfrac{m}{n}. Tồn tại số tự nhiên \displaystyle p và hai số hạng \displaystyle \dfrac{a}{b},\dfrac{a'}{b'} của \displaystyle SB_p sao cho \displaystyle \dfrac{a}{b}<\dfrac{m}{n}<\dfrac{a'}{b'}. Nếu \displaystyle \dfrac{m}{n} là phân số trung gian của \displaystyle \dfrac{a}{b},\dfrac{a'}{b'} thì tất nhiên nó xuất hiện trong cây, nếu không sẽ xảy ra một trong hai trường hợp: \displaystyle \dfrac{a}{b}<\dfrac{m}{n}<\dfrac{a+a'}{b+b'}, ta thay phân số \displaystyle \dfrac{a'}{b'} bởi \displaystyle \dfrac{a+a'}{b+b'}; \dfrac{a+a'}{b+b'}<\dfrac{m}{n}<\dfrac{a'}{b'}, ta thay phân số \displaystyle \dfrac{a}{b} bởi \displaystyle \dfrac{a+a'}{b+b'}. Quá trình này không thể tiếp tục mãi vì với dãy dạng \displaystyle \dfrac{a}{b}<\dfrac{m}{n}<\dfrac{a'}{b'} ta luôn có \displaystyle m+n\geq a+a'+b+b', suy ra \displaystyle \dfrac{m}{n} xuất hiện trong cây.

SternBrocot

Chú ý 3. Khi thay \displaystyle \dfrac{0}{1}<\dfrac{1}{0} bởi hai số hữu tỷ không âm \displaystyle \dfrac{a}{b}<\dfrac{c}{d} với \displaystyle bc-ad=1 ta sẽ được các dãy mới, gọi là các dãy Stern-Brocot suy rộng. Có thể chứng minh được rằng mọi số hữu tỷ nằm giữa \displaystyle \dfrac{a}{b}\displaystyle \dfrac{c}{d} đều xuất hiện trong một dãy Stern-Brocot suy rộng nào đó.

3) Đường tròn Ford

Định nghĩa. Cho số hữu tỷ \displaystyle a/b với \displaystyle (a,b)=1,\, b>0. Đường tròn Ford của số hữu tỷ này ký hiệu bởi \displaystyle C[a,b] là đường tròn trong mặt phẳng tọa độ có tâm \displaystyle (a/b;1/2b^2) và bán kính \displaystyle 1/2b^2.

Các đường tròn Ford có tên như thế sau khi Ford nghiên cứu chúng vào năm 1938 (Xem bài trên AMM 1938/số 9). Dễ thấy \displaystyle C[a,b] tiếp xúc với trục hoành tại điểm có hoành độ \displaystyle a/b và nằm trên nó.

Định lý 4. Xét hai đường tròn Ford khác nhau \displaystyle C[a,b]\displaystyle C[c,d]. Khi đó

1) Nếu \displaystyle |ad-bc|=1 thì hai đường tròn tiếp xúc ngoài với nhau.

2) Nếu \displaystyle |ad-bc|>1 thì hai đường tròn ở ngoài nhau.

Chứng minh. Ta tính được bình phương của độ dài đoạn nối tâm của hai đường tròn trừ bình phương của tổng độ dài hai bán kính của hai đường tròn bằng \displaystyle  \frac{(ad-bc)^2-1}{b^2d^2}. Từ đó định lý được chứng minh.

Từ định lý trên ta thấy các đường tròn Ford của hai phân số Farey liên tiếp tiếp xúc ngoài với nhau.

Định lý 5. Cho các phân số Farey liên tiếp \displaystyle \displaystyle \frac{a}{b}<\frac{h}{k}<\frac{c}{d}. Khi đó

1) \displaystyle C[a;b] tiếp xúc với \displaystyle C[h,k] tại \displaystyle \displaystyle \left(\frac{h}{k}-\frac{b}{k(b^2+k^2)};\frac{1}{b^2+k^2}\right).

2) \displaystyle C[c;d] tiếp xúc với \displaystyle C[h,k] tại \displaystyle \displaystyle \left(\frac{h}{k}+\frac{d}{k(d^2+k^2)};\frac{1}{d^2+k^2}\right).

3) Tiếp điểm của \displaystyle C[a;b]\displaystyle C[h,k] nằm trên nửa đường tròn có đường kính là đoạn nối hai điểm \displaystyle (a/b;0)\displaystyle (h/k;0).

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

4) Xấp xỉ số vô tỷ bởi số hữu tỷ

Trong phần này chúng tôi sẽ dùng dãy Farey để chứng minh một số kết quả về xấp xỉ số vô tỷ bởi số hữu tỷ, sau đó giới thiệu một số áp dụng của các kết quả này.

Định lý 6. (Dirichlet, 1842) Cho số thực \displaystyle \alpha và số nguyên \displaystyle Q\geq 1. Khi đó tồn tại các số nguyên \displaystyle a\displaystyle q sao cho \displaystyle 1\leq q\leq Q\displaystyle \left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q(Q+1)}.

Chứng minh thứ nhất. Phân hoạch khoảng \displaystyle [0;1) thành \displaystyle Q+1 khoảng \displaystyle I_i=\left[\dfrac{i-1}{Q+1};\dfrac{i}{Q+1}\right) với \displaystyle i=1,2,\cdots,Q+1. Xét \displaystyle Q số \displaystyle \{i\alpha\} với \displaystyle i=1,2,\cdots,Q.

Nếu tồn tại \displaystyle i sao cho \displaystyle \{i\alpha\}\in I_1 thì với \displaystyle i đó ta có

\displaystyle 0\leq i\alpha-[i\alpha]<\dfrac{1}{Q+1}\Rightarrow \left|\alpha-\frac{[i\alpha]}{i}\right|<\dfrac{1}{i(Q+1)},

đến đây ta chỉ cần chọn \displaystyle q=i\displaystyle a=[i\alpha].

Nếu tồn tại \displaystyle i sao cho \displaystyle \{i\alpha\}\in I_{Q+1} thì với \displaystyle i đó ta có

\displaystyle \frac{Q}{Q+1}\leq i\alpha-[i\alpha]<1\Rightarrow \left|\alpha-\frac{[i\alpha]+1}{i}\right|\leq\dfrac{1}{i(Q+1)}, ta chọn \displaystyle q=i\displaystyle a=[i\alpha]+1.

Nếu không xảy ra hai trường hợp trên thì tồn tại \displaystyle i>j để \displaystyle \{i\alpha\}\displaystyle \{j\alpha\} cùng thuộc \displaystyle I_k với \displaystyle k nào đó thỏa mãn \displaystyle 2\leq k\leq Q. Suy ra

\displaystyle 0\leq |\{i\alpha\}-\{j\alpha\}|<\frac{1}{Q+1}\Rightarrow \left|\alpha-\frac{[i\alpha]-[j\alpha]}{i-j}\right|<\frac{1}{(i-j)(Q+1)}, ta chọn \displaystyle q=i-j\displaystyle a=[i\alpha]-[j\alpha].

Chứng minh thứ hai. Giả sử \displaystyle T_Q là mở rộng mod \displaystyle 1 của dãy Farey bậc \displaystyle Q, nghĩa là

\displaystyle T_Q=\left\{\frac{a}{q}|a\in\mathbb{Z},q\in\mathbb{N}^*,q\leq Q,\gcd (a,q)=1\right\}.

Với mỗi phân số \displaystyle \dfrac{a}{q} thuộc \displaystyle T_Q, lấy \displaystyle x<y là hai phân số kề với nó trong \displaystyle T_Q, nghĩa là \displaystyle x<\dfrac{a}{d}<y là ba phân số liên tiếp trong \displaystyle T_Q. Gọi \displaystyle x' là phân số trung gian của \displaystyle x\displaystyle \dfrac{a}{q}, \displaystyle y' là phân số trung gian của \displaystyle y\displaystyle \dfrac{a}{q}. Đặt \displaystyle I_{a/d}=[x';y'].

Dễ thấy \displaystyle \{I_{a/d}\}_{a/d\in T_Q} là một phủ của \displaystyle \mathbb{R}, do đó tồn tại \displaystyle \dfrac{a}{d}\in T_Q sao cho \displaystyle \alpha\in I_{a/d}. Để ý rằng cũng như \displaystyle F_Q, tổng các mẫu của hai phân số liên tiếp trong \displaystyle T_Q không bé hơn \displaystyle Q+1 và hiệu hai phân số liên tiếp trong \displaystyle T_Q là một phân số có tử bằng \displaystyle 1, suy ra

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

Định lý 7. (Dirichlet, 1842) Cho số vô tỷ \displaystyle \alpha. Khi đó có vô hạn phân số tối giản \displaystyle \dfrac{a}{q} sao cho

\displaystyle \left|\alpha-\frac{a}{q}\right|<\frac{1}{q^2}. Hơn nữa ta có thể chọn \displaystyle q lớn tùy ý.

Chứng minh thứ nhất. 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 \displaystyle Q\geq 1 bất kỳ, theo định lý trên, tồn tại phân số \displaystyle \dfrac{a}{q} sao cho \displaystyle 1\leq q\leq Q

\displaystyle \left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q(Q+1)}. Bằng cách thu gọn \displaystyle \dfrac{a}{q} nếu cần, ta có thể xem phân số này tối giản.

Do \displaystyle 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 \dfrac{a_1}{q_1},\dfrac{a_2}{q_2},\cdots,\dfrac{a_m}{q_m} thỏa mãn bất đẳng thức trong định lí. Vì \displaystyle \alpha là số vô tỷ nên \displaystyle |\alpha-a_i/q_i|>0\,\forall i, bởi thế nên ta có thể chọn được số nguyên dương \displaystyle Q để

\displaystyle Q>\max \{|\alpha-a_i/q_i|^{-1}\}.

Dùng định lí 1 cho  số \displaystyle Q này ta tìm được phân số tối giản \dfrac{a_{m+1}}{q_{m+1}} sao cho \displaystyle 1\leq q_{m+1}\leq Q

\displaystyle \left|\alpha-\frac{a_{m+1}}{q_{m+1}}\right|\leq\frac{1}{q_{m+1}(Q+1)}<\frac{1}{q_{m+1}^2}.

Phân số này khác tất cả các phân số trước vì

\displaystyle \left|\alpha-\frac{a_{m+1}}{q_{m+1}}\right|\leq\frac{1}{q_{m+1}(Q+1)}<\frac{1}{Q}<\min\{|\alpha-a_i/q_i|\}.

Để kết thúc chỉ cần để ý rằng với mỗi \displaystyle q>1 chỉ có nhiều nhất hai giá trị \displaystyle a làm cho bất đẳng thức trong định lí đúng.

Chứng minh thứ hai. Không mất tính tổng quát ta giả sử \displaystyle 0<\alpha<1. Ta có thể chọn \displaystyle a=0,q=1 để được một phân số tối giản thỏa mãn. Giả sử ta đã xây dựng được một vài phân số, ta sẽ chỉ ra một phân số khác cũng thỏa mãn bất đẳng thức trong định lí nhưng khác tất cả các phân số này. Chọn số nguyên dương \displaystyle n đủ lớn sao cho \displaystyle \dfrac{1}{n} nhỏ hơn tất cả các khoảng cách từ \displaystyle \alpha đến các phân số đã được tìm. Số \displaystyle \alpha sẽ nằm giữa hai phần số liên tiếp \displaystyle a/b<c/d của \displaystyle F_n, giả sử \displaystyle b\geq d. Vì \displaystyle \dfrac{c}{d}-\dfrac{a}{b}=\dfrac{1}{bd}\leq\dfrac{1}{b+d-1}\leq\dfrac{1}{n} nên cả \displaystyle a/b\displaystyle c/d đều khác tất cả các phân số trước, mà \displaystyle |\alpha-c/d|<\dfrac{1}{bd}<\dfrac{1}{d^2}, suy ra ta có thể chọn \displaystyle c/d là phân số tiếp theo.

Định lý 8. (Hurwitz, 1891)

1) Cho số vô tỷ \displaystyle \alpha. Khi đó có vô hạn phân số tối giản \displaystyle \dfrac{a}{q} sao cho

\displaystyle \left|\alpha-\frac{a}{q}\right|<\frac{1}{\sqrt{5}q^2}. Hơn nữa ta có thể chọn q lớn tùy ý.

2) Cho số thực \displaystyle A>\sqrt{5}. Khi đó chỉ có hữu hạn phân số tối giản \displaystyle \dfrac{a}{q} sao cho

\displaystyle \left|\alpha-\frac{a}{q}\right|<\frac{1}{Aq^2}, ở đây \displaystyle \alpha=\dfrac{\sqrt{5}-1}{2}.

Chứng minh.

1) Không mất tính tổng quát ta giả sử \displaystyle 0<\alpha<1. Xét một số nguyên dương \displaystyle n bất kỳ.

Số \displaystyle \alpha sẽ nằm giữa hai phần số liên tiếp \displaystyle a/b<c/d của \displaystyle F_n. Ta chỉ cần chứng minh một trong ba phân số \displaystyle \dfrac{a}{b}, \displaystyle \dfrac{c}{d}, \displaystyle \dfrac{a+c}{b+d} thỏa mãn bất đẳng thức trong định lí, phần sau sẽ làm như trong chứng minh định lí 2.

Giả sử \displaystyle \displaystyle\frac{a}{b}<\frac{a+c}{b+d}<\alpha<\frac{c}{d} và cả ba phân số đều không thỏa mãn bất đẳng thức trong định lí, nghĩa là

\displaystyle \alpha-\frac{a}{b}\geq \frac{1}{\sqrt{5}b^2},\quad\alpha-\frac{a+c}{b+d}\geq\frac{1}{\sqrt{5}(b+d)^2},\quad \frac{c}{d}-\alpha\geq\frac{1}{\sqrt{5}d^2}.

Cộng bất đẳng thức thứ nhất với thứ ba, thứ hai với thứ ba ta được

\displaystyle \frac{\sqrt{5}}{bd}\geq\frac{1}{b^2}+\frac{1}{d^2},\quad \frac{\sqrt{5}}{d(b+d)}\geq \frac{1}{(b+d)^2}+\frac{1}{d^2}.

Đặt \displaystyle b/d=t, từ trên ta có một hệ bất phương trình bậc hai ẩn \displaystyle t, giải hệ này ta có \displaystyle t=\dfrac{\sqrt{5}-1}{2}\not\in\mathbb{Q}, vô lí.

2) Giả sử bất đẳng thức trên đúng với vô hạn phân số \displaystyle a/q. Vì mỗi \displaystyle q chỉ có nhiều nhất hai giá trị \displaystyle a làm cho bất đẳng thức đó đúng nên \displaystyle q chạy trên một tập vô hạn.

Viết lại bất đẳng thức trong định lí dưới dạng \displaystyle \frac{q\sqrt{5}}{2}-\frac{1}{Aq}<\frac{q}{2}+a<\frac{q\sqrt{5}}{2}+\frac{1}{Aq}, bình phương ta có

\displaystyle \frac{1}{A^2q^2}-\frac{\sqrt{5}}{A}<a^2+aq-q^2<\frac{1}{A^2q^2}+\frac{\sqrt{5}}{A}.\displaystyle A>\sqrt{5} nên ta có thể chọn \displaystyle q đủ lớn để \displaystyle -1<\frac{1}{A^2q^2}-\frac{\sqrt{5}}{A}<a^2+aq-q^2<\frac{1}{A^2q^2}+\frac{\sqrt{5}}{A}<1, với \displaystyle q này, \displaystyle a^2+aq-q^2=0, vô lý!

Ví dụ 1. (Euler, 1747) Mọi số nguyên tố dạng \displaystyle 4k+1 có thể viết thành tổng của hai số chính phương.

Lời giải. Theo định lý Wilson, tồn tại số nguyên dương \displaystyle c sao cho \displaystyle c^2+1\equiv 0\pmod{p}. Áp dụng định lý Dirichlet với \displaystyle Q=[\sqrt{p}] và số \displaystyle \alpha=c/p, tồn tại các số nguyên \displaystyle a,b sao cho \displaystyle 1\leq b\leq [\sqrt{p}]

\displaystyle \left|\frac{c}{p}-\frac{a}{b}\right|<\frac{1}{b(Q+1)}<\frac{1}{b\sqrt{p}}. \,\, (1)

Từ \displaystyle (1) ta có \displaystyle |cb-ap|<\sqrt{p}, suy ra \displaystyle 0<(cb-ap)^2+b^2<2p, mà

\displaystyle (cb-ap)^2+b^2\equiv b^2(c^2+1)\equiv 0\pmod{p}, suy ra \displaystyle (cb-ap)^2+b^2=p.

Ví dụ 2. (Phương trình Pell) Cho \displaystyle d là số nguyên dương không phải là số chính phương. Xét phương trình Pell

\displaystyle x^2-dy^2=1.\quad (*)

a) Chứng minh rằng \displaystyle (*) có nghiệm nguyên dương.

b) Cho \displaystyle (x_1,y_1),(x_2,y_2) là hai nghiệm nguyên dương của \displaystyle (*).

Chứng minh rằng

\displaystyle x_1<x_2\Leftrightarrow y_1<y_2\Leftrightarrow x_1+y_1\sqrt{d}<x_2+y_2\sqrt{d}.

c) Gọi \displaystyle (x',y') là nghiệm nguyên dương của \displaystyle (*) với \displaystyle x' nhỏ nhất. Chứng minh rằng tập nghiệm nguyên dương của \displaystyle (*)\displaystyle \{(x_n,y_n)|n=1,2,\cdots\}, ở đây \displaystyle (x_n),(y_n) là hai dãy các số nguyên dương xác định bởi

\displaystyle x_n+y_n\sqrt{d}=(x'+y'\sqrt{d})^n,\quad\forall n\geq 1.

Lời giải.

a) Vì \displaystyle d không phải số chính phương nên \displaystyle \sqrt{d} là số vô tỷ, do đó theo định lý Drichlet, tồn tại vô hạn phân số tối giản \displaystyle p/q sao cho \displaystyle \left|\sqrt{d}-\frac{p}{q}\right|<\frac{1}{q^2}. Hơn nữa ta có thể chọn \displaystyle q lớn tùy ý.

Với các phân số \displaystyle p/q đó ta có \displaystyle |p^2-dq^2|<1+2\sqrt{d}, suy ra tồn tại số nguyên \displaystyle c\not=0 để có vô hạn phân số tối giản \displaystyle p/q sao cho \displaystyle p^2-dq^2=c.\, (1) Trong các phân số thỏa mãn \displaystyle (1), ta chọn hai phân số khác nhau \displaystyle p_1/q_1\displaystyle p_2/q_2 sao cho

\displaystyle p_1\equiv p_2\pmod{|c|},\quad q_1\equiv q_2\pmod{|c|}. Xét các số hữu tỷ ab xác định bởi

\displaystyle a+b\sqrt{d}=\frac{p_1+q_1\sqrt{d}}{p_2+q_2\sqrt{d}}=\frac{p_1p_2-dq_1q_2}{c}+\frac{p_2q_1-p_1q_2}{c}\sqrt{d}.

Theo cách chọn \displaystyle p_1/q_1\displaystyle p_2/q_2 ta có \displaystyle a,b là các số nguyên với \displaystyle b\not=0.

Ta thấy \displaystyle (|a|,|b|) là một nghiệm nguyên dương của \displaystyle (*)

\displaystyle a^2-db^2=(a+b\sqrt{d})(a-b\sqrt{d})=\frac{p_1+q_1\sqrt{d}}{p_2+q_2\sqrt{d}}\cdot \frac{p_1-q_1\sqrt{d}}{p_2-q_2\sqrt{d}}=\frac{c}{c}=1.

b) Do \displaystyle x_1,y_1,x_2,y_2 là các số nguyên dương thỏa mãn \displaystyle x_1^2=1+dy_1^2,\quad x_2^2=1+dy_2^2 nên \displaystyle x_1<x_2\Leftrightarrow y_1<y_2. Từ đây ta có điều cần chứng minh.

c) Dễ thấy \displaystyle (x_n,y_n) là nghiệm nguyên dương của phương trình với mọi \displaystyle n=1,2,\cdots. Bây giờ giả sử \displaystyle (x_0,y_0) là một nghiệm nguyên dương nào đó của phương trình. Ta sẽ chứng minh tồn tại số nguyên dương \displaystyle n để \displaystyle (x_0,y_0)=(x_n,y_n), hay \displaystyle x_0+y_0\sqrt{d}=(x'+y'\sqrt{d})^n. Nếu điều này không xảy ra thì tồn tại số nguyên dương \displaystyle k thỏa mãn

\displaystyle (x'+y'\sqrt{d})^k<x_0+y_0\sqrt{d}<(x'+y'\sqrt{d})^{k+1}, từ đây ta có \displaystyle 1<(x_0+y_0\sqrt{d})(x'-y'\sqrt{d})^k<x'+y'\sqrt{d}\,\, (2).

Gọi \displaystyle a\displaystyle b là các số nguyên xác định bởi \displaystyle a+b\sqrt{d}=(x_0+y_0\sqrt{d})(x'-y'\sqrt{d})^k. Từ \displaystyle (2) ta thấy \displaystyle (a,b) là một nghiệm nguyên dương của phương trình \displaystyle (*)\displaystyle a<x', vô lý.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s