Category: Number theory

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à

\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 q>1 chỉ có nhiều nhất hai giá trị a làm cho bất đẳng thức trong định lí đúng. \Box

Continue reading “Pell’s equation” →

Siegel’s lemma


Trong bài này tôi sẽ giới thiệu một chứng minh của bổ đề Siegel, một bổ đề có nhiều áp dụng trong số học (xem trong [1], trang 316).

Bổ đề Siegel. Cho hai số nguyên dương N>M và một bảng các số nguyên không đồng thời bằng không (a_{i,j}) có cỡ M\times N. Khi đó hệ phương trình

\displaystyle \sum_{j=1}^Na_{i,j}x_j=0,\quad i=1,2,\ldots,M

có nghiệm nguyên (y_1,y_2,\ldots,y_N) thỏa mãn \max \mid y_i\mid \leq \left(N\max \mid a_{i,j}\mid \right)^{\frac{M}{N-M}} và các số y_1,y_2,\ldots,y_N không đồng thời bằng không.

Hệ phương trình thuần nhất trên có số ẩn nhiều hơn số phương trình và có hệ số hữu tỷ nên nó có nghiệm hữu tỷ khác không, do đó nó có nghiệm nguyên khác không (xem trong [2], trang 49). Bổ đề nói rằng ta có thể tìm nghiệm nguyên không tầm thường đủ nhỏ của hệ.

Chứng minh. Đặt a=\max \mid a_{i,j}\mid, \displaystyle L_i(x_1,x_2,\ldots,x_N)=\sum_{j=1}^Na_{i,j}x_j,
\displaystyle a_i^{+}=\sum_{j=1}^N\max\{a_{i,j};0\}, và \displaystyle a_i^{-}=\sum_{j=1}^N\min \{a_{i,j};0\}, với i=1,2,\ldots,M.

Xét một số tự nhiên b. Gọi S là tập các bộ số tự nhiên (x_1,x_2,\ldots,x_{N}) thỏa mãn x_i\leq b với mọi i. Khi đó \mid S\mid =(b+1)^N và với mỗi (x_i)\in S, bộ

(L_1(x_1,x_2,\ldots,x_N),L_2(x_1,x_2,\ldots,x_N),\ldots,L_M(x_1,x_2,\ldots,x_N))

thuộc tập hợp tích \displaystyle T=\prod_{i=1}^M\{a_i^{-}b,a_i^{-}b+1,\ldots,a_i^{+}b\}. Ta có

\displaystyle \mid T\mid = \prod_{i=1}^M\mid \{a_i^{-}b,a_i^{-}b+1,\ldots,a_i^{+}b\}\mid = \prod_{i=1}^M(b(a_i^+-a_i^-)+1)\leq (bNa+1)^M.

Giả sử chọn được b thỏa mãn bất đẳng thức

\displaystyle (bNa+1)^M<(b+1)^N.\quad (*)

Khi đó tồn tại hai phần tử khác nhau (x_i) và (x_i^{\prime}) của S để hai phần tử tương ứng trong T là một. Ta thấy (y_i), với y_i=x_i-x_i^{\prime}, là một nghiệm nguyên khác không của hệ phương trình thỏa mãn \mid y_i\mid\leq b với mọi i. Bây giờ kiểm tra thấy khi b= \left[\left(Na\right)^{\frac{M}{N-M}}\right] thì có (*), từ đó có nghiệm (y_i) thỏa mãn bổ đề.

Tài liệu tham khảo

[1] Hindry, M., Silverman, J.H.: Diophantine Geometry. Springer, New York (2000)
[2] Jacobson, N.: Lectures in Abstract Algebra: II. Linear Algebra. Springer, New
York (1975)