Luận văn Về một số thuật toán phân tích đa thức một biến thành nhân tử

KHOA HỌC: TS. Đoàn Trung Cƣờng THÁI NGUYÊN - 2016 iMụ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 Fp . . . 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 3.3 Phân tích nhân tử của đa thức trên trường hữu hạn Fp . . . . . . . 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 3.4 Phân tích bất khả quy trên Z[X ] . . . . . . . . . . . . . . . . . . . 44 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 degP(X) bậc của đa thức P(X) mod p modulo p a 6 | 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) 1Mở đầ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 Fp. 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 Fp, 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 Fp. 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 3Nguyê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 4Chươ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) = X2+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. 5Chứng minh. Trước hết nhận xét rằng degP(X) = degP(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) = Pα11 . . .P αr 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 degG(X) = degG∗(X), degF(X) = degF∗(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. 6Chứ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) = anXn+ . . .+a1X+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 s , . . . , ra1 s , ra0 s ∈ Z. 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, degF(X) = degF∗(X) và degG(X) = degG∗(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) = λPα11 . . .P αr 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. 71.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 đó degR(X)< degG(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 degF(X)< degG(X) thì ta chọnQ(X)= 0 và R(X)=F(X). Giả sử F(X) 6= 0 và degF(X)≥ degG(X). Đặt degF(x) = n và degG(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−1m ∈ K sao cho bmb−1m = 1. Chọn H(X) = amb−1m xn−m. Đặt F1(X) = F(X)−G(X)H(X). Khi đó F1(X)= 0 hoặc degF1(X)< degF(X). Nếu F1(X)= 0 hoặc degF1(X)< degG(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à degF1(X) ≥ degG(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 degF2(X)< degF1(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à 8F1(X) = F(X)−G(X)H(X), degF(X)> degF1(X)≥ degG(X) F2(X) = F1(X)−G(X)H1(X), degF1(X)> degF2(X)≥ degG(X) . . . Fk−1(X) = Fk−2(X)−G(X)Hk−2(X), degFk−2(X)> degFk−1(X)≥ degG(X) Fk(X) = Fk−1(X)−G(X)Hk−1(X), với Fk(X) = 0 hoặc degFk(X)< degG(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) = −2X3− 14X2+ 4X − 3 và G(X) = −2X2+2X−1. Ta thực hiện phép chia F(X) cho G(X) như sau: F1(X) = F(X)−XG(X) =−16X2+5X−3. F2(X) = F1(X)−8G(X) =−11X+5. Thuật toán dừng lại ở đây vì degF2(X) = 1< 2= degG(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) = X1+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, degR0(X)< degG(X); G(X) = R0(X)Q1(X)+R1(X), R1(X) 6= 0, degR1(X)< degR0(X); R0(X) = R1(X)Q2(X)+R2(X), R2(X) 6= 0, degR2(X)< degR1(X); . . . Rk−2(X) = Rk−1(X)Qk(X)+Rk(X), Rk(X) 6= 0, degRk(X)< degRk−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à degR(X) < degG(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 degG(X)> degR0(X)degR1(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 X6− 1, X4− 1 và X3− 3X+2, trước hết ta tìm ước chung lớn nhất của X6−1 và X4−1. Ta có X6−1= X2(X4−1)+X2−1, X4−1= (X2+1)(X2−1) Theo thuật toán Eucid, ước chung lớn nhất của X6−1 và X4−1 là X2−1. Ta tiếp tục tìm ước chung lớn nhất của X2−1 và X3−3X+2. Ta có X3−3X+2= (X2−1)X−2X+2, X2−1= (−2X+2) ( −X 2 − 1 2 ) . Do đó −2X + 2 là một ước chung lớn nhất của X2− 1 và X3− 3X + 2. Vì thế −2X+2 là một ước chung lớn nhất của X3−3X+2, X4−1 và X6−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 Fp. Chứng minh. Giả sử P(X) = anXn+an−1Xn−1+ . . .+a1X+a0, với degP= n. Đa thức tương ứng của P(X) trên Fp là P(X) = anXn+an−1Xn−1+ . . .+a1X+a0. 12 Theo giả thiết, P(X) được phân tích thành P(X) = H(X)K(X), với 0< degH(X), degK(X)< n. Do đó, xét mod p, trên trường Fp 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 a¯n 6= 0 trong Fp do đó degP(X) = n. Ngoài ra, do degH(X) ≥ degH(X), degK(X)≥ degK(X) mà degH(X)+degK(X) = degP(X) = degP(X) = degH(X)+degK(X), nên degH(X) = degH(X)< n, degK(X) = degK(X)< n. Vậy đa thức P(X) khả quy trên trường Fp. 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 Fp 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 degP(X)≤ 3 và một số nguyên tố p. Khi đó P(X) là bất khả quy trên Fp khi và chỉ khi P(X) có một nghiệm trong Fp. Chứng minh. Điều kiện cần. Giả sử đa thức P(X) có dạng P(X) = a3X3+a2X2+a1X+a0 với a3 6= 0. Theo giả thiết thì đa thức P(X) khả quy trên Fp. Suy ra P(X) =H(X)K(X) với 0< degH(X), degK(X)< 3 và degH(X)+degK(X) = 3. Do đó, hoặc degH(X) = 1, hoặc degK(X) = 1. 13 Giả sử degH(X)= 1, hayH(X)= b1X+b0 với b1 6= 0. Ta có P(X)= ( b1X+b0 ) K(X), nên đa thức P(X) có nghiệm X =−b0 b1 . Điều kiện đủ. Giả sử P(X) có một nghiệm trên Fp là X = X0. Khi đó ta có thể viết P(X) = (X−X0)Q(X) với 0< degQ(X)≤ 2. Như vậy đa thức P(X) khả quy trên Fp. Ví dụ 2.1.3. Đa thức P(X) = X5+7X2+11 là bất khả quy. Xét thu gọn mod 2, ta có P(X) = X5+X2+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) = (X2+a1X+a0)(X3+b2X2+b1X+b0) = X5+(b2+a1)X4+(a0+a1b2+b1)X3+(a0b2+b0+a1b1)X2 +(a0b1+a1b0)X+a0b0. Suy ra b2+a1 = 0 (2.1) a0+a1b2+b1 = 0 (2.2) a0b1+b0+a1b1 = 1 (2.3) a0b1+a1b0 = 0 (2.4) a0b0 = 1 (2.5) Từ (2.5) suy ra a0 = 1 và b0 = 1, kéo theo b2+a1 = 0, (2.6) 14 1+a1b2+b1 = 0, (2.7) b1+a1b1 = 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) = X5−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) = X5−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< degH(X)≤ degK(X)< 5. Có hai trường hợp xảy ra degH(X) = 1, degK(X) = 4 (2.10) hoặc degH(X) = 2, degK(X) = 3. (2.11) 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) = (X2+a1X+a0)(X3+b2X2+b1X+b0) = X5+(b2+a1)X4+(b1+a1+a1b2)X3 +(b0+a1b1+a0b2)X2+(a1b0+a0b1)X+a0b0 Suy ra b2+a1 = 0, (2.13) a1+a1b2+b1 = 0, (2.14) a0b2+b0+a1b1 = 0, (2.15) a0b1+a1b0 =−1, (2.16) a0b0 = 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 = a12−a0. Từ (2.15) suy ra b0 =−a13+2a0a1. Vậy ta có hệ phương trình−a1 4+3a0a12−a02 =−1 2a02a1−a13a0 = n. Theo Định lí Fermat nhỏ trên F5, ta có a15 ≡ 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ì a15 = a1 kéo theo a14 = 1. Suy ra 3a0a12−a02 = 0. Giải phương trình này ta được a0 = 0 hoặc là a0 = 3a12. 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. 16 Một mặt phương pháp thu gọn mod p khá hữu hiệu để kiểm tra một số đa thức có là bất khả quy hay không, một mặt ta cần chú ý rằng phương pháp này không phải lúc nào cũng áp dụng được, ít nhất là áp dụng trực tiếp. Trong ví dụ sau đây ta sẽ thấy có đa thức nguyên bất khả quy đồng thời là khả quy trên mọi trường Fp. Ví dụ 2.1.5. Xét đa thức P(X) = X4+1. Dễ dàng chứng minh trực tiếp (bằng định nghĩa) P(X) là một đa thức nguyên bất khả quy. Xét một số nguyên tố p và ta tìm hiểu phân tích của P(X) trên Fp. Với p= 2 ta có P(X) = (X+1)4. Với p= 3 thì P(X) = (X2+X+2)(X2−X+2). Nhận xét là luôn có một trong các số −1, 2, −2 là bình phương trong trường Fp, nghĩa là số đó có dạng x2 với một phần tử x ∈ Fp nào đó. Thật vậy, ký hiệu A = {a ∈ Fp : a 6= 0} và B = { a2 ∈ Fp : a 6= 0 } . Khi đó B ⊆ A là một nhóm con. Vì a2 = b2 tương đương với a = ±b nên |B| = |A| hoặc |B| = |A|2 . Do đó, A/B có cấp 1 hoặc 2. Nói riêng, nếu a, b ∈ A\B thì ab ∈ B. Như vây, nếu −1, 2 không là bình phương thì −2 = (−1) ·2 phải là bình phương. Sử dụng nhận xét này, ta xét các trường hợp • Nếu −1= a2 thì P(X) = (X2−a)(X2+a). • Nếu +2= b2 thì P(X) = (X2+bX+1)(X2−bX+1). • Nếu −2= c2 thì P(X) = (X2+ cX−1)(X2− cX−1). Vậy P(X) là đa thức khả quy trên Fp với mọi số nguyên tố p. 2.2 Tiêu chuẩn bất khả quy Eisenstein Trong các tiêu chuẩn bất khả quy của một đa thức nguyên, tiêu chuẩn Eisenstein là một trong những tiêu chuẩn quan trọng nhất. Sử dụng phương pháp thu gọn mod p, ta có thể chứng minh tiêu chuẩn này khá ngắn gọn. Hơn nữa, phương pháp chứng minh này cho phép ta có thể mở rộng tiêu chuẩn Eisenstein ra cho nhiều đa thức khác. 17 Trong phần tiếp theo chúng ta sẽ trình bày tiêu chuẩn Eisenstein và một số ví dụ minh họa việc sử dụng tiêu chuẩn này. Định lí 2.2.1 (Tiêu chuẩn Eisenstein). Cho đa thức nguyên bản P(X) = anXn+an−1Xn−1+ · · ·+a1X+a0. Giả sử có một số nguyên tố p sao cho (1) p là ước của a0, . . . ,an−1, (2) p không là ước của an, (3) p2 không là ước của a0. Khi đó P(X) là một đa thức nguyên bất khả quy. Chứng minh. Trên trường Fp, ta có P(X) = anXn. Giả sử P(X) = H(X)K(X), ta suy ra H(X)K(X) = anXn. Từ Định lý phân tích nhân tử (Định lý 1.1.2), ta có H(X) = bhXh, h≤ degH(X), K(X) = ckXk, k ≤ degK(X). Suy ra n= h+k≤ degH(X)+degK(X) = n. Do vậy h= degH(X), k= degK(X). Giả sử h> 0, k> 0 và P(X)=H(X)K(X). Suy ra P(0) =H(0)K(0). Theo giả thiết a0 = P(0) 6 ... p2, dẫn đến H(0) 6 ... p hoặc K(0) 6 ... p. Giả sử H(0) 6 ... p, suy ra H(0) 6= 0. Vì H(X) = bhXh nên h= 0, do đó H(X) là đa thức hằng. Vậy đa thức P(X) là bất khả quy trên Z. Ta xét một vài ví dụ áp dụng tiêu chuẩn Eisenstein để kiểm tra tính chất bất khả quy của một đa thức nguyên. Ví dụ 2.2.2 (Áp dụng trực tiếp tiêu chuẩn Eisenstein). Các đa thức sau đây là bất khả quy: 18 (a) P(X) = X8−6X6+9X4−12X2+15. Thật vậy, xét p= 3 ta có 3 là ước của −6, 9,−12, 15, và 32 không phải là ước của 15. Theo tiêu chuẩn Eisenstein, đa thức P(X) là bất khả quy trên Z. (b) P(X) = Xn− pq với 0< p< q là các số nguyên tố. Thật vậy, ta có p là ước của −pq và p2 không phải là ước của −pq. Áp dụng tiêu chuẩn Eisenstein, đa thức P(X) là bất khả quy trên Z. Trong nhiều bài toán, tiêu chuẩn Eisenstein không được áp dụng trực tiếp để xem xét tính bất khả quy của một đa thức mà ta phải biến đổi đa thức đi một chút dựa trên Bổ đề 1.1.1 trong chương trước. Ta xét các ví dụ minh họa sau. Ví dụ 2.2.3. Các đa thức sau là bất khả quy. (a) P(X) = X4+2X3+2X+1. Xét đa thức P(X+a) = (X+a)4+2(X+a)3+2(X+a)+1. Vậy số hạng tự do của đa thức P(X+a) là a4+2a3+2a+1. Ta có P(X−1) = (X−1))4+2(X−1)3+2(X−1)+1 = X4−2X3+4X−2. Xét p= 2. Theo tiêu chuẩn Eisenstein, đa thức P(X −1) là bất khả quy, do đó đa thức P(X) cũng bất khả quy (Bổ đề 1.1.1). (b) P(X) = X p−1+ · · ·+X+1 với p là số nguyên tố lẻ. Xét đa thức X p−1= (X−1)(X p−1+X p−2+ · · ·+X+1) = (X−1)P(X) với p là số nguyên tố lẻ. Trên trường Fp ta có( X−1)P(X) = X p−1= (X−1)p 19 hay là P(X) = (X−1)p−1. Điều này gợi ý ta đổi biến số P(X+1) = [(X+1)p−1]/X = X p−1+C1pX p−2+ . . .+Cp−2p X+ p. Áp dụng tiêu chuẩn Eisenstein, ta được đa thức P(X+1) là bất khả quy, do đó đa thức P(X) cũng là bất khả quy. (c) P(X) = X4+3X3−X2+2X+1. Xét đa thức P(X+a) = (X+a)4+3(X+a)3− (X+a)2+2(X+a)+1 = X4+(4a−3)X3+(6a2−9a−1)X2+(4a3−9a2−2a−2) +(a4+3a3−a2+2a+1) Ta cần tìm một số nguyên tố p sao cho nó là ước của các số (4a− 3), (6a2−9a−1), (4a3−9a2−2a−2), (a4+3a3−a2+2a+1). Từ hai số đầu ta được p | 35, suy ra p = 5 hoặc p = 7. Thử lần lượt, các giá trị a = ±1, a=±2 bị loại. Với a= 3, áp dụng tiêu chuẩn Eisenstein cho đa thức P(X) = X4+15X3+80X2+185X+160 với số nguyên tố p= 5, suy ra đa thức P(X) là bất khả quy. Trong phần tiếp theo ta sẽ xét một số mở rộng của tiêu chuẩn Eisenstein. Trước hết ta có định nghĩa hữu ích sau đây. Định nghĩa 2.2.4. Cho các số tự nhiên n≥ m≥ 0 và một số nguyên tố p. Giả sử P(X) = anXn+an−1Xn−1+ · · ·+a1X+a0, với các hệ số là các số nguyên a0, a1, . . . ,an. Ta nói đa thức P(X) có tính chất Em,p nếu p là ước của a0,a1, . . . ,am−1 và p không phải là ước của am. 20 Nhận xét 2.2.5. Trong phát biểu tiêu chuẩn Eisenstein thì đa thức P(X) có tính chất En,p với n= degP(X). Bổ đề 2.2.6. Đa thức nguyên P(X) có tính chất Em,p khi và chỉ khi trong Fp[X ], P(X) = XmP1(X) với P1(0) 6= 0. Chứng minh. Điều kiện cần. Giả sử đa thức nguyên P(X) có tính chất Em,p. Từ định nghĩa ta có P(X) = anXn+an−1Xn−1+ · · ·+amXm+ pa′m−1Xm−1+ · · ·+ pa′1X+ pa′0. Do đó P(X) = anXn+an−1Xn−1+ · · ·+amXm, am 6= 0 = Xm ( anXn−m+ · · ·+am ) = XmP1(X) với P1(X) = anXn−m+ · · ·+am+1X+am và P1(0) = am 6= 0 trong Fp. Điều kiện đủ. Giả sử P(X) = XmP1(X), P1(0) 6= 0. Suy ra có biểu diễn P(X) = XmP1(X)+ pQ(X) với Q(X) là một đa thức nào đó. Ta có P1(X) = XP2(X)+bm, bm 6= 0, Q(X) = Xm+1Q1(X)+ cmXm+ · · ·+ c1X+ c0. Suy ra P(X) = Xm(XP2(X)+bm)+ p(Xm+1Q1(X)+ cmXm+ · · ·+ c1X+ c0) = Xm+1(P2(X)+ pQ1(X))+(bm+ pcm)Xm+ pcm−1Xm−1 + · · ·+ pc1X+ pc0. Do đó đa thức P(X) có tính chất Em,p. 21 Hệ quả 2.2.7. Cho đa thức nguyên P(X) và một số nguyên tố p không đồng thời là ước của tất cả các hệ số của đa thức P(X). Đa thức P(X) luôn có tính chất Em,p với 0≤m≤ degP(X) nào đó. Số m như vậy là duy nhất và chỉ phụ thuộc vào P(X) và p. Mệnh đề 2.2.8. Cho đa thức nguyên P(X) và một số nguyên tố p không đồng thời là ước của tất cả các hệ số của đa thức P(X). Giả sử P(X) =H(X)K(X) với H(X) và K(X) là các đa thức nguyên. Khi đó, nếu P(X) có tính chất Em,p, H(X) có tính chất Eh,p thì h≤ m và K(X) có tính chất Em−h,p. Chứng minh. Trong Fp[X ] ta có P(X) = XmP1(X) với P1(0) 6= 0, H(X) = XhH1(X) với H1(0) 6= 0. Ta có P(X) = H(X)K(X) nên XmP1(X) = XhH1(X)K(X). Vì X 6 | P1(X), suy ra Xh | Xm nên h≤ m. Kéo theo Xm−hP1(X) = H1(X)K1(X). Vì X 6 | H1(X) nên H1(X) | Xm−hP1(X), suy ra H1(X) | P1(X) hay P1(X) = H1(X)K1(X) với đa thức K1(X) nào đó. Do đó K(X) = Xm−hK1(X). Vì P1(0) =H1(0)K1(0) nên K1(0) 6= 0. Suy ra K(X) có tính chất Em−h,p. Định lí 2.2.9 (Tiêu chuẩn Eisenstein mở rộng). Cho đa thức nguyên P(X) = anXn+an−1Xn−1+ · · ·+a1X+a0 với các hệ số là các số nguyên a0, a1, . . . ,an nguyên tố cùng nhau. Giả sử có một số m ∈ {1, . . . ,n} và số nguyên tố p sao cho (1) p là ước của a0, . . . ,am−1, 22 (2) p không là ước của am, (3) p2 không là ước của a0. Khi đó P(X) có một ước là đa thức nguyên bất khả quy có bậc lớn hơn hoặc bằng m. Chứng minh. Từ giả thiết suy ra P(X) có tính chất Em,p. Cố định số m, ta sẽ chứng minh bài toán bằng phương pháp quy nạp theo n= degP(X). Chú ý rằng, n≥ m. Xét n = m, khi đó đa thức P(X) có tính chất En,p, từ tiêu chuẩn Eisenstein ta suy ra P(X) bất khả quy. Xét n > m. Giả sử P(X) có một ước H(X) với 0 < degH(X) < m (nếu không tồn tại một ước H(X) như vậy thì kết luận được chứng minh). Ta có P(X) = H(X)K(X). Khi đó, H(X) có tính chất Eh,p, K(x) có tính chất Ek,p với h+k=m nào đó. Ta có P(0)=H(0)K(0). Vì p2