Tài liệu Về một số thuật toán phân tích đa thức một biến thành nhân tử

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC ------------------------------- DƢƠNG THỊ LAN HƢƠNG VỀ MỘT SỐ THUẬT TOÁN PHÂN TÍCH ĐA THỨC MỘT BIẾN THÀNH NHÂN TỬ 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 ------------------------------- DƢƠNG THỊ LAN HƢƠNG VỀ MỘT SỐ THUẬT TOÁN PHÂN TÍCH ĐA THỨC MỘT BIẾN THÀNH NHÂN TỬ 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: TS. Đoàn Trung Cƣờng THÁI NGUYÊN - 2016 i Mục lục Danh sách ký hiệu iii Mở đầu 1 Chương 1. Kiến thức chuẩn bị 4 1.1 Phân tích bất khả quy của đa thức . . . . . . . . . . . . . . . . . 4 1.2 Thuật toán chia đa thức . . . . . . . . . . . . . . . . . . . . . . . 7 Chương 2. Thu gọn mod p và đa thức bất khả quy 11 2.1 Thu gọn mod p và đa thức bất khả quy . . . . . . . . . . . . . . . 11 2.2 Tiêu chuẩn bất khả quy Eisenstein . . . . . . . . . . . . . . . . . 16 2.3 Trường hợp đa thức thu gọn P(X) không có nghiệm trong F p . . . 24 2.4 Bài tập đề nghị . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Chương 3. Một số thuật toán phân tích đa thức thành nhân tử 28 3.1 Phân tích đa thức thành nhân tử . . . . . . . . . . . . . . . . . . . 28 3.2 Thuật toán Yun phân tích không bình phương . . . . . . . . . . . 32 3.2.1 Phân tích không bình phương . . . . . . . . . . . . . . . 32 3.2.2 Thuật toán Yun . . . . . . . . . . . . . . . . . . . . . . . 35 Phân tích nhân tử của đa thức trên trường hữu hạn F p . . . . . . . 38 3.3.1 Thuật toán tổng quát . . . . . . . . . . . . . . . . . . . . 38 3.3.2 Phân tích tách bậc . . . . . . . . . . . . . . . . . . . . . 40 3.3.3 Phân tích đồng bậc . . . . . . . . . . . . . . . . . . . . . 42 Phân tích bất khả quy trên Z[X] . . . . . . . . . . . . . . . . . . . 44 3.3 3.4 ii 3.4.1 Chặn cho hệ số của các ước trong vành đa thức nguyên . . 44 3.4.2 Phân tích bất khả quy mod pe . . . . . . . . . . . . . . . 48 3.4.3 Thuật toán Zassenhaus . . . . . . . . . . . . . . . . . . . 51 Kết luận 54 Tài liệu tham khảo 55 iii Danh sách ký hiệu Z vành các số nguyên Q trường các số hữu tỷ Fp trường có p phần tử K[X] vành đa thức với hệ số trên trường K P(X) đa thức một biến X deg P(X) bậc của đa thức P(X) mod p modulo p a6| b a không là ước của b gcd(P(X), Q(X)) ước chung lớn nhất của hai đa thức P(X) và Q(X) 1 Mở đầu Đa thức là một khái niệm cơ sở của toán học. Một mặt đa thức là đối tượng nghiên cứu của đại số, một mặt chúng xuất hiện trong tất cả các lĩnh vực của toán học cũng như nhiều lĩnh vực khoa học khác. Các bài toán về đa thức xuất hiện cả trong toán phổ thông cũng như toán cao cấp. Trong toán phổ thông, những bài toán về đa thức thường là những bài toán khó, hay xuất hiện trong các kỳ thi học sinh giỏi, kể cả các kỳ thi Học sinh giỏi Quốc gia và Olympic Toán Quốc tế. Khi xét đa thức, một vấn đề được người ta quan tâm là tính bất khả quy và rộng hơn là phân tích của đa thức đó thành tích các đa thức bất khả quy. Tính chất này cũng tương tự như của các số nguyên là tính chất nguyên tố và phân tích thành tích các số nguyên tố. Các câu hỏi về tính bất khả quy và phân tích bất khả quy của đa thức nói chung là khó trả lời hơn nhiều. Do vậy, việc hệ thống lại một số tiêu chuẩn về đa thức bất khả quy và nghiên cứu một số thuật toán phân tích đa thức một biến (với hệ số nguyên) thành nhân tử là cần thiết. Với lý do như vậy, chúng tôi chọn đề tài “Về một số thuật toán phân tích đa thức một biến thành nhân tử”. Khác với các số nguyên, một thuật toán để phân tích một đa thức nguyên thành tích các đa thức nguyên bất khả quy là không hiển nhiên. Nếu xét đa thức với hệ số trên một trường hữu hạn thì việc phân tích sẽ khả thi hơn, vì chỉ có hữu hạn đa thức có bậc nhỏ hơn bậc của một đa thức cho trước. Với các đa thức hệ số nguyên, những thuật toán phân tích đa thức thành nhân tử mà hiệu quả (về mặt tính toán) đều đưa đa thức về xét trên trường hữu hạn, sau đó nâng phân tích tìm được lên lại vành các số nguyên. Trong luận văn này, chúng tôi trình bày một số thuật toán phân tích một đa thức thành tích các nhân tử bất khả quy, trong đó xét các trường hợp đa thức nguyên, 2 đa thức có hệ số trên một trường hữu hạn F p . Nội dung chính 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 về tiêu chuẩn đa thức bất khả quy thông qua thu gọn mod p (reduction mod p) và các thuật toán phân tích đa thức một biến thành nhân tử bất khả quy như thuật toán Kronecker, thuật toán Yun, thuật toán Zassenhaus. Nội dung của luận văn được trình bày trong ba chương: Chương 1. Kiến thức chuẩn bị. Trong chương này chúng tôi trình bày các kiến thức cơ sở chuẩn bị cho các chương sau như định lý phân tích đa thức thành nhân tử, bổ đề Gauss, thuật toán chia đa thức và thuật toán tìm ước chung lớn nhất của hai đa thức. Chương 2. Thu gọn mod p và đa thức bất khả quy. Chúng tôi trình bày việc xét tính chất bất khả quy của một đa thức nguyên thông qua thu gọn mod p với p là một số nguyên tố. Kết quả chính được trình bày là tiêu chuẩn bất khả quy Eisenstein và các mở rộng của nó. Các tiêu chuẩn này được trình bày rất ngắn gọn thông qua thu gọn mod p. Chương 3. Một số thuật toán phân tích đa thức thành nhân tử. Trong chương này chúng tôi trình bày thuật toán Kronecker để phân tích một đa thức nguyên thành nhân tử. Đây là thuật toán đầu tiên để phân tích đa thức nguyên, tuy nhiên chỉ có ý nghĩa lý thuyết do về mặt tính toán thì rất không hiệu quả. Tiếp theo chúng tôi trình bày thuật toán Yun để phân tích một đa thức thành các ước không chứa bình phương. Thuật toán tiếp theo chúng tôi trình bày là phân tích các đa thức với hệ số trên trường hữu hạn thành nhân tử. Ý tưởng của các thuật toán này được sử dụng trong thuật toán Zassenhaus, trình bày trong phần cuối cùng của Chương 3, để phân tích một đa thức nguyên thành tích các đa thức nguyên bất khả quy. Ý tưởng của thuật toán này là chuyển việc xét đa thức nguyên về xét trên trường F p , sau đó sử dụng thuật toán trước để phân tích đa thức thành tích các đa thức bất khả quy trên F p . Cuối cùng, sử dụng một dạng của Bổ đề Hensel để nâng phân tích này lên trên Z. 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 3 Nguyên và hoàn thành với sự hướng dẫn của TS. Đoàn Trung Cường (Viện Toán học - Viện Hàn lâm Khoa học và Công nghệ Việt Nam). 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ả muốn gửi những lời cảm ơn tốt đẹp nhất tới tập thể Lớp B, cao học Toán khóa 8 (2014-2016) đã động viên và giúp đỡ tác giả rất nhiều trong suốt quá trình học tập. Nhân dịp này, tác giả cũng xin chân thành cảm ơn Sở Giáo dục và Đào tạo Hải Phòng, Ban Giám hiệu và các đồng nghiệp ở Trường THPT Lê Hồng Phong, 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. Cuối cùng, tác giả muốn dành những lời cảm ơn đặc biệt nhất đến bố mẹ và đại gia đình đã luôn động viên và chia sẻ những khó khăn để tác giả hoàn thành tốt luận văn này. Thái Nguyên, ngày 20 tháng 5 năm 2016 Tác giả Dương Thị Lan Hương 4 Chương 1 Kiến thức chuẩn bị Mục đích của chương này là nhắc lại một số kiến thức chuẩn bị cần thiết cho việc trình bày các kết quả trong các chương sau. Nội dung của chương là chúng tôi nhắc lại một số định lí về đa thức bất khả quy và phân tích bất khả quy, thuật toán chia đa thức, thuật toán tìm ước chung lớn nhất của hai đa thức. Hầu hết các kết quả trong chương này được trình bày dựa theo tài liệu [2]. 1.1 Phân tích bất khả quy của đa thức Trong tiết này, chúng ta nhắc lại một số kết quả về đa thức bất khả quy và sự tồn tại phân tích bất khả quy. Nhắc lại, một đa thức khác hằng với hệ số trên một trường là bất khả quy nếu nó không phân tích được thành tích của hai đa thức có bậc nhỏ hơn. Ví dụ, mọi đa thức bậc nhất aX + b, với a 6= 0, đều là bất khả quy. Tính chất bất khả quy của một đa thức phụ thuộc vào trường hệ số được xét. Ví dụ, đa thức P(X) = X 2 + 1 là đa thức bất khả quy trong R[X] nhưng là đa thức khả quy trong C[X] vì P(X) = (X − i)(X + i). Để xét tính chất bất khả quy của một đa thức, ta hay dùng bổ đề đơn giản sau để biến đổi đa thức về dạng mà ta có thể áp dụng một số tiêu chuẩn bất khả quy đã biết. Bổ đề 1.1.1. Cho đa thức P(X) với hệ số trên một trường K. Với mỗi a ∈ K, đa thức P(X) là bất khả quy khi và chỉ khi đa thức P(X + a) là bất khả quy. 5 Chứng minh. Trước hết nhận xét rằng deg P(X) = deg P(X + a). Ngoài ra, một phân tích P(X) = H(X)K(X) tương đương với một phân tích P(X + a) = H(X + a)K(X + a). Vì vậy P(X) là khả quy khi và chỉ khi P(X + a) là khả quy. Hai đa thức P(X), Q(X) được gọi là liên hợp nếu P(X) = λ Q(X) với một hằng số λ 6= 0 nào đó. Định lí 1.1.2 (Phân tích thành nhân tử). Giả sử K là một trường. Khi đó mọi đa thức P(X) ∈ K[X] khác hằng đều có phân tích P(X) = P1α1 . . . Prαr với Pi ∈ K[X] là đa thức bất khả quy đôi một không liên hợp, α1 , . . . , αr > 0. Hơn nữa phân tích này là duy nhất sai khác một thứ tự của các ước bất khả quy. Với đa thức nguyên, ta cũng định nghĩa một đa thức nguyên khác hằng là bất khả quy nếu nó không phân tích được thành tích hai đa thức có bậc nhỏ hơn. Với định nghĩa này thì đa thức nguyên bất khả quy không là một phần tử bất khả quy trong vành Z[X] như định nghĩa thông thường. Ví dụ, đa thức nguyên 2X + 4 = 2(X + 2) vẫn là đa thức bất khả quy theo định nghĩa trên. Trong toàn bộ luận văn này ta sẽ sử dụng định nghĩa đa thức nguyên bất khả quy này. Một đa thức nguyên cũng là một đa thức hữu tỷ (có hệ số trên trường các số hữu tỷ Q). Liên hệ giữa tính chất bất khả quy trên Z và trên Q được thể hiện trong định lý nổi tiếng sau, thường gọi là Bổ đề Gauss. Định lí 1.1.3 (Bổ đề Gauss). Cho một đa thức nguyên P(X) khác hằng. Giả sử có phân tích P(X) = G(X)F(X) với G(X), F(X) là các đa thức có hệ số hữu tỷ. Khi đó tồn tại các đa thức nguyên G∗ (X), F∗ (X) sao cho deg G(X) = deg G∗ (X), deg F(X) = deg F∗ (X) và P(X) = G∗ (X)F∗ (X). Nói riêng, nếu P(X) là khả quy trên Q thì nó phân tích được thành tích của hai đa thức với hệ số nguyên có bậc thấp hơn. 6 Chứng minh. Viết F(X) = aF1 (X) và G(X) = bG1 (X) trong đó a, b ∈ Q và F1 (X), G1 (X) ∈ Z[X] là các đa thức nguyên mà hệ số có ước chung lớn nhất bằng 1 (thường gọi là các đa thức nguyên bản). Rõ ràng P(X) = abF1 (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 X n + . . . + 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ó ra1 ra0 ran ,..., , ∈ 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) = abF1 (X) và G∗ (X) = G1 (X). Khi đó, P(X) = F∗ (X)G∗ (X) với F∗ (X) và G∗ (X) có hệ số nguyên, deg F(X) = deg F∗ (X) và deg G( X) = deg G∗ (X). Như vậy với một đa thức nguyên thì tính chất bất khả quy trên Z và trên Q là tương đương. Tương tự như định lý phân tích duy nhất của các đa thức với hệ số trên một trường, ta có định lý phân tích cho đa thức nguyên. Nhắc lại là một đa thức nguyên được gọi là đa thức nguyên bản (primitive) nếu các hệ số của đa thức đó có ước chung lớn nhất là 1. Định lí 1.1.4 (Phân tích thành nhân tử). Mọi đa thức nguyên khác hằng đều có phân tích duy nhất P(X) = λ P1α1 . . . Prαr , trong đó λ ∈ Z, P1 , . . . , Pr là các đa thức nguyên bản bất khả quy đôi một không liên hợp và α1 , . . . , αr > 0. Hơn nữa, một phân tích như vậy là duy nhất sai khác thứ tự của các nhân tử bất khả quy. 7 1.2 Thuật toán chia đa thức Trong các tính toán trên các đa thức, thuật toán chia Euclid đóng vai trò then chốt. Từ thuật toán này người ta dẫn đến các thuật toán cơ bản khác như tìm ước chung lớn nhất, tìm bội chung nhỏ nhất, ... Trong các thuật toán phân tích đa thức thành nhân tử mà ta xét ở phần sau, thuật toán chia đa thức và tìm ước chung nhỏ nhất thường xuyên được dùng. Trong tiết này ta nhắc lại thuật toán này. Trong các tiết sau ta sẽ không nhắc lại mà sử dụng như một thuật toán cơ sở đã biết. Giả sử K là một trường. Cho F(X), G(X) là hai đa thức với hệ số trên K, trong đó G(X) 6= 0. Khi đó luôn tồn tại duy nhất hai đa thức Q(X) và R(X) sao cho F(X) = G(X)Q(X) + R(X), trong đó deg R(X) < deg G(X). Để tìm các đa thức thương Q(X) và dư R(X) ta thực hiện như sau: Nếu F(X) = 0 hoặc deg F(X) < deg G(X) thì ta chọn Q(X) = 0 và R(X) = F(X). Giả sử F(X) 6= 0 và deg F(X) ≥ deg G(X). Đặt deg F(x) = n và deg G(X) = m. Giả sử am , bm lần lượt là hệ số cao nhất của F(X), G(X). Vì K là trường nên tồn tại phần tử b−1 m ∈K −1 n−m . Đặt F (X) = F(X) − G(X)H(X). sao cho bm b−1 1 m = 1. Chọn H(X) = am bm x Khi đó F1 (X) = 0 hoặc deg F1 (X) < deg F(X). Nếu F1 (X) = 0 hoặc deg F1 (X) < deg G(X) thì dư của phép chia là R(X) = F1 (X) và thương là Q(X) = H(X). Nếu F1 (X) 6= 0 và deg F1 (X) ≥ deg G(X) thì ta tiếp tục làm tương tự đối với cặp đa thức F1 (X) và G(X) và ta được đa thức F2 (X) và H1 (X) thỏa mãn F2 (X) = F1 (X) − G(X)H(X), trong đó F2 (X) = 0 hoặc deg F2 (X) < deg F1 (X). Cứ tiếp tục quá trình này, ta thu được dãy F1 (X), F2 (X), . . . , Fk−1 (X) gồm các đa thức khác 0 với bậc giảm dần. Các bậc này không thể giảm mãi nên quá trình phải dừng tại một bước k nào đó, khi mà Fk (X) là đa thức đầu tiên hoặc bằng 0 hoặc có bậc bé hơn bậc của G(X). Thuật toán trên được gọi là thuật toán chia Eulid. Các bước của thuật toán cụ thể là 8 F1 (X) = F(X) − G(X)H(X), F2 (X) = F1 (X) − G(X)H1 (X), deg F(X) > deg F1 (X) ≥ deg G(X) deg F1 (X) > deg F2 (X) ≥ deg G(X) ... Fk−1 (X) = Fk−2 (X) − G(X)Hk−2 (X), deg Fk−2 (X) > deg Fk−1 (X) ≥ deg G(X) Fk (X) = Fk−1 (X) − G(X)Hk−1 (X), với Fk (X) = 0 hoặc deg Fk (X) < deg G(X). Cộng từng vế với vế các đẳng thức đó lại ta được   F(X) = G(X) H(X) + H1 (X) + . . . + Hk−1 (X) + Fk (X). Đặt Q(X) = H(X) + H1 (X) + . . . + Hk−1 (X) và R(X) = Fk (X) ta có kết quả. Ví dụ 1.2.1. Trên trường Q, ta xét F(X) = −2X 3 − 14X 2 + 4X − 3 và G(X) = −2X 2 + 2X − 1. Ta thực hiện phép chia F(X) cho G(X) như sau: F1 (X) = F(X) − XG(X) = −16X 2 + 5X − 3. F2 (X) = F1 (X) − 8G(X) = −11X + 5. Thuật toán dừng lại ở đây vì deg F2 (X) = 1 < 2 = deg G(X). Do đó F(X) = (X + 8)G(X) − 11X + 5. Vậy, thương của phép chia là Q(X) = X + 8 và dư là R(X) = −11X + 5. Chú ý 1.2.2. Với các đa thức nguyên không phải lúc nào ta cũng chia được hai đa thức cho nhau. Ví dụ không thể chia P(X) = X 1 + 1 cho đa thức Q(X) = 2X + 4 để nhận được các đa thức thương Q(X) và đa thức dư R(X) cũng là đa thức nguyên. Tuy nhiên, nếu hệ số bậc cao nhất của Q(X) bằng 1 hoặc −1 thì ta vẫn sử dụng được thuật toán Euclid như ở trên để tìm thương và dư khi chia một đa thức cho Q(X). Tiếp theo ta xét thuật toán tìm ước chung lớn nhất của hai đa thức. Nhắc lại là trên một trường K, ước chung lớn nhất của hai đa thức F, G 6= 0 là đa thức R có bậc lớn nhất sao cho R chia hết F, G. Nếu R là ước chung lớn nhất của F, G thì λ R, với 9 λ 6= 0 ∈ K, cũng là ước chung lớn nhất. Do đó ước chung lớn nhất của hai đa thức là không duy nhất. Tuy nhiên, ước chung lớn nhất với hệ số bậc cao nhất bằng 1 (đa thức monic) là duy nhất và thường được ký hiệu là gcd(F(X), G(X)). Để tìm ước chung lớn nhất của hai đa thức, ta có định lý sau đây. Định lí 1.2.3 (Thuật toán Euclid tìm ước chung lớn nhất). Giả sử F(X), G(X) là hai đa thức với hệ số trên một trường K và G(X) 6= 0. Khi đó tồn tại số tự nhiên k và các đa thức Ri (X), Qi (X) ∈ K[X] sao cho F(X) = G(X)Q0 (X) + R0 (X), R0 (X) 6= 0, deg R0 (X) < deg G(X); G(X) = R0 (X)Q1 (X) + R1 (X), R1 (X) 6= 0, deg R1 (X) < deg R0 (X); R0 (X) = R1 (X)Q2 (X) + R2 (X), R2 (X) 6= 0, deg R2 (X) < deg R1 (X); ... Rk−2 (X) = Rk−1 (X)Qk (X) + Rk (X), Rk (X) 6= 0, deg Rk (X) < deg Rk−1 (X); Rk−1 (X) = Rk (X)Qk+1 (X). Hơn nữa đa thức dư cuối cùng Rk (X) 6= 0 là một ước chung lớn nhất của F(X) và G(X). Để chứng minh định lý trên, ta nêu ra không chứng minh một kết quả dưới dạng bổ đề như sau: Bổ đề 1.2.4. Giả sử F(X) = G(X)Q(X) + R(X) trong đó hoặc R(X) = 0 hoặc R(X) 6= và deg R(X) < deg G(x). Khi đó mỗi ước chung lớn nhất của F(X) và G(X) là một ước chung lớn nhất của G(X) và R(X). Chứng minh Định lý 1.2.3. Chia F(X) cho G(X) ta được thương Q0 (X) và dư R0 (X). Nếu R0 6= 0 thì chia G(X) cho R0 (X) ta được thương Q1 (X) và dư R1 (X). Nếu R1 (X) 6= 0 thì chia R0 (X) cho R1 (X) ta được thương Q2 (X) và dư là R2 (X). Cứ tiếp tục quá trình trên, quá trình này phải dừng lại sau một số hữu hạn bước vì dãy giảm các số tự nhiên deg G(X) > deg R0 (X) deg R1 (X) > · · · 10 không thể kéo dài vô hạn. Từ Bổ đề 1.2.4 ta suy ra ước chung lớn nhất của F(X) và G(X) là Rk (X). Ví dụ 1.2.5. Để tìm ước chung lớn nhất của các đa thức X 6 − 1, X 4 − 1 và X 3 − 3X + 2, trước hết ta tìm ước chung lớn nhất của X 6 − 1 và X 4 − 1. Ta có X 6 − 1 = X 2 (X 4 − 1) + X 2 − 1, X 4 − 1 = (X 2 + 1)(X 2 − 1) Theo thuật toán Eucid, ước chung lớn nhất của X 6 − 1 và X 4 − 1 là X 2 − 1. Ta tiếp tục tìm ước chung lớn nhất của X 2 − 1 và X 3 − 3X + 2. Ta có X 3 − 3X + 2 = (X 2 − 1)X − 2X + 2,   X 1 2 X − 1 = (−2X + 2) − − . 2 2 Do đó −2X + 2 là một ước chung lớn nhất của X 2 − 1 và X 3 − 3X + 2. Vì thế −2X + 2 là một ước chung lớn nhất của X 3 − 3X + 2, X 4 − 1 và X 6 − 1. 11 Chương 2 Thu gọn mod p và đa thức bất khả quy Kiểm tra tính chất bất khả quy là một phần của bài toán phân tích một đa thức thành nhân tử. Mục đích của chương này 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 về tiêu chuẩn đa thức bất khả quy thông qua thu gọn mod p, tiêu chuẩn bất khả quy Eisenstein và một số mở rộng có minh họa bằng các ví dụ. 2.1 Thu gọn mod p và đa thức bất khả quy Một trong những cách kiểm tra tính bất khả quy của một đa thức nguyên khá hữu hiệu là sử dụng thu gọn mod p, với p là một số nguyên tố. Nghĩa là thay cho việc kiểm tra trực tiếp với đa thức nguyên P(X), ta kiểm tra trước hết cho đa thức thu gọn P(X) modulo một số nguyên tố p nào đó. Phương pháp kiểm tra này dựa trên nhận xét sau. Bổ đề 2.1.1. Cho một đa thức nguyên bản P(X) và một số nguyên tố p. Giả sử p không là ước của hệ số bậc cao nhất của P(X). Nếu P(X) là khả quy trên Z thì đa thức tương ứng P(X) là khả quy trên trên trường F p . Chứng minh. Giả sử P(X) = an X n + an−1 X n−1 + . . . + a1 X + a0 , với deg P = n. Đa thức tương ứng của P(X) trên F p là P(X) = an X n + an−1 X n−1 + . . . + a1 X + a0 . 12 Theo giả thiết, P(X) được phân tích thành P(X) = H(X)K(X), với 0 < deg H(X), deg K(X) < n. Do đó, xét mod p, trên trường F p ta có P(X) = H(X)K(X), nên P(X) phân tích được thành tích hai đa thức. Vì p 6 | an nên ān 6= 0 trong F p do đó deg P(X) = n. Ngoài ra, do deg H(X) ≥ deg H(X), deg K(X) ≥ deg K(X) mà deg H(X) + deg K(X) = deg P(X) = deg P(X) = deg H(X) + deg K(X), nên deg H(X) = deg H(X) < n, deg K(X) = deg K(X) < n. Vậy đa thức P(X) khả quy trên trường F p . Như vậy để xét tính bất khả quy của một đa thức nguyên, ta có thể trước hết xét tính chất bất khả quy của đa thức thu gọn tương ứng mod p với p là một số nguyên tố thích hợp. Việc xét tính chất bất khả quy của một đa thức trên một trường hữu hạn có nhiều thuận lợi. Ví dụ, trên F p chỉ có hữu hạn đa thức có bậc nhỏ hơn số n cho trước. Trong trường hợp đa thức có bậc nhỏ, ta có thể kiểm tra tính bất khả quy thông qua việc tìm nghiệm đa thức như sau. Bổ đề 2.1.2. Cho một đa thức nguyên P(X) có bậc deg P(X) ≤ 3 và một số nguyên tố p. Khi đó P(X) là bất khả quy trên F p khi và chỉ khi P(X) có một nghiệm trong F p. Chứng minh. Điều kiện cần. Giả sử đa thức P(X) có dạng P(X) = a3 X 3 + a2 X 2 + a1 X + a0 với a3 6= 0. Theo giả thiết thì đa thức P(X) khả quy trên F p . Suy ra P(X) = H(X)K(X) với 0 < deg H(X), deg K(X) < 3 và deg H(X) + deg K(X) = 3. Do đó, hoặc deg H(X) = 1, hoặc deg K(X) = 1. 13
Giả sử deg H(X) = 1, hay H(X) = b1 X +b0 với b1 6= 0. Ta có P(X) = b1 X + b0 K(X), nên đa thức P(X) có nghiệm X = − bb0 . 1 Điều kiện đủ. Giả sử P(X) có một nghiệm trên F p là X = X0 . Khi đó ta có thể viết P(X) = (X − X0 )Q(X) với 0 < deg Q(X) ≤ 2. Như vậy đa thức P(X) khả quy trên F p. Ví dụ 2.1.3. Đa thức P(X) = X 5 + 7X 2 + 11 là bất khả quy. Xét thu gọn mod 2, ta có P(X) = X 5 + X 2 + 1. Ta có P(0̄) = 1̄, P(1̄) = 1̄ nên P(X) 6= 0 với mọi X ∈ F2 . Dẫn đến P(X) không có nghiệm trong trường F2 . Vì P(X) không có nghiệm trên F2 nên nếu P(X) khả quy trên F2 thì P(X) phải có phân tích dạng P(X) = (X 2 + a1 X + a0 )(X 3 + b2 X 2 + b1 X + b0 ) = X 5 + (b2 + a1 )X 4 + (a0 + a1 b2 + b1 )X 3 + (a0 b2 + b0 + a1 b1 )X 2 +(a0 b1 + a1 b0 )X + a0 b0 . Suy ra b2 + a1 = 0 (2.1) a0 + a1 b2 + b1 = 0 (2.2) a0 b1 + b0 + a1 b1 = 1 (2.3) a0 b1 + a1 b0 = 0 (2.4) a0 b0 = 1 (2.5) Từ (2.5) suy ra a0 = 1 và b0 = 1, kéo theo b2 + a1 = 0, (2.6) 14 1 + a1 b2 + b1 = 0, (2.7) b1 + a1 b1 = 0, (2.8) b1 + a1 = 0. (2.9) Từ (2.8) ta có b1 = 0 hoặc a1 = −1. Với b1 = 0, suy ra b2 + a1 = 0, 1 = 0, a1 = 0. Điều này là vô lý. Với a1 = −1, suy ra b2 + a1 = 0, 1 − b2 + 1 = 0, b1 = 1. Hệ này tương đương với 0 − 1 = 0, b2 = 0, b1 = 1, điều này cũng là là vô lý. Do đó hệ phương trình (2.1)-(2.5) là vô nghiệm. Vậy đa thức P(X) là bất khả quy trên F2 . Từ Bổ đề 2.1.1 suy ra P(X) là đa thức bất khả quy. Ví dụ 2.1.4. Với mỗi số nguyên n không là bội của 5, đa thức P(X) = X 5 − X + n là bất khả quy. Theo giả thiết 5 6 | n nên n 6= 0. Xét thu gọn mod 5 P(X) = X 5 − X + n. Giả sử P(X) khả quy trên F5 , hay P(X) có phân tích P(X) = H(X)K(X), với 0 < deg H(X) ≤ deg K(X) < 5. Có hai trường hợp xảy ra deg H(X) = 1, deg K(X) = 4 (2.10) deg H(X) = 2, deg K(X) = 3. (2.11) hoặc Trường hợp 1. Ta có P(X) = (X + a)Q(X). (2.12)  Suy ra X = −a là một nghiệm của P(X) trong F5 . Vậy x ∈ 0, 1, 2, 3, 4 , thay vào P(X) ta được P(0) = P(1) = P(2) = P(3) = P(4) = n 6= 0. Vô lý. Suy ra đa thức P(X) không có nghiệm trong F5 . 15 Trường hợp 2. Ta viết P(X) = (X 2 + a1 X + a0 )(X 3 + b2 X 2 + b1 X + b0 ) = X 5 + (b2 + a1 )X 4 + (b1 + a1 + a1 b2 )X 3 +(b0 + a1 b1 + a0 b2 )X 2 + (a1 b0 + a0 b1 )X + a0 b0 Suy ra b2 + a1 = 0, (2.13) a1 + a1 b2 + b1 = 0, (2.14) a0 b2 + b0 + a1 b1 = 0, (2.15) a0 b1 + a1 b0 = −1, (2.16) a0 b0 = n. (2.17) Từ (2.13) suy ra b2 = −a1 thay vào (2.14), (2.15), (2.16), (2.17). Từ (2.14) suy ra b1 = a1 2 − a0 . Từ (2.15) suy ra b0 = −a1 3 + 2a0 a1 . Vậy ta có hệ phương trình   −a1 4 + 3a0 a1 2 − a0 2 = −1  2a0 2 a1 − a1 3 a0 = n. Theo Định lí Fermat nhỏ trên F5 , ta có a1 5 ≡ a1 . Suy ra a1 = 0 hoặc a1 6= 0. Nếu a1 = 0 thì từ phương trình thứ hai suy ra n = 0 (điều này vô lý). Nếu a1 6= 0 thì a1 5 = a1 kéo theo a1 4 = 1. Suy ra 3a0 a1 2 − a0 2 = 0. Giải phương trình này ta được a0 = 0 hoặc là a0 = 3a1 2 . Suy ra n = 0 (vô lý). Như vậy P(X) bất khả quy trên F5 . Từ Bổ đề 2.1.1 suy ra P(X) là đa thức bất khả quy.