Luận văn Thạc sĩ Toán học: Đa thức bất khả quy trên trường Zp thuật toán Berlekamp và phân tích đa thức trên trường Q

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

63
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn quan tâm đến bài toán phân tích đa thức với hệ số nguyên thành nhân tử bất khả quy trên Q. Đây là một trong những bài toán quan trọng nhất của Lí thuyết đa thức. Ta biết rằng bài toán xét tính bất khả quy của đa thức trên Q có liên quan mật thiết với bài toán xét tính bất khả quy của đa thức trên trường hữu hạn. Cho f(x) là đa thức với hệ số nguyên. Nếu tồn tại một số nguyên tố p sao cho khi chuyển vào Zp[x] bậc của đa thức f(x) không đổi và f(x) bất khả quy trên Zp, thì f(x) là bất khả quy trên Q.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Đa thức bất khả quy trên trường Zp thuật toán Berlekamp và phân tích đa thức trên trường Q

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- VŨ ĐỨC CẢNH ĐA THỨC BẤT KHẢ QUY TRÊN TRƯỜNG Zp THUẬT TOÁN BERLEKAMP VÀ PHÂN TÍCH ĐA THỨC TRÊN TRƯỜNG Q LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2016
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- VŨ ĐỨC CẢNH ĐA THỨC BẤT KHẢ QUY TRÊN TRƯỜNG Zp THUẬT TOÁN BERLEKAMP VÀ PHÂN TÍCH ĐA THỨC TRÊN TRƯỜNG Q LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS. Lê Thị Thanh Nhàn THÁI NGUYÊN - 2016
i Mục lục Lời cảm ơn ii Mở đầu 1 Chương 1. Đa thức bất khả quy 3 1.1 Khái niệm đa thức bất khả quy . . . . . . . . . . . . . . . 3 1.2 Một số tiêu chuẩn bất khả quy trên trường Q . . . . . . . . 7 Chương 2. Thuật toán Berlekamp và bài toán phân tích đa thức thành nhân tử 13 2.1 Trường phân rã của đa thức, trường hữu hạn . . . . . . . . 13 2.2 Thuật toán Berlekamp . . . . . . . . . . . . . . . . . . . . 19 2.3 Tính bất khả quy trên Z p và ứng dụng phân tích bất khả quy trên Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Kết luận 39 Tài liệu tham khảo 40
ii Lời cảm ơn Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của GS.TS. Lê Thị Thanh Nhàn. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học - Đại học Thái Nguyên, Ban Chủ nhiệm Khoa Toán-Tin, cùng các giảng viên đã tham gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu. Tác giả cũng xin chân thành cảm ơn Phòng Giáo dục và Đào tạo huyện Tiên Lãng, Ban giám hiệu và các đồng nghiệp trường THCS Vinh Quang, huyện Tiên Lãng, thành phố Hải Phòng đã tạo điều kiện cho tác giả hoàn thành tốt nhiệm vụ học tập và công tác của mình. Nhân dịp này, tác giả cũng xin gửi lời cảm ơn tới tập thể lớp cao học Toán K8B (khóa 2014-2016), cảm ơn gia đình bạn bè đã động viên và giúp đỡ tác giả rất nhiều trong quá trình học tập.
1 Mở đầu Luận văn quan tâm đến bài toán phân tích đa thức với hệ số nguyên thành nhân tử bất khả quy trên Q. Đây là một trong những bài toán quan trọng nhất của Lí thuyết đa thức. Ta biết rằng bài toán xét tính bất khả quy của đa thức trên Q có liên quan mật thiết với bài toán xét tính bất khả quy của đa thức trên trường hữu hạn. Cho f (x) là đa thức với hệ số nguyên. Nếu tồn tại một số nguyên tố p sao cho khi chuyển vào Z p [x] bậc của đa thức f (x) không đổi và f (x) bất khả quy trên Z p , thì f (x) là bất khả quy trên Q. Chú ý rằng điều ngược lại là không đúng. D. Hilbert đã chỉ ra một đa thức bậc 4 bất khả quy trên Q nhưng khả quy trên mọi trường Z p . Quan hệ trên về tính bất khả quy trên Q và trên Z p gợi ý cho chúng ta nghĩ đến việc tìm một thuật toán phân tích bất khả quy của đa thức trên trường hữu hạn và sử dụng nó để tìm phân tích bất khả quy của đa thức trên Q. Mục đích của luận văn là trình bày chi tiết những kết quả chọn lọc trong một số tài liệu gần đây về đa thức bất khả quy và sự phân tích đa thức thành nhân tử bất khả quy. Trong luận văn này, trước hết chúng tôi xét tính bất khả quy của đa thức trên trường Z p và thuật toán Berlekamp phân tích đa thức thành nhân tử bất khả quy trên trường Z p . Sau đó, sử dụng các kết quả thu được, chúng tôi trình bày một phương pháp phân tích đa thức thành nhân tử trên trường Q các số hữu tỷ. Nội dung nghiên cứu của luận văn là hoàn toàn chưa được tiếp cận ở bậc phổ thông và đại học, nhưng gắn liền với toán sơ cấp, đặc biệt là bài toán phân tích đa thức thành nhân tử rất được quan tâm ở bậc học phổ thông. Luận văn gồm phần mở đầu, hai chương và tài liệu tham khảo. Trong Chương 1, chúng tôi nhắc lại khái niệm đa thức bất khả quy và một số tiêu
2 chuẩn bất khả quy trên Q. Chương 2 là nội dung chính của luận văn. Mục 2.1 dành để nghiên cứu khái niệm trường phân rã của đa thức, từ đó xét cấu trúc của trường hữu hạn. Mục tiếp theo mô tả huật toán Berlekamp phân tích đa thức thành nhân tử trên trường hữu hạn. Mục cuối là ứng dụng kết quả vào bài toán phân tích đa thức trên trường Q. Thái Nguyên, ngày 25 tháng 5 năm 2016 Tác giả Vũ Đức Cảnh
3 Chương 1 Đa thức bất khả quy 1.1 Khái niệm đa thức bất khả quy Trước khi trình bày khái niệm đa thức bất khả quy, chúng ta nhắc lại khái niệm phần tử bất khả quy trong một miền nguyên. Cho V là một miền nguyên và a ∈ V . Ta nói a là ước của b nếu tồn tại c ∈ V sao cho b = ac. Một ước a của b được gọi là ước thực sự nếu b không là ước của a. Phần tử p ∈ V được gọi là phần từ bất khả quy nếu nó khác 0, không khả nghịch và không có ước thực sự. Từ đây ta có khái niệm đa thức bất khả quy trong vành đa thức V [x]. Trong suốt tiết này ta luôn giả thiết V là miền nguyên. Định nghĩa 1.1.1. Cho f (x) ∈ V [x] là đa thức khác 0 và không khả nghịch. Ta nói f (x) là bất khả quy trên V nếu nó không có ước thực sự. Ta nói f (x) khả quy nếu f (x) có ước thực sự. Bổ đề 1.1.2. Đa thức f (x) là bất khả quy nếu và chỉ nếu f (x + a) là bất khả quy với mọi a ∈ V. Chứng minh. Cho a ∈ V . Với mỗi h(x) ∈ V [x] ta đặt h1 (x) = h(x − a). Chú ý rằng deg h1 (x) = deg h(x). Vì thế f (x + a) = k(x)g(x) là phân tích của f (x + a) thành tích của hai đa thức có bậc thấp hơn khi và chỉ khi f (x) = k1 (x)g1 (x) là phân tích của f (x) thành tích của hai đa thức có bậc thấp hơn. Vì vậy f (x) bất khả quy khi và chỉ khi f (x + a) bất khả quy. Từ nay đến hết mục này chúng ta làm việc với đa thức có các hệ số trên một trường K. Trong trường hợp này, các đa thức hằng khác 0 đều khả nghịch. Do đó ta có ngay kết quả sau:
4 Bổ đề 1.1.3. Đa thức f(x) với hệ số trên trường K là bất khả quy nếu và chỉ nếu deg f (x) > 0 và f (x) không phân tích được thành tích của hai đa thức có bậc bé hơn. Sau đây là tính bất khả quy của các đa thức bậc thấp. Bổ đề 1.1.4. Trên một trường K, các phát biểu sau là đúng. (i) Đa thức bậc nhất luôn bất khả quy. (ii) Đa thức bậc 2 và bậc 3 là bất khả quy nếu và chỉ nếu nó không có nghiệm trong K. Chứng minh. (i) Rõ ràng đa thức bậc nhất không thể là tích của hai đa thức bậc thấp hơn, do đó nó bất khả quy. (ii) Giả sử f (x) có nghiệm x = a ∈ K. Vì deg f (x) > 1 nên ta có f (x) = (x − a)g(x), trong đó g(x) ∈ K[x] và deg g(x) = deg f (x) − 1 ≥ 1. Do đó f (x) khả quy. Ngược lại, giả sử f (x) khả quy. Vì f (x) có bậc 2 hoặc 3 nên f (x) phân tích được thành tích của hai đa thức có bậc thấp hơn, một trong hai đa thức đó phải có bậc 1. Rõ ràng đa thức bậc 1 trên một trường có nghiệm trong trường đó, vì thế f (x) có nghiệm trong K Chú ý rằng phát biểu (ii) trong bổ đề trên là không đúng cho trường hợp bậc của đa thức lớn hơn 3. Cụ thể, nếu f (x) bậc lớn hơn 3 và có nghiệm trong K thì f (x) khả quy. Tuy nhiên, tồn tại những đa thức không có nghiệm trong K nhưng vẫn khả quy. Chẳng hạn đa thức (x2 + 1)(x2 + 2) không có nghiệm trong R nhưng nó khả quy trên R. Từ nay về sau, nếu a là ước của b thì ta kí hiệu là a | b. Mệnh đề 1.1.5. Cho p(x) ∈ K[x] là đa thức có bậc dương. Khi đó p(x) bất khả quy nếu và chỉ nếu p(x) | a(x)b(x) kéo theo p(x) | a(x) hoặc p(x) | b(x) với mọi a(x), b(x) ∈ K[x]. Đặc biệt, nếu đa thức bất khả quy p(x) là ước của một tích hữu hạn thì đa thức p(x) phải là ước của ít nhất một trong các đa thức đó. Chứng minh. Cho p(x) bất khả quy. Giả sử p(x) | a(x)b(x) và a(x), b(x) đều không là bội của p(x). Do p(x) bất khả quy nên gcd(p(x), a(x)) = 1 và gcd(p(x), b(x)) = 1. Vì thế, tồn tại s(x), r(x), e(x), f (x) sao cho 1 = s(x)p(x) + r(x)a(x) và 1 = e(x)p(x) + f (x)b(x). Nhân vế với vế của hai
5 đẳng thức này ta có 1 = p(x)g(x) + r(x) f (x)a(x)b(x) với g(x) là một đa thức nào đó. Vì p(x) là ước của a(x)b(x) nên đa thức bên vế phải của đẳng thức trên là bội của p(x), trong khi đó đa thức bên vế trái là 1 không chia hết cho p(x). Điều này là vô lí. Ngược lại, do p(x) có bậc dương nên p(x) 6= 0 và không khả nghịch. Giả sử p(x) = a(x)b(x) với a(x), b(x) ∈ K[x]. Khi đó p(x) | a(x)b(x). Theo giả thiết, p(x) | a(x) hoặc p(x) | b(x). Vì thế p(x) không có ước thực sự, do đó p(x) bất khả quy. Định lý cơ bản của Số học nói rằng mỗi số tự nhiên lớn hơn 1 đều phân tích được thành tích các thừa số nguyên tố và sự phân tích đó là duy nhất nếu không kể đến thứ tự các thừa số. Kết quả sau đây là một sự tương tự đối với đa thức. Định lý 1.1.6. Mỗi đa thức dạng chuẩn bậc dương trong K[x] có thể phân tích được thành tích các đa thức bất khả quy dạng chuẩn và sự phân tích này là duy nhất nếu không kể đến thứ tự các nhân tử. Chứng minh. Trước hết, ta chứng minh sự tồn tại phân tích bằng quy nạp theo bậc của đa thức. Giả sử f (x) ∈ K[x] là đa thức dạng chuẩn bậc d > 0. Nếu d = 1 thì f (x) là bất khả quy, và sự phân tích bất khả quy của f (x) là f (x) = f (x). Cho d > 1 và giả sử kết quả đã đúng cho các bậc nhỏ hơn d. Nếu f (x) bất khả quy thì f (x) có sự phân tích bất khả quy là f (x) = f (x). Vì thế ta giả thiết f (x) không bất khả quy. Khi đó f (x) = g(x)h(x) với degg(x), deg h(x)
6 sự phân tích thành nhân tử bất khả quy dạng chuẩn f (x) = p1 (x)p2 (x)...pn (x) = q1 (x)q2 (x)...qm (x). Ta chứng minh bằng sự quy nạp theo n rằng n = m và sau khi đánh lại thứ tự các nhân tử vế bên phải ta có pi (x) = qi (x) với mọi i = 1, ..., n. Do p1 (x) | q1 (x)q2 (x)...qm (x) và p1 (x) bất khả quy nên theo mệnh đề trên ta có p1 (x) | qi (x) với i nào đó. Không mất tính tổng quát ta giả thiết p1 (x) | q1 (x). Biểu diễn q1 (x) = p1 (x)t1 (x). Vì q1 (x) bất khả quy nên t1 (x) = a ∈ K. Do đó q1 (x) = ap1 (x). Do p1 (x) và q1 (x) có dạng chuẩn nên a = 1. Vì thế p1 (x) = q1 (x). Cho n = 1. Nếu m > 1 thì giản ước cả hai vế cho p1 (x) ta được 1 = q2 (x)...qm (x), điều này là vô lí. Vậy, kết quả đúng cho n = 1. Cho n > 1. Vì p1 (x) = q1 (x) nên f (x) = p2 (x)p3 (x)...pn (x) = q2 (x)q2 (x)...qm (x). Theo giả thiết quy nạp ta có n − 1 = m − 1 và bằng việc đánh số lại thứ tự các nhân tử bất khả quy ở vế phải ta có pi (x) = qi (x) với i = 2, ..., n., suy ra pi (x) = qi (x) với mọi i = 2, ..., n. Từ định lý trên, ta có kết quả sau. Hệ quả 1.1.7. Cho f (x) ∈ K[x] là đa thức với hệ số cao nhất là an . Khi đó tồn tại phân tích f (x) = an f1 (x)... fk (x) với f1 (x), ..., fk (x) là các nhân tử bất khả quy dạng chuẩn, và sự phân tích này là duy nhất nếu không kể đến thứ tự các nhân tử. Euclid đã chứng minh rằng có vô hạn số nguyên tố. Kết quả sau đây là một sự tương tự cho đa thức bất khả quy. Hệ quả 1.1.8. Trên một trường K bất kỳ, có vô hạn đa thức bất khả quy dạng chuẩn. Chứng minh. Chú ý rằng x + 1 ∈ K[x] là đa thức bất khả quy dạng chuẩn. Giả sử f1 (x), ..., fn (x) ∈ K[x] là tất cả các đa thức bất khả quy dạng chuẩn. Đặt f (x) = f1 (x)... fn (x) + 1. Theo định lý trên, tồn tại p(x) là ước bất khả quy dạng chuẩn của f (x). Do đó p(x) = fi (x) với i nào đó. Suy ra p(x) | f1 (x)... fn (x). Vì p(x) | f( x) nên p(x) | 1, điều này vô lí, tức là phải có vô hạn các đa thức bất khả quy dạng chuẩn.
7 1.2 Một số tiêu chuẩn bất khả quy trên trường Q Trong lí thuyết số, bài toán tìm thuật toán tất định với độ phức tạp đa thức để kiểm tra tính nguyên tố của các số tự nhiên là một trong những bài toán quan trọng nhất. Bắt đầu bằng “Sàng Eratosthenes" để tìm các số nguyên tố nhỏ hơn 100 do nhà toán học cổ Hy Lạp Eratosthenes phát minh ra, trải qua hàng nghìn năm sau, mãi đến năm 2002 người ta mới tìm được thuật toán như mong muốn, gọi là Thuật toán kiểm tra nguyên tố AKS. Trong lí thuyết đa thức, một bài toán quan trọng tương tự là tìm các đa thức bất khả quy trên các trường Q, R, C. Nhờ Định lí cơ bản của Đại số “mỗi đa thức bậc dương với hệ số phức đều có ít nhất một nghiệm phức", chúng ta dễ dàng thấy rằng đa thức bất khả quy trên C là và chỉ là các đa thức bậc nhất. Từ Định lí cơ bản của Đại số, ta cũng suy ra rằng các đa thức bất khả quy trên R là và chỉ là các đa thức bậc nhất hoặc bậc hai với biệt thức âm. Tuy nhiên, bài toán xét tính khả quy của các đa thức trên trường Q các số hữu tỷ cho đến nay vẫn là bài toán chưa được giải quyết trọn vẹn. Mục tiêu của mục này là trình bày một số tiêu chuẩn và phương pháp xét tính bất khả quy của đa thức trên Q như phương pháp sử dụng nghiệm hữu tỷ, phương pháp sử dụng Bổ đề Gauss, tiêu chuẩn Eisenstein. Giả sử f (x) ∈ Q[x]. Chú ý rằng f (x) là bất khả quy trên Q khi và chỉ khi a f (x) là bất khả quy, trong đó a là mẫu số chung của các hệ số của f (x). Rõ ràng a f (x) ∈ Z[x]. Do đó ta chỉ cần xét tính bất khả quy trên Q cho các đa thức với hệ số nguyên. Từ nay đến hết mục này, luôn giả thiết f (x) = an xn + ... + a1 x + a0 ∈ Z[x], trong đó an 6= 0 và n > 0. Chú ý rằng một đa thức bậc bậc 1 thì luôn có nghiệm trong Q và cũng luôn bất khả quy trên Q. Đối với đa thức f (x) bậc lớn hơn 1, khi đó nếu f (x) có nghiệm hữu tỷ thì nó khả quy trên Q. Vì thế chúng ta có thể sử dụng tiêu chuẩn có nghiệm hữu tỷ sau đây để xét tính bất khả quy của đa thức trên Q. Bổ đề 1.2.1. Cho f (x) = an xn + ... + a1 x + a0 ∈ Z[x]. Nếu phân số tối giản r/s là nghiệm của f(x) thì r là ước của a0 và s là ước của an . Đặc biệt, nếu an = ±1 thì mọi nghiệm hữu tỷ của f(x) đều là nghiệm nguyên. r Chứng minh. Giả sử là nghiệm của f (x), trong đó r, s ∈ Z và (r, s) = 1. s
8 Khi đó ta có r rn rn−1 r 0 = f ( ) = an n + an−1 n−1 + . . . + a1 + a0 . s s s s Suy ra 0 = an rn + an−1 rn−1 s + . . . + a1 rsn−1 + a0 sn . Vì thế ta có an rn = −(an−1 rn−1 s + . . . + a1 rsn−1 + a0 sn ). Vế phải của đẳng thức là bội của s. Vì thế an rn là bội của s. Do (r, s) = 1 nên s là ước của an . Tương tự ta có a0 sn = −(an rn + an−1 rn−1 s + . . . + a1 rsn−1 ). Vế phải của đẳng thức này là bội của r. Vì thế a0 sn là bội của r. Do (r, s) = 1 nên r là ước của a0 . Bổ đề 1.2.2. Cho f (x) = an xn + ... + a1 x + a0 ∈ Z[x] và m ∈ Z. Nếu phân số tối giản r/s là nghiệm của f (x) thì r − ms là ước của f (m). Đặc biệt, (r + s) là ước của f (−1) và (r − s) là ước của f (1). Chứng minh. Bằng cách khai triển các nhị thức ((x − m) + m)k và nhóm các hạng tử tương ứng, ta có thể phân tích f (x) theo các lũy thừa của (x − m) theo cách sau f (x) = f ((x − m) + m) =an ((x − m) + m)n + . . . + a1 ((x − m) + m) + a0 =an (x − m)n + bn−1 (x − m)n−1 + . . . + b1 (x − m) + b0 , trong đó b0 , b1 , . . . , bn−1 ∈ Z. Suy ra f (m) = b0 và ta có r 0 =f( ) s r r r =an ( − m)n + bn−1 ( − m)n−1 + . . . + b1 ( − m) + f (m). s s s Từ đó ta có 0 = an (r − ms)n + bn−1 (r − ms)n−1 s + . . . + b1 (r − ms)n−1 sn−1 + f (m)sn .
9 Vì thế ta có f (m)sn = −an (r − ms)n − bn−1 (r − ms)n−1 s − . . . − b1 (r − ms)n−1 sn−1 . Vế phải của đẳng thức trên là bội của r −ms. Do đó f (m)sn là bội của r −ms. Đặt d = gcd(s, r − ms). Vì d là ước chung của s và r − ms nên d là ước của r s và r. Vì là phân số tối giản nên d = 1. Suy ra gcd(sn , r − ms) = 1. Vì thế s r − ms là ước của f (m). Đặc biệt, khi m = 1 thì r − s là ước của f (1) và khi m = −1 thì r + s là ước của f (−1). Sau đây là một số ví dụ minh họa. Ví dụ 1.2.3. (i) Đa thức f (x) = 4x3 − 16x2 + 11x + 10 là khả quy trên Q. (ii) Đa thức g(x) = 4x3 + 8x2 − 6x + 5 = 0 là bất khả quy trên Q. Chứng minh. Ta dùng Bổ đề 1.2.1 và Bổ đề 1.2.2 để chứng minh Ví dụ 1.2.3 như sau. (i) Giả sử phân số tối giản r/s là nghiệm của f (x). Khi đó ta có r là ước của 10 và s là ước của 4. Suy ra r ∈ {±1, ±2, ±5,±10} và s ∈ {±1, ±2, ±4}.Vì f (1) = 9 và f (−1) = −21 1 1 5 5 nên ta có r/s ∈ ± , ± , ± , ± , ±2, ±10 . 2 4 2 4 1 5 Thử lại ta thấy − , 2, là nghiệm của f (x). Vậy f (x) khả quy trên Q. 2 2 (ii) Ta có 2g(x) = 8x3 + 16x2 − 12x + 10 = 0. Khi đó g(x) = 0 nếu và chỉ nếu 8x3 + 16x2 − 12x + 10 = 0. Đặt y = 2x, phương trình thứ hai trở thành h(y) = y3 + 4y2 − 6y + 10 = 0, có an = 1, nên h(y) nếu có nghiệm hữu tỷ thì đó là nghiệm nguyên(theo (1)), giả sử s là nghiệm của h(y) thì theo (1), s | 10, hay s ∈ {±1, ±2, ±5, ±10}. Thử lại ta thấy không có giá trị nào là nghiệm của h(y), tức là g(x) không có nghiệm hữu tỷ. Do đó g(x) bất khả quy trên Q. Việc xét tính bất khả quy bằng phương pháp tìm nghiệm hữu tỷ gặp rất nhiều hạn chế. Nếu đa thức có bậc 2 hoặc 3 thì đa thức đó là bất khả quy trên Q khi và chỉ khi nó có nghiệm hữu tỷ. Tuy nhiên, nếu bậc của đa thức lớn hơn hay bằng 4 thì phát biểu trên không còn đúng nữa. Chẳng hạn, (x2 + 2)(x2 + 2) không có nghiệm hữu tỷ, nhưng lại khả quy trên Q. Một trong những phương pháp hữu hiệu để xét tính bất khả quy của đa thức trên Q là sử dụng Bổ đề Gauss. Phương pháp này đặc biệt hiệu quả
10 cho các đa thức không có nghiệm hữu tỷ. Trước hết chúng ta phát biểu và chứng minh Bổ đề Gauss. Định lý 1.2.4. (Bổ đề Gauss). Cho p(x) ∈ Z[x]. Giả sử p(x) = g(x) f (x) với g(x), f (x) ∈ Q[x]. Khi đó tồn tại g∗ (x), f∗ (x) ∈ Z[x] sao cho deg g(x) = deg g∗ (x), deg f (x) = deg f∗ (x) và p(x) = g∗ (x) f∗ (x). Đặc biệt, nếu p(x) là khả quy trên Q thì nó phân tích được thành hai đa thức với hệ số nguyên có bậc thấp hơn. Chứng minh. Viết f (x) = a f1 (x) và g(x) = bg1 (x) trong đó a, b ∈ Q và f1 (x), g1 (x) là hai đa thức nguyên bản. Rõ ràng p(x) = ab f1 (x)g1 (x) ∈ Z[x]. Ta chứng minh ab ∈ Z. Thật vậy, giả sử ab ∈ / Z. Khi đó, ab = r/s với r/s là phân số tối giản và s > 1. Viết f1 (x), g1 (x) = an xn + ... + a1 x + a0 . Vì f1 (x), g1 (x) là nguyên bản nên gcd(an , an−1 , ..., a0 ) = 1. Vì p(x) ∈ Z[x] nên ta có ran ra1 ra0 , ..., , ∈ Z. s s s Suy ra s là ước chung của an , . . . , a1 , a0 , điều này là vô lí. Vậy ab ∈ Z. Đặt f∗ (x) = ab f1 (x) và g∗ (x) = g1 (x). Khi đó p(x) = f∗ (x)g∗ (x) với f∗ (x), g∗ (x) ∈ Z[x] và deg f (x) = deg f∗ (x) và deg g(x) = deg g ∗ (x). Dưới đây là một số ví dụ xét tính bất khả quy trên Q bằng việc sử dụng Bổ đề Gauss. Ví dụ 1.2.5. Đa thức f (x) = x4 + 7x3 + x2 + 7 bất khả quy trên Q. Chứng minh. Sử dụng Bổ đề 1.2.1 ta suy ra f (x) không có nghiệm hữu tỷ. Vì thế f (x) không là tích của một đa thức bậc nhất và một đa thức bậc ba. Giả sử f (x) khả quy trên Q. Theo Bổ đề Gauss, f (x) có sự phân tích f (x) = g(x)h(x) trong đó g(x), h(x) ∈ Z[x] có bậc hai và có hệ số cao nhất bằng 1. Viết g(x) = x2 + ax + b và h(x) = x2 + cx + d với a, b, c, d ∈ Z. Đồng nhất hệ số ở hai vế của đẳng thức f (x) = g(x)h(x) ta được bd = 7, bc + ad = 0, ac + d + b = 1, c + a = 7. Vì bd = 7 và vai trò b, d như nhau nên không mất tính tổng quát ta có thể giả thiết b = 1, d = 7 hoặc b = −1, d = −7. Nếu b = 1, d = 7 thì c + 7a = 7 0, ac = −7, a + c = 7. Suy ra a = − ∈ / Z, vô lí. Nếu b = −1, d = −7 thì 6
11 7 −c − 7a = 0, ac = 9, a + c = 7. Suy ra a = − ∈/ Z, vô lí. Như vậy, f (x) bất 6 khả quy trên Q. Ví dụ 1.2.6. Đa thức f (x) = x5 + x3 + x2 + 3 là bất khả quy trên Q. Chứng minh. Sử dụng Bổ đề 1.2.1 ta suy ra f (x) không có nghiệm hữu tỷ. Vì thế f (x) không là tích của một đa thức bậc nhất và một đa thức bậc bốn. Giả sử f (x) khả quy trên Q. Theo Bổ đề Gauss, tồn tại phân tích f (x) = g(x)h(x) trong đó g(x), h(x) ∈ Z[x] có hệ số cao nhất bằng 1 và deg g(x) = 2, deg h(x) = 3. Viết g(x) = x2 + ax + b và h(x) = x3 + cx2 + dx + e với a, b, c, d, e ∈ Z. Đồng nhất hệ số ở hai vế của đẳng thức f (x) = g(x)h(x) ta được c + a = 0, b + d + ac = 1, bc + ad + e = 1, ae + bd = 0, be = 3. Vì be = 3 nên chỉ có thể xảy ra 4 trường hợp sau. Trường hợp 1: b = 1, e = 3. Khi đó c + a = 0, d + ac = 0, c + ad = −2, 3a + d = 0. Từ hai phương trình đầu ta được c = −a, d = a2 . Thay vào phương trình thứ ba được a(a2 − 1) = −2 không có a | 2 thỏa mãn. Trường hợp 2: b = −1, e = −3. Khi đó c + a = 0, d + ac = 2, −c + ad = 4, 3a + d = 0. Từ hai phương trình đầu ta được a = −c, d = a2 + 2. Thay vào phương trình thứ ba được a(a2 + 3) = 4 không có a | 6 thỏa mãn. Trường hợp 3: b = 3, e = 1. Khi đó a + c = 0, d + ac = −2, 3c + ad = 0, a + 3d = 0. Từ hai phương trình đầu ta được a = −c, d = a2 − 2. Thay vào phương trình cuối được 3a2 + a − 6 = 0. Suy ra a ∈ / Z. Không thỏa mãn. Trường hợp 4: b = −3, e = −1. Khi đó a + c = 0, d + ac = 4, −3c + ad = 2, a + 3d = 0. Từ hai phương trình đầu ta được a = −c, d = a2 + 4. Thay vào phương trình thứ ba được a(a2 + 7) = 2. Không có a | 2 thỏa mãn. Vì vậy f (x) bất khả quy. Tiêu chuẩn sau đây cũng rất hay được sử dụng để xét tính bất khả quy của đa thức trên Q. Định lý 1.2.7. (Tiêu chuẩn Eisenstein). Cho f = an xn +...+a1 x+a0 ∈ Z[x]. Giả sử tồn tại một số nguyên tố p thỏa mãn các tính chất (i) p không là ước của hệ số cao nhất an ; (ii) p là ước của các hệ số a0 , a1 , ..., an−1 ; (iii) p2 không là ước của hệ số tự do a0 . Khi đó f(x) là bất khả quy trên Q. Chứng minh. Giả sử f (x) khả quy trên Q. Theo Bổ đề Gauss, tồn tại biểu
12 diễn f (x) = g(x)h(x), trong đó g(x) = bm xm + . . . + b1 x + b0 ∈ Z[x] và h(x) = ck xk +...+c1 x+c0 ∈ Z[x] với deg g(x) = m, deg h(x) = k và m, k < n. Do p là ước của a0 = b0 c0 nên p | b0 hoặc p | c0 . Lại do p2 không là ước của a0 nên trong hai số b0 và c0 , có một và chỉ một số chia hết cho p. Giả thiết p | c0 . Khi đó b0 không chia hết cho p. Vì an = bm ck và an không chia hết cho p nên bm và ck đều không chia hết cho p. Do đó tồn tại số r bé nhất sao cho cr không là bội của p. Ta có ar = b0 cr + (b1 cr−1 + b2 cr−2 + ... + br c0 ). Vì r ≤ k < n nên p | ar . Theo cách chọn r ta có p | b1 cr−1 + b2 cr−2 + ... + br c0 . Suy ra p | b0 cr , điều này là vô lí vì cả hai số b0 và cr đều không là bội của p. Vậy f (x) là bất khả quy trên Q. Ví dụ 1.2.8. (i) Đa thức x2016 + 2015 là bất khả quy trên Q theo tiêu chuẩn Eisenstein với p = 5. (ii) Đa thức 23x3 + 1970 là bất khả quy trên Q theo tiêu chuẩn Eisenstein với p = 5. (iii) Đa thức 2015x2016 − 2016x2015 + 6x30 + 30x6 + 6 là bất khả quy trên Q theo tiêu chuẩn Eisenstein với p = 3. (iv) Đa thức f (x) = x4 − 8x3 + 10x2 − 12x + 3 là bất khả quy trên Q vì đa thức f (x + 3) = x4 + 4x3 − 8x2 − 60x − 78 là bất khả quy trên Q theo tiêu chuẩn Eisenstein với p = 2.
13 Chương 2 Thuật toán Berlekamp và bài toán phân tích đa thức thành nhân tử Trong Lí thuyết số, một trong những bài toán khó nhất và lâu đời nhất là tìm thuật toán hữu hiệu phân tích số tự nhiên ra thừa số nguyên tố. Bài toán này cho đến nay vẫn chưa được giải quyết trọn vẹn. Trong lí thuyết đa thức, bài toán tương tự "tìm thuật toán phân tích đa thức trên một trường thành nhân tử bất khả quy" cũng là một trong những bài toán khó nhất. Bài toán này mới chỉ được giải quyết trong một số trường hợp đặc biệt mà chưa có lời giải tổng quát. Mục tiêu của chương này là trình bày Thuật toán Berlekamp phân tích đa thức thành nhân tử trên trường hữu hạn và ứng dụng để phân tích đa thức thành nhân tử trên trường Q. 2.1 Trường phân rã của đa thức, trường hữu hạn Trong suốt tiết này luôn giả thiết K là một trường. Định nghĩa 2.1.1. (i) Nếu K là một trường con của E thì ta gọi E là một trường mở rộng của K, ký hiệu là E/K. (ii) Giả sử E/K là một mở rộng trường. Xem E là một không gian véc tơ trên K. Nếu E là K- không gian véc tơ hữu hạn chiều thì ta nói E là mở rộng bậc hữu hạn của trường K. Nếu dimK E = n thì n được gọi là bậc của mở rộng E/K và được ký hiệu là [E : K].
14 Chú ý 2.1.2. Chú ý rằng nếu E/K và K/F là các mở rộng hữu hạn, trong đó E, K, F là các trường thì [E : F] = [E : K][K : F]. Cho E/K là mở rộng trường và α ∈ E. Kí hiệu K(α) là giao của tất cả các trường con của E chứa K và α, khi đó K(α) là trường con bé nhất của E chứa K và α. Kí hiệu K[α] là giao của tất cả các vành con của E chứa K và α. Khi đó K[α] là vành con bé nhất của E chứa K và α. Rõ ràng K[α] ⊆ K(α). Chú ý 2.1.3. (Xem [1]). Cho E/K là mở rộng trường và α ∈ E. Khi đó (i) K[α] = {f (α) | f (x) ∈ K[x]}. f (α) (ii) K(α) = | f , g ∈ K[x], g(α) 6= 0 . g(α) (iii) Nếu α là đại số trên K (tức α là nghiệm của một đa thức khác 0 với hệ số trong K) thì K(α) = K[α]. (iv) Nếu α là siêu việt trên K (tức α không đại số trên K) thì K(α) ∼ = K[α]. Định nghĩa 2.1.4. Giả sử E/K là một mở rộng trường và f (x) ∈ K[x] là đa thức bậc n ≥ 1. Ta nói f (x) là phân rã trên E nếu f (x) = a(x − α1 )...(x − αn ) với a là hệ số cao nhất của f (x) và α1 , ..., αn ∈ E. Ta nói E là trường phân rã của f (x) trên K nếu f (x) phân rã trên E và không phân rã trên bất cứ trường con thực sự nào của E. Ví dụ 2.1.5. Cho đa thức f (x) = x3 − 7 ∈ Q[x]. Khi đó trường phân rã của √ √ f (x) trên Q là Q( 3 7, i). Ở đây ta kí hiệu Q( 3 7, i) là trường con bé nhất √ của trường số phức chứa 3 7 và i. Bổ đề 2.1.6. Với mọi đa thức f (x) ∈ K[x] bất khả quy trên trường K, tồn tại một trường E chứa K và chứa một nghiệm của f (x). Chứng minh. Xét vành thương T = K[x]/I, trong đó I là iđêan của K[x] sinh bởi f (x). Vì K[x] là một vành giao hoán nên T cũng là một vành giao hoán có đơn vị là 1 = 1 + I. Rõ ràng ta có 1 6= 0, ta sẽ chứng minh T là một
15 trường. Thật vậy, giả sử g(x) = g(x) + I là một phần tử khác không của T . Vì g(x) 6= 0 nên g(x) ∈ / I tức g(x) không chia hết cho f (x). Do f (x) bất khả quy trên K nên f (x) và g(x) nguyên tố cùng nhau. Vì vậy tồn tại các đa thức r(x), s(x) ∈ K[x] sao cho ta có f (x)r(x) + g(x)s(x) = 1. Lấy các lớp tương ứng trong vành thương ta được f (x).r(x) + g(x).s(x) = 1. Do f (x) = 0 nên g(x).s(x) = 1. Điều này chứng tỏ g(x) khả nghịch trong vành T . Vậy T là trường. Thiết lập ánh xạ ϕ : K → T cho bởi a 7→ a + I = a. Rõ ràng, ϕ là một đơn cấu trường. Vậy tập hợp {a ∈ T | a ∈ K} lập thành một trường con đẳng cấu với K. Nếu ta đồng nhất K với ϕ(K) bằng cách đồng nhất a ≡ a thì ta có thể xem K như là một trường con của trường T . Ngoài ra nếu f (x) = a0 + a1 x + ... + an xn thì ta có 0 = 0 = f (x) = a0 + a1 x + ... + an xn = a0 + a1 x + ... + an xn = f (x). Vậy phần tử x = x + I ∈ T là một nghiệm của đa thức f (x). Do đó tồn tại trường T chứa K và chứa một nghiệm của f (x) Định lý 2.1.7. Với mỗi đa thức f (x) ∈ K[x]) có bậc n ≥ 1, tồn tại một trường phân rã f (x) trên K. Chứng minh. Trước hết ta chứng minh sự tồn tại mở rộng trường E của K sao cho f (x) phân rã trên E. Ta chứng minh điều này bằng quy nạp theo n. Cho n = 1 thì f (x) = ax + b với a 6= 0, a, b ∈ K. Suy ra f (x) = a(x − α), trong đó α = −ba−1 ∈ K. Do đó chỉ việc chọn E = K. Cho n > 1 và giả thiết kết quả đã đúng cho các đa thức bậc nhỏ hơn n. Nếu f (x) bất khả quy thì theo Bổ đề 2.1.6, tồn tại một trường T chứa K và chứa một nghiệm α của f (x). Suy ra f (x) = (x − α)g(x) với g(x) ∈ T [x] có bậc là n − 1. Theo giả thiết quy nạp, có trường mở rộng E của K1 sao cho g(x) có đủ n − 1 nghiệm trong E. Do đó E là trường chứa K và chứa đủ n nghiệm của f (x). Giả sử f (x) không bất khả quy trên K. Khi đó f (x) = g(x)h(x) với deg h(x) = n1 < n và deg h(x) = n2 < n. Theo giả thiết quy nạp, tồn tại trường F chứa K và chứa đủ n1 nghiệm của g(x). Chú ý rằng h(x) ∈ F[x]. Do đó theo giả thiết quy nạp, tồn tại trường E chứa F và chứa đủ n2 nghiệm của h(x). Do đó E
16 là trường chứa K và chứa đủ n nghiệm. Vậy, khẳng định được chứng minh. Bây giờ ta chứng minh sự tồn tại của trường phân rã. Theo khẳng định trên, tồn tại trường E chứa K và chứa đủ n nghiệm α1 , ..., αn của f (x). Gọi K(α1 , . . . , αn ) là trường con bé nhất của E chứa K và α1 , . . . , αn . Khi đó K(α1 , . . . , αn ) chính là trường phân rã của đa thức f (x) trên K. Chú ý 2.1.8. (xem [1]). Trường phân rã của một đa thức trên một trường là tồn tại và duy nhất theo nghĩa nếu T và T 0 là hai trường phân rã trên K của đa thức f (x) ∈ K[x] thì T ∼ = T 0. Cho K là trường. Đặc số của K là số nguyên dương nhỏ nhất k (nếu tồn tại) sao cho k1 = 0, trong đó 1 ∈ K là phần tử đơn vị. Nếu không tồn tại số nguyên dương k thỏa mãn k1 = 0 thì ta nói K có đặc số 0. Chú ý rằng mỗi trường hoặc có đặc số 0 hoặc có đặc số là một số nguyên tố. Rõ ràng Q có đặc số 0 và nếu p nguyên tố thì thì trường Z p có đặc số p. Bổ đề 2.1.9. Nếu K là trường hữu hạn có q phần tử thì K có đặc số p nguyên tố và q là một lũy thừa của p. Chứng minh. Giả sử K có đặc số 0. Khi đó n1 6= m1 với mọi n 6= m. Do đó tập {n1 | n ∈ N} là một tập con vô hạn của K, vô lí. Do đó K có đặc số p nguyên tố. Xét ánh xạ ϕ : Z → K cho bởi ϕ(n) = n1. Khi đó ϕ là một đẳng cấu vành và Kerϕ = {k ∈ Z | k1 = 0} = pZ. Suy ra Z/pZ ∼ = Imϕ, tức là Z p ∼ = Imϕ ⊆ K. Do p nguyên tố nên Z p là trường. Vì thế K là một không gian véc tơ trên trường Z p . Do K có hữu hạn phần tử nên không gian này có chiều hữu hạn. Giả sử dimZ p K = d. Suy ra K có q = pd phần tử. Định lý 2.1.10. (i) Nếu p là số nguyên tố thì với mỗi số nguyên dương d, tồn tại một trường có đúng pd phần tử. (ii) Nếu K và T là hai trường hữu hạn cùng có q phần tử thì chúng có cùng đặc số p và đều là trường phân rã của đa thức g(x) = xq − x trên trường Z p . Hơn nữa, K ∼ = T. Chứng minh. (i) Đặt q = pd . Do p nguyên tố nên Z p là trường. Theo định lí trên, tồn tại một trường F chứa Z p và chứa các nghiệm của đa thức g(x) = xq − x ∈ Z p [x]. Đặt E = {α ∈ F | g(α) = 0}. Ta chứng minh E là