Tag: chuyên Toán

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]” →

Polynomials in one variable: Basic definitions


Trong bài này K là một trong các tập hợp \mathbb{F}_p (tập các số nguyên modulo một số nguyên tố p), \mathbb{Q}, \mathbb{R}, hoặc \mathbb{C}.

Định nghĩa 1. Cho n là một số tự nhiên và a_0,a_1,...,a_n \in K. Mỗi tổng hình thức có dạng

a_n x^n+a_{n-1} x^{n-1}+\ldots+a_1 x+a_0

được gọi là một đa thức trên K theo biến x với hệ số a_0,a_1,...,a_n. Nếu k là chỉ số lớn nhất sao cho a_k \neq 0, thì ta nói đa thức f(x)=a_k x^k+\ldots+a_1x+a_0 có bậc k, viết \text{deg}(f(x))=k, a_k được gọi là hệ số đầu của đa thức f(x), và a_0 được gọi là hệ số tự do của f(x). Nếu a_0 là hệ số đầu của f(x), thì f(x) được gọi là đa thức hằng.

Nếu hệ số đầu của f(x) là 1, thì f(x) được gọi là đa thức monic. Tập tất cả đa thức với hệ số trong K được ký hiệu bởi K[x].

Theo định nghĩa này thì đa thức không, đa thức mà mọi hệ số là không, không có bậc. Để thuận tiện, ta qui ước nó là đa thức hằng và có bậc bằng -\infty. Một đa thức hằng f(x)=a_0 có bậc 0 nếu a_0 \neq 0. Hai đa thức bằng nhau nếu chúng có cùng bậc và tất cả các hệ số tương ứng bằng nhau. Cần phân biệt giữa đa thức f(x) và hàm đa thức tương ứng từ K đến K xác định bởi thay một phần tử của K vào vị trí của x. Nếu f(x)=a_m x^m+\ldots+a_1x+a_0 và c \in K, thì f(c)=a_m c^m+\ldots+a_1c+a_0 được gọi là giá trị của f(x) tại c. Nếu K là \mathbb{F}_p thì có thể có hai đa thức khác nhau xác định cùng một hàm đa thức.

Ví dụ 1. Cho K là \mathbb{F}_3 và xét các đa thức x^3 và x. Với mỗi c \in \mathbb{F}_3, ta có c^3 \equiv c\pmod{3}, do đó các hàm đa thức f(x)=x^3 và g(x)=x là bằng nhau như các hàm từ \mathbb{F}_3 tới \mathbb{F}_3.

Continue reading “Polynomials in one variable: Basic definitions” →

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)