Tag: Number theory

Square roots are linearly independent


Trong bài này tôi giới thiệu nhiều lời giải cho bài toán quan trọng sau:

Bài toán. Cho a_1,\ldots,a_k là các số nguyên không đồng thời bằng 0. Chứng minh rằng nếu n_1, n_2,\ldots, n_k là các số nguyên dương đôi một khác nhau và không có ước chính phương lớn hơn 1 thì \sum a_i\sqrt{n_i}\not=0. 

Lời giải 1. Ta sẽ chứng minh bằng quy nạp theo N, số ước nguyên tố của \prod n_i, khẳng định: Tồn tại tổng S'=\sum b_i\sqrt{m_i} sao cho SS' là số nguyên khác 0, ở đây m_i là các số nguyên dương đôi một khác nhau và không có ước chính phương khác 1, tập các ước nguyên tố của \prod m_i là tập con của tập các ước nguyên tố của \prod n_i, b_i là các số nguyên, và S=\sum a_i\sqrt{n_i}. Từ đó suy ra S\not=0.

Với N=0 ta chọn S'=1.

Với N=1 ta chọn S'=\sqrt{p_1} khi S=a_1\sqrt{p_1}, chọn S'=-a_1\sqrt{p_1}+a_2 nếu S=a_1\sqrt{p_1}+a_2.

Continue reading “Square roots are linearly independent” →

A proof of Pick’s theorem


Hình tạo bởi một đường gấp khúc đóng và không tự cắt được gọi là đa giác đơn. Một tam giác cơ bản là một tam giác trong mặt phẳng tọa độ có các đỉnh là các điểm nguyên đồng thời trên biên và phần trong của nó không còn điểm nguyên nào khác. Định lí Pick cho một cách đơn giản tính diện tích đa giác đơn có các đỉnh nguyên.

Trong chứng minh định lí Pick ta cần dùng công thức tích diện tích của tam giác trong mặt phẳng tọa độ.

Định lí 1. Trong mặt phẳng tọa độ Oxy, cho tam giác ABC. Khi đó diện tích của tam giác ABC bằng \displaystyle \frac{1}{2}\left|(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)\right|. Nói riêng, với mỗi hai điểm M và N ta có diện tích của tam giác OMN bằng \dfrac{1}{2}\mid x_My_N-y_Mx_N\mid.

Định lí 2. Mọi tam giác cơ bản đều có diện tích bằng \dfrac{1}{2}.

Chứng minh. Giả sử TAB là một tam giác cơ bản bất kỳ. Không mất tính tổng quát, xem T trùng với gốc tọa độ O. Ta cần chứng minh \mid x_1y_2-x_2y_1\mid =1, với (x_1;y_1) và (x_2;y_2) lần lượt là tọa độ của A và B.

Gọi K là điểm sao cho OAKB là hình bình hành. Giả sử M là một điểm nguyên nằm trong hoặc trên biên hình bình hành sao cho M khác các đỉnh. Khi đó M thuộc tam giác ABK và điểm N đối xứng với M qua tâm hình bình hành là điểm nguyên thuộc tam giác OAB nhưng khác các đỉnh, không thể xảy ra điều này do OAB là một tam giác cơ bản. Như vậy hình bình hành OAKB không chứa điểm nguyên nào khác bốn đỉnh của nó.

Giả sử P là một điểm nguyên bất kỳ. Vì \overrightarrow{OA} và \overrightarrow{OB} là hai vector không cùng phương nên tồn tại cặp số thực (\alpha,\beta) để \overrightarrow{OP}=\alpha \overrightarrow{OA}+\beta \overrightarrow{OB}. Gọi P' là điểm xác định bởi \overrightarrow{OP'}=\{\alpha\} \overrightarrow{OA}+\{\beta\} \overrightarrow{OB}. Vì \{\alpha\} và \{\beta\} thuộc [0;1) nên P' thuộc hình bình hành OAKB, nhưng P' lại là một điểm nguyên, suy ra P' phải là một trong bốn đỉnh của hình bình hành. Dễ thấy P'\equiv O và do đó \alpha và \beta là hai số nguyên.

Gọi \overrightarrow{i} và \overrightarrow{j} lần lượt là các vector đơn vị đặt trên Ox và Oy. Khi đó theo lập luận trên, tồn tại các cặp số nguyên (u,v) và (u',v') để \overrightarrow{i}=u \overrightarrow{OA}+v \overrightarrow{OB} và \overrightarrow{j}=u' \overrightarrow{OA}+v' \overrightarrow{OB}. Từ hai đẳng thức này ta có \begin{cases} 1=ux_1+vx_2\\ 0=uy_1+vy_2\end{cases} và \begin{cases}0=u'x_1+v'x_2\\ 1=u'y_1+v'y_2,\end{cases} suy ra \displaystyle u=\frac{y_2}{D},v=-\frac{y_1}{D},u'=-\frac{x_2}{D} và \displaystyle v'=\frac{x_1}{D}, trong đó D=x_1y_2-x_2y_1\not =0 do O,A và B không thẳng hàng. Vì u, v, u' và v' là các số nguyên nên x_1,x_2,y_1 và y_2 đều là bội của D, do đó D^2\mid D và bởi thế, D=\pm 1.

Định lí Pick. Cho P là một đa giác đơn có các đỉnh là các điểm nguyên, I là số điểm nguyên nằm trong và B là số điểm nguyên nằm trên biên của P. Khi đó ta có đẳng thức \displaystyle S_P=I+\frac{1}{2}B-1.

Chứng minh. Chia P thành N tam giác cơ bản. Gọi S là tổng các góc trong của tất cả các tam giác cơ bản đó. Ta sẽ tính S theo hai cách. Vì số tam giác là N nên S=N\pi.

Tổng tất cả các góc có đỉnh là một điểm nguyên nằm trong P bằng 2\pi, tổng tất cả các góc có đỉnh là một điểm nguyên nằm trên biên của P nhưng không phải đỉnh của P bằng \pi và tổng của tất cả các góc có đỉnh là đỉnh của P bằng (n-2)\pi, ở đây n là số đỉnh của P. Do đó S=2\pi I+\pi B-2\pi, suy ra N\pi=2\pi I+\pi B-2\pi\Rightarrow N=2I+B-2. Để ý thêm S_P=\dfrac{1}{2}N, ta có điều phải chứng minh.

Popoviciu’s theorem


Trong  bài này chúng tôi sẽ giới thiệu một công thức tính số nghiệm tự nhiên của phương trình ax+by=n, ở đây a,b là các số nguyên dương thỏa mãn (a,b)=1 và n là số tự nhiên.

Định lí. (Công thức Popoviciu)  Gọi N(a,b;n) là số các cặp số tự nhiên (x,y) sao cho ax+by=n, ở đây a,b là các số nguyên dương thỏa mãn (a,b)=1 và n là số tự nhiên. Khi đó

\displaystyle N(a,b;n)=\frac{n}{ab}-\left\{\frac{a^{-1}n}{b}\right\}-\left\{\frac{b^{-1}n}{a}\right\}+1, với a^{-1} là nghịch đảo modulo b của a và b^{-1} là nghịch đảo modulo a của b.

Chứng minh. Gọi \displaystyle F(z)=\sum_{n=0}^{+\infty}N(a,b;n)z^n là hàm sinh của dãy số \{N(a,b;n)\}_{n\geq 0}. Ta có

\displaystyle F(z)=\sum_{k\in\mathbb{N}}\sum_{l\in\mathbb{N}}z^{ak}z^{bl}=\frac{1}{(1-z^a)(1-z^b)}.\quad (1)

Vì (a,b)=1 nên đa thức (1-z^a)(1-z^b) có nghiệm là 1 với bội 2 và các nghiệm đơn \xi_a^k (k=1,2,\ldots,a-1), \xi_b^l (l=1,2,\ldots,b-1), ở đây \xi_a=\cos\dfrac{2\pi}{a}+i\sin \dfrac{2\pi}{a} và \xi_b=\cos\dfrac{2\pi}{b}+i\sin \dfrac{2\pi}{b}. Kết hợp với (1) ta có tồn tại các số phức C_1,C_2; A_i; B_i sao cho

\displaystyle F(z)=\frac{C_1}{1-z}+\frac{C_2}{(1-z)^2}+\sum_{k=1}^{a-1}\frac{A_k}{1-\xi_a^{-k}z}+\sum_{l=1}^{b-1}\frac{B_l}{1-\xi_b^{-l}z}.\quad (2)

Để ý đến hệ số của z^n, từ (2) ta có

\displaystyle N(a,b;n)=C_1+C_2(n+1)+\sum_{k=1}^{a-1}A_k\xi_a^{-nk}+\sum_{l=1}^{b-1}B_l\xi_b^{-nl}.\quad (3)

Bây giờ ta sẽ đi tìm các số phức C_1,C_2; A_i; B_i từ đẳng thức

\displaystyle \frac{1}{(1-z^a)(1-z^b)}=\frac{C_1}{1-z}+\frac{C_2}{(1-z)^2}+\sum_{k=1}^{a-1}\frac{A_k}{1-\xi_a^{-k}z}+\sum_{l=1}^{b-1}\frac{B_l}{1-\xi_b^{-l}z}.\quad (4)

Nhân hai vế của (4) với (1-z)^2 và cho z\to 1 ta có C_2=\dfrac{1}{ab}, sau đó nhân hai vế của (4) với 1-z, để C_1 một bên và cho z\to 1 ta được C_1=\dfrac{a+b-2}{2ab}. Theo cùng một cách ta có

\displaystyle A_k=\frac{1}{a(1-\xi_a^{kb})},\quad B_l=\frac{1}{b(1-\xi_b^{la})}.

Thay vào (3) ta được

\displaystyle N(a,b;n)=\frac{n}{ab}+\frac{a+b}{2ab}+\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{bk}}+\frac{1}{b}\sum_{l=1}^{b-1}\frac{\xi_b^{-nl}}{1-\xi_b^{al}}.\quad (5)

Từ (5) ta có \displaystyle N(a,1;n)=\frac{n}{a}+\frac{a+1}{2a}+\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{k}}, mà \displaystyle N(a,1;n)=\left[\frac{n}{a}\right]+1, suy ra

\displaystyle \frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{k}}=\frac{1}{2}-\left\{\frac{n}{a}\right\}-\frac{1}{2a},

do đó \displaystyle \frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{bk}}=\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nb^{-1}k}}{1-\xi_a^{k}}=\frac{1}{2}-\left\{\frac{nb^{-1}}{a}\right\}-\frac{1}{2a},

chứng minh tương tự ta được

\displaystyle \frac{1}{b}\sum_{l=1}^{b-1}\frac{\xi_b^{-nl}}{1-\xi_b^{al}}=\frac{1}{2}-\left\{\frac{na^{-1}}{b}\right\}-\frac{1}{2b},

thay hai đẳng thức cuối cùng vào (5) ta có điều cần chứng minh. \Box

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 “Z – K[x]” →