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ử

a 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 6 | P(0) nên p 6 | H(0) hoặc p 6 | K(0). Do h+k=m và h≤ degH(X) 0. Ta có K(X) =XkK1(X) suy ra K(0) = 0 nên p | K(0). Do đó p 6 | H(0) suy ra H(0) 6= 0 hên h= 0. Suy ra k = m. Như vậy, K(X) thỏa mãn • degK(X)< degP(X), • K(X) có tính chất Em,p, • p2 6 | K(0) (vì p2 6 | P(0) = H(0)K(0)). Từ giả thiết quy nạp, suy ra K(X) có một ước là đa thức bất khả quy có bậc lớn hơn hoặc bằng m. Nhận xét 2.2.10. Tiêu chuẩn Eisenstein mở rộng có thể được phát biểu theo cách khác: Cho một đa thức nguyên P(X) và một số nguyên tố p. Giả sử đa thức P(X) có tính chất Em,p và p2 6 | P(0). Khi đó P(X) có một ước là đa thức bất khả quy có bậc lớn hơn hoặc bằng m. 23 Bổ đề 2.2.11. Giả sử đa thức P(X) có tính chất Em,p và p2 6 | P(0). Nếu P(X) được viết thành P(X) = H(X)K(X) thì hoặc H(X) có tính chất Em,p và p 6 | K(0), hoặc K(X) có tính chất Em,p và p 6 | H(0). Chứng minh. Theo Bổ đề 2.2.6 suy ra H(X) có tính chất Eh,p, K(X) có tính chất Ek,p, với k+h= m nào đó. Do p2 6 | P(0) suy ra p 6 | H(0), tức là h= 0, do vậy k=m. Từ đây suy ra K(X) có tính chất Em,p, hoặc p 6 | K(0). Vậy k = 0, tương đương với h = m. Như vậy H(X) có tính chất Em,p. Mệnh đề 2.2.12. Giả sử P(X) có tính chất Em,p và p2 6 | P(0). Khi đó (1) P(X) luôn có một ước bất khả quy duy nhất Q(X) thỏa mãn tính chất Em,p và p2 6 | Q(0). (2) Mọi ước bất khả quy còn lại R(X) của P(X) đều có tính chất E0,p, nghĩa là p 6 | R(0). Chứng minh. Suy ra trực tiếp từ Bổ đề 2.2.11. Hệ quả 2.2.13. Giả sử P(X) là đa thức monic có tính chất En−1,p và P(X) không có nghiệm nguyên, trong đó n = degP(X). Giả sử p2 6 | P(0). Khi đó P(X) là bất khả quy. Chứng minh. Vì P(X) có tính chất En−1,p và p2 6 | P(0) nên P(X) có một ước bất khả quy Q(X) có tính chất En−1,p. Khi đó degQ(X) ≥ n− 1. Giả sử degQ(X) = n−1, suy ra P(X) = Q(X)(X+b) với b ∈ Z. Điều này mâu thuẫn mới giả thiết P(X) không có nghiệm nguyên. Vậy degQ(X) = n và do đó P(X) là bất khả quy. Ví dụ 2.2.14 (IMO 1993). Đa thức P(X) = Xn+5Xn−1+3, với n≥ 1, là bất khả quy trên Z. 24 Thật vậy, vì P(X) có tính chất En−1,3 và P(X) không có nghiệm nguyên nên theo Hệ quả 2.2.13, đa thức P(X) là bất khả quy. Ví dụ 2.2.15. Đa thức P(X) = X4−X3+X+2 là bất khả quy trên Z. Để kiểm tra điều này, ta thử với một số giá trị của p. Trên trường F2 ta có phân tích P(X) = X(X3+X2+1) là tích của hai đa thức bất khả quy. Trên trường F3 ta phân tích như sau P(X) = X4−X3+X−1 = (X−1)(X3+1) = (X−1)(X+1)3. Phân tích này gợi ý ta xét P(X−1) = X4−5X3+9X2−6X+3. Thật vậy, vì P(X) có tính chất E3,3 nên nếu P(X) là khả quy thì P(X) phải có một nghiệm nguyên a. Nghiệm này phải là ước của 2 nên nhận một trong các giá trị −2, −1, 1, 2. Kiểm tra lại ta thấy không có giá trị nào là nghiệm của P(X). Vậy P(X) là bất khả quy. Chú ý rằng do bậc của đa thức trên bằng 4 nên ta cũng có thể áp dụng trực tiếp định nghĩa để kiểm tra tính chất bất khả quy của P(X). 2.3 Trường hợp đa thức thu gọn P(X) không có nghiệm trong Fp Trong các giả thiết khi áp dụng các tiêu chuẩn Eisenstein (Định lý 2.2.1) và Eisen- stein mở rộng (Định lý 2.2.9), ta đều giả sử đa thức P(X) có nghiệm x = 0 trong Fp. Trong thực tế, có nhiều tính huống đa thức cần xét không thỏa mãn điều kiện này. Trong mục này ta xét một số đa thức như vậy. 25 Mệnh đề 2.3.1. Cho các đa thức nguyên F(X) và R(X) thỏa mãn • degF(X) = n, F(X) có tính chất En,p và p2 6 | F(0); • R(X) là đa thức monic và R(X) là bất khả quy trên trường Fp. Khi đó P(X) := F(R(X)) là bất khả quy. Chứng minh. Giả sử P(X) = H(X)K(X). Vì R(X) là đa thức monic nên sử dụng thuật toán chia đa thức, ta có H(X) = H0(X)R(X)+H1(X) với degH1(X)< degR(X) và K(X) = K0(X)R(X)+K1(X) với degK1(X)< degR(X). Như vậy P(X) = H(X)K(X) = ( H0(X)K0(X)+H0(X)K1(X)+H1(X)K0(X) ) R(X) +H1(X)+K1(X). Giả sử F(X) = anXn+an−1Xn−1+ . . .+a1X+a0. Ta có P(X) = anRn+an−1Rn−1+ . . .+a1R+a0 = H(X)K(X). Vì P(X) thỏa mãn En,p nên trong vành đa thức Fp[X ] ta có anR n = HK = (H0K0+H1K0+H0K1)R+H1K1. Suy ra R | H1K1. Vì R là bất khả quy, suy ra H = bhRh, K = ckRk với h+ k = n. Suy ra H = bhR h+ pH1, K = ckRk+ pK1. 26 Điều này kéo theo HK = bhckRn+ pckH1Rk+ pK1bhRh+ p2H1K1, mà H1K1 = RQ+ S, nên P = RP1+ p2S. Do đó P(0) = p2S(0). Điều này suy ra khẳng định p2 6 | P(0), mâu thuẫn. Do vậy h = 0 hoặc k = 0. Tóm lại, P(X) := F(R(X)) bất khả quy. Ta xét một số ví dụ sau. Ví dụ 2.3.2 (Hong Kong TST 2011). Với mọi n> 0, đa thức P(X) = (X2+X)2 n +1, là bất khả quy trên Z. Đây là một bài trong đề thi chọn đội tuyển thi Olympic Toán Quốc tế của Hồng Kông năm 2011. Lời giải của bài toán dựa trên nhận xét: trên F2, P(X) = F(R(X)) = (X2+X+1)2 n , trong đó • R(X) := X2+X+1 là một đa thức bất khả quy trên F2; • F(X) = (X−1)2n+1 thỏa mãn điều kiện E2n,p=2 và 22 6 | F(0). Từ Mệnh đề 2.3.1 ta nhận được P(X) là đa thức bất khả quy. 2.4 Bài tập đề nghị Bài tập 1. Chứng minh rằng các đa thức nguyên P(X) = X4−X3+5X2+5X−7 là đa thức bất khả quy. Bài tập 2 (Áp dụng tiêu chuẩn Eisenstein). Chứng minh rằng các đa thức sau đây đa thức bất khả quy. 27 (a) P(X) = Xn+4X2+6 với n ∈ N và n> 2. (b) P(X) = Xn−2 với số tự nhiên n cho trước. (c) P(X) = X5−X4+X3+X2+2X+1. Bài tập 3. Chứng minh rằng đa thức P(X) = (X3+X)2n−3, với n≥ 1, là bất khả quy trên Z. Bài tập 4. Cho trước số nguyên a. Chứng minh rằng đa thức P(X) = (X2+aX)2 n +1, là bất khả quy trên Z với mọi n≥ 1. 28 Chương 3 Một số thuật toán phân tích đa thức thành nhân tử Từ định lý phân tích nhân tử của đa thức, ta biết rằng mọi đa thức nguyên P(X) đều có phân tích P(X) = Pα11 (X) . . .P αr r (X) với P1, . . . ,Pr là các đa thức bất khả quy không liên hợp và α1, . . . ,αr > 0. Trong chương này ta xét một số thuật toán để tìm các ước bất khả quy P1, . . . ,Pr và các số α1, . . . ,αr của một đa thức P(X) cho trước. 3.1 Phân tích đa thức thành nhân tử Xét một đa thức P(X) với hệ số trên một trường K hoặc trên tập các số nguyên. Bài toán tìm một phân tích của P(X) thành tích các nhân tử với một tính chất nào đó, phổ biến nhất là tính chất bất khả quy, là một bài toán cơ bản và rất quan trọng trong lý thuyết đa thức. Trong Chương 2, ta đã xét tính chất bất khả quy của đa thức nguyên. Đây có thể coi là một bài toán con trong bài toán phân tích đa thức thành nhân tử. Một trường hợp riêng khác của bài toán phân tích nhân tử là bài toán tìm nghiệm của đa thức, nói cách khác là tìm các ước bậc nhất của đa thức P(X). Đây là bài toán cực kỳ khó với một đa thức bất kỳ và chỉ giải được trong một số trường hợp đặc biệt. 29 Ta liệt kê một số trường hợp phổ biến mà có thể tìm được tất cả nghiệm của một đa thức. (a) Đa thức P(X) có bậc thấp: Ví dụ degP(X) = 1,2,3,4 với hệ số trên một trường K. Với các đa thức này ta có công thức nghiệm tổng quát của P(X). (b) Đa thức nguyên (tổng quát hơn là đa thức hữu tỷ): Xét một đa thức nguyên P(X) = anXn+ an−1Xn−1+ . . .+ a1X + a0. Giả sử X = uv , với u, v ∈ Z và (u,v) = 1, là nghiệm của đa thức P(X), tức là an (u v )n +an−1 (u v )n−1 + . . .+a1 (u v ) +a0 = 0. Suy ra anun+an−1vun−1+ . . .+a1vn−1u+a0vn = 0. Điều này tương đương với −anun = v(an−1un−1+ . . .+a0vn−1). Vì (u,v) = 1. Suy ra v | an. Tương tự ta được u | a0. Để tìm u và v ta chỉ cần xét tất cả các ước số của an và a0, sau đó tính u và v. Ta có các nhận xét sau: - Số uv là nghiệm hữu tỷ của P(X) khi và chỉ khi P (u v ) = 0. Điều này tương đương với vX−u là ước của P(X). - Cách tìm nghiệm trên cũng có thể áp dụng cho đa thức hữu tỷ vì mọi đa thức hữu tỷ đều liên hợp với một đa thức nguyên thông qua quy đồng mẫu số các hệ số của đa thức đó. (c) Đa thức với hệ số trên trường hữu hạn: Với một đa thức P(X) ∈ Fp[X ], để tìm nghiệm của P trong Fp, ta chỉ cần tính tất cả giá trị P(a¯) với a¯∈{0¯, 1¯, . . . , p−1}. Vì Fp là hữu hạn nên việc này sẽ dừng sau một số hữu hạn bước. 30 Thuật toán Kronecker Thuật toán phân tích nhân tử đa thức nguyên đầu tiên là thuật toán Kronecker. Trong phần tiếp theo chúng ta sẽ trình bày thuật toán này. Để mô tả và chứng minh tính đúng đắn của thuật toán này, ta nhắc lại phương pháp nội suy Lagrange. Định lí 3.1.1 (Nội suy Lagrange). Mọi đa thức có hệ số trên một trường K và có bậc nhỏ hơn hoặc bằng n đều hoàn toàn xác định nếu biết giá trị của đa thức đó tại n+1 điểm phân biệt. Chứng minh. Cụ thể, cho đa thức P(X) ∈ K[X ] với degP(X) ≤ n. Tại n+1 điểm đôi một khác nhau a1,a2, . . . ,an,an+1, đặt bi = P(ai) ∈ K. Ta sẽ chứng minhh P(X) = n+1 ∑ i=1 bi (X−a1) . . .(X−ai−1)(X−ai+1) . . .(X−an+1) (ai−a1) . . .(ai−ai−1)(ai−ai+1) . . .(ai−an+1) . Ký hiệu đa thức ở vế phải là Q(X). Ta có degQ(X)≤ n và Q(ai) = bi = P(ai), với mọi i = 1, . . . ,n,n+1. Đa thức P(X)−Q(X) có bậc không vượt quá n nhưng có n+1 nghiệm phân biệt. Do đó P(X)≡ Q(X). Cho đa thức nguyên P(X) có degP(X) < n. Thuật toán Kronecker tìm một phân tích thành nhân tử của P(X) được thực hiện như sau. Lấy n số a1,a2, . . . ,an đôi một khác nhau. Nếu có một ai nào đó là nghiệm của P(X) thì bằng cách chia P(X) cho X −ai vài lần, ta có thể giả sử P(a1), . . . ,P(an) là các số khác 0. Giả sử H(X) là một ước của P(X). Ta có P(X) =H(X)K(X) với K(X) là một đa thức nào đó. Ngoài ra degH(X)≤ degP(X)< n. Ta cũng có P(ai) = H(ai)K(ai). Nói cách khác, H(ai) là ước của P(ai). Suy ra (H(a1),H(a2), . . . ,H(an)) ∈X , với X = {(d1,d2, . . . ,dn) : di | P(ai)} . 31 TậpX được tính dựa trên ước của các số P(a1), . . . ,P(an), do đó là tập hữu hạn. Theo Định lý nội suy Lagrange 3.1.1, bộ (H(a1),H(a2), . . . ,H(an)) hoàn toàn xác định một đa thức H(X) có bậc nhỏ hơn n. Với mỗi bộ (d1,d2, . . . ,dn) ∈X ta gọi Hd1,d2,...,dn(X) là đa thức nhận giá trị di tại ai. Có hữu hạn đa thức như vậy. Ước H(X) cần tìm của P(X) là một trong các đa thức Hd1,d2,...,dn(X) như vậy. Vì vậy để tìm các ước của P(X) ta chỉ cần tìm các đa thức Hd1,d2,...,dn(X) và thử lại. Tiếp tục thực hiện thuật toán trên với các ước tìm được. Cuối cùng dồn lại ta sẽ được một phân tích bất khả quy của đa thức P(X). Ví dụ 3.1.2. Xét đa thức F(X) = X3+ 2X2− 2X + 3. Nếu đa thức này khả quy trên Z thì ít nhất một trong các nhân tử của nó phải có bậc một. Ta cần hai giá trị để xác định duy nhất một đa thức bậc một. Ta sẽ dùng F(0) = 3 và F(1) = 4. Lưu ý rằng, nếu một trong hai giá trị này bằng 0 thì ta tìm ra một nghiệm. Nếu không có giá trị nào bằng 0, thì mỗi một giá trị có hữu hạn ước số. Bây giờ, 3 chỉ có thể phân tích được thành 1 ·3, 3 ·1, (−1) · (−3) hoặc (−3) · (−1). Do đó nếu nhân tử đa thức nguyên bậc 1 tồn tại, nó phải lấy trong các giá trị 1, 3, −1 hoặc −3 tại X = 0. Có 6 cách khác nhau để phân tích 4 (mỗi cách ứng với một bội của 4) nên có 4 · 6 = 24 tổ hợp có thể, một nửa trong số đó bị loại do là phần âm của nửa kia, tương ứng với 12 đa thức nguyên bậc một cần phải được kiểm tra. Chỉ có vài nhân tử đa thức nguyên thật sự của F(X). Kiểm tra một cách tường tận cho thấy P(X) = X+3 được xây dựng từ P(0) = 3, P(1) = 4, nhân tử F(X). Chia F cho P ta được nhân tử khác Q(X) = X2−X+1 nên F = PQ. Bây giờ ta có thể kiếm tra theo cách đệ quy để tìm các nhân tử của P và Q. Kết quả là cả hai đều bất khả quy trên tập số nguyên, do đó phân tích của F là F(X) = P(X)Q(X) = (X+3)(X2−X+1). Ví dụ 3.1.3. Xét đa thức F(X) = X5+X4+X2+X+2. Nếu đa thức này khả quy trên Z thì ít nhất một trong các nhân tử của nó phải có bậc hai hoặc ít hơn. Ta cần 32 ba giá trị để xác định duy nhất đa thức bậc hai. Ta sẽ dùng F(0) = 2, F(1) = 6, F(−1) = 2. Lưu ý rằng nếu một trong các giá trị này bằng 0 thì ta đã tìm ra một nghiệm (và một nhân tử). Nếu không có giá trị nào bằng 0, thì mỗi một giá trị có hữu hạn ước số. Bây giờ, số 2 chỉ có thể phân tích được thành 1 · 2, 2 · 1, (−1) · (−2) hoặc (−2) · (−1). Do đó nếu nhân tử đa thức nguyên bậc hai tồn tại, nó phải lấy trong các giá trị 1, 2, −1 hoặc −2 tại X =−1. Có 8 cách khác nhau để phân tích 6 (mỗi cách ứng với một bội của 6), nên có 4 ·4 ·8= 128 tổ hợp có thể, một nửa trong số đó bị loại do là phần âm của một nửa kia, tương ứng với 64 đa thức nguyên bậc hai cần phải được kiểm tra. Chỉ có vài nhân tử đa thức nguyên thực sự của F(X). Kiểm tra chúng một cách tường tận cho thấy P(X) = X2+X+1 được xây dựng tử P(0) = 1, P(1) = 3 và P(−1) = 1, nhân tử F(X). Chia F cho P ta được nhân tử Q(X) = X3−X+2, nên F = PQ. Bây giờ ta có thể kiếm tra theo cách đệ quy để tìm các nhân tử của P và Q. Kết quả là cả hai đều bất khả quy trên tập số nguyên, do đó phân tích của F là F(X) = P(X)Q(X) = (X2+X+1)(X3−X+2). 3.2 Thuật toán Yun phân tích không bình phương Trong phần này chúng ta sẽ xét các phân tích không bình phương, một dạng yếu hơn của phân tích nhân tử bất khả quy. Trong phân tích không bình phương, các nhân tử nhận được chỉ cần thỏa mãn không chứa bình phương của một đa thức bậc dương nào đó. 3.2.1 Phân tích không bình phương Xét đa thức P(X) với hệ số trên một trường K (ví dụ, Q,Fp). 33 Định nghĩa 3.2.1. Ta nói đa thức P(X) không chứa bình phương nếu trong phân tích bất khả quy P= P1P2 . . .Pr thì hai ước bất khả quy Pi, Pj bất kỳ, i 6= j, không liên hợp với nhau. Nói cách khác, mọi đa thức bậc dương H(X) đều có bình phương không là ước của Pi. Nhắc lại là hai đa thức P(X) và Q(X) liên hợp với nhau nếu P(X) = λQ(X) với λ 6= 0 ∈ K nào đó. Ví dụ 3.2.2. • Đa thức P(X) = (X2+1)(X+2) không chứa bình phương. • Đa thức Q(X) = (X2−1)(X3+1) có chứa bình phương. Định nghĩa 3.2.3. Một phân tích không bình phương của đa thức P(X) là một phân tích có dạng P(X) = P11 (X)P 2 2 (X) . . .P r r (X), trong đó P1(X),P2(X), . . . ,Pr(X) hoặc không có bình phương, hoặc bằng 1 và đôi một nguyên tố cùng nhau. Ví dụ 3.2.4. • Đa thức P(X) = (X2+1)(X +2) không chứa bình phương nên tự nó là một phân tích không chứa bình phương. • Đa thức Q(X) = (X2−1)(X3+1) có phân tích không bình phương là Q(X) = (X2−1)(X3+1) = (X−1)(X2−X+1)(X+1)2 = P1(X)P2(X)2, trong đó P1(X) = (X−1)(X2−X+1) và P2(X) = X+1. Về sự tồn tại của phân tích không bình phương, ta có định lý quan trọng sau. 34 Định lí 3.2.5. Một phân tích không bình phương luôn tồn tại và duy nhất, nghĩa là nếu P(X) = P1(X)P22 (X) . . .P r r (X) = Q1(X)Q 2 2(X) . . .Q s s(X) là hai phân tích không bình phương thì r = s và các cặp Pi(X),Qi(X) là liên hợp với nhau, i= 1,2, . . . ,n. Chứng minh. Giả sử P(X) có phân tích bất khả quy là P(X) = Hα11 (X) . . .H αr r (X) trong đó H1(X) là bất khả quy và đôi một không liên hợp. Sự tồn tại. Với mỗi i, đặt Pi(X) =  ∏ α j=i H j(X) nếu tồn tại α j = i, 1 nếu không tồn tại α j = i. Đa thức Pi(X) không chứa bình phương và rõ ràng P= P1(X)P22 (X) . . .P s s (X), với s=max{α1, . . . ,αr}. Tính duy nhất. Giả sử P(X) có phân tích không chứa bình phương thứ hai P(X) = Q1(X)Q22(X) . . .Q s′ s′(X). Giả sử H(X) là ước bất khả quy của P(X). Suy ra H(X) | Qi(X) nào đó và H(X) 6 | Q j(X) với mọi i 6= j. Suy ra H i(X) | Qii(X). Điều này dẫn đếnH i(X) | P(X) H i+1(X) 6 | P(X) kéo theo H i(X) | Pii (X). Do đó Pi(X) | Qi(X) (Pi(X) là tích các nhân tử mũ i ở trên). Suy ra Pi(X) | Qi(X) với mọi i. 35 Mặt khác P1(X)P2(X) . . .Prr (X) = Q1(X)Q2(X) . . .Q r r(X)Q r+1 r+1(X) . . .Q s s(X). Suy ra s= s′ và Pi(X) liên hợp với Qi(X), i= 1, . . . ,s. Nhận xét 3.2.6. Nếu ta biết trước phân tích bất khả quy thì ta sẽ có phân tích không bình phương xây dựng như trong chứng minh trên. Ngược lại, phân tích không bình phương là bước đầu tiên để tìm một phân tích bất khả quy. 3.2.2 Thuật toán Yun Thuật toán Yun giúp ta tìm một phân tích không có bình phương của một đa thức P(X) ∈ K[X ]. Các bước cụ thể của thuật toán như sau: Bước 0. Cho đa thức P(X) 6= 0. Bước 1. P0 := gcd(P,P′) (sử dụng thuật toán Euclid). Nhận xét 3.2.7. Nếu P có phân tích không bình phương P= P1P22 . . .P r r thì đạo hàm của P thỏa mãn P′ = P′1P 2 . . .Prr +2P ′ 2P1P2P 3 3 . . .P r r + . . .+ rP ′ rP1P 2 2 . . .P r−1 r−1P r−1 r = P2P23 . . .P r−1 r ( P′1P2 . . .P r r +2P1P ′ 2P3 . . .P r r + . . .+ rP1P2 . . .Pr−1P′r ) = Q ( P2P23 . . .P r−1 r ) . Với i= 1, P1 không là ước của Q do P1 6 | P′1P2P3 . . .Pr còn P1 | 2P1P′2P3 . . .Pr+ . . .+ rP1P2 . . .Pr−1P′r. Với i= 2, ta có điều tương tự . . . Do đó Pi 6 | Q. Ta tính các đa thức H1 := P P0 = P1 . . .Pr, 36 P0 := gcd(P,P′) = P2P23 . . .P r−1 r , K1 := P′ P0 = Q= r ∑ i=1 iP1 . . .Pi−1P′iPi+1 . . .Pr, I1 := K1−H ′1 = ( r ∑ i=1 iP1 . . .P′i . . .Pr ) − ( r ∑ i=1 P1 . . .P′i . . .Pr ) = ( r ∑ i=1 (i−1)P1 . . .P′i . . .Pr ) = P1 ( r ∑ i=2 (i−1)P2 . . .P′i . . .Pr ) . Suy ra P1 = gcd(I1,H1) vì Pj 6 | r ∑ i=2 (i−1)P1 . . .P′i . . .Pr với mọi j = 2,3, . . . ,r. Bước 2. H2 = H1 P1 , K2 = I1 P1 = r ∑ i=2 (i−1)P2 . . .P′i . . .Pr. I2 = K2−H ′2 = P2 ( r ∑ i=3 (i−1)P3 . . .P′i . . .Pr. ) Suy ra P2 = gcd(I2,H2). . . . Bước r. Tính Hr, Kr, Ir, Pr tương tự như Bước 2. Bước r+1. Hr+1 = 1, Kr+1 = 1 (dừng thuật toán). Chú ý rằng thuật toán trên áp dụng được cho đa thức với hệ số trên một trường. Thường ta xét K là trường các số hữu tỷ Q hoặc trường hữu hạn Fp. Ta có một số ví dụ cụ thể sau. 37 Ví dụ 3.2.8. Xét đa thức P(X) = X2−1. Trước tiên ta có gcd(P(X),P′(X)) = gcd(X2−1,2X) = 1. Vậy P0(X) = gcd(P(X),P′(X)) = 1. Ta có H1 = P P0 = X2−1 K1 = P′ P0 = 2X I1 = K1−H ′1 = 2X−2X = 0. Suy ra gcd(I1,H1) = X2−1. Vậy P1 = X2−1. Ta lại có H2 = H1 P1 = 1. Ta dừng lại tại đây. Vậy P(X) = X2−1. Ví dụ 3.2.9. Xét đa thức P(X) = 3X5−5X4+7X3−3X2+X+1. Ta tính P0 = gcd(P(X),P′(X)) = gcd(3X5−5X4+7X3−3X2+X+1,15X4−20X3+21X2−6X+1) = X2−X+1. Thêm nữa, H1 = P P0 = 3X3−2X2+2X+1 K1 = P′ P0 = 15X2−5X−1 I1 = K1−H ′1 = 6X2−X−1. Suy ra gcd(I1,H1) = 3X+1. Vậy P1 = 3X+1. 38 Ta thực hiện tiếp các phép tính H2 = H1 P1 = X2−X+1 K2 = I1 P1 = 2X−1 I2 = K2−H ′2 = 0. Suy ra gcd(I2,H2) = X2−X+1, dẫn đến P2 = X2−X+1. Ta lại có H3 = H2 P2 = 1. Ta dừng lại tại đây. Vậy phân tích không bình phương của đa thức P(X) là P(X) = (3X+1)(X2−X+1)2. 3.3 Phân tích nhân tử của đa thức trên trường hữu hạn Fp Trong tiết này ta xét thuật toán phân tích một đa thức trên trường Fp, p là một số nguyên tố. Chú ý rằng về mặt lý thuyết, với một đa thức P(X) ∈ Fp[X ] luôn có hữu hạn đa thức có bậc nhỏ hơn degP(X). Vì vậy để tìm ước của P(X) ta chỉ cần duyệt các đa thức có bậc nhỏ hơn degP(X) và xem đa thức nào là ước của P(X). Tuy nhiên cách này không hiệu quả về mặt tính toán do ta phải tính rất nhiều đa thức và thực hiện rất nhiều phép chia đa thức. Một thuật toán phân tích hiệu quả là cần thiết. 3.3.1 Thuật toán tổng quát Mục đích của phân tích này là với mỗi đa thức monic (chuẩn) P(X) ∈ Fp[X ], P(X) 6= 0, đưa ra một phân tích bất khả quy của P(X). Sau đây ta xét các bước chính của thuật toán. 39 Thuật toán phân tích bất khả quy trên Fp Bước 1 (Phân tích không bình phương). Dùng thuật toán Yun để tìm một phân tích không bình phương P = P1P22 . . .P r r , trong đó Pi không chứa bình phương, các đa thức Pi, Pj nguyên tố cùng nhau với mọi i 6= j. Bước 2 (Phân tích tách bậc). Với mỗi đa thức không chứa bình phương Pi trong Bước 1, tìm phân tích Pi = Pi,1Pi,2 . . .Pi,n với Pi,d là tích các ước bất khả quy bậc d của Pi. Bước 3 (Phân tích đồng bậc). Với mỗi đa thức Pi,d là tích các đa thức bất khả quy cùng bậc d, tìm phân tích bất khả quy của Pi,d (có degPi,d/d ước trong một phân tích như vậy). Bước 4 Viết lại phân tích bất khả quy của đa thức P(X) ban đầu. Trước khi trình bày tiếp, ta xét ví dụ minh họa cho phân tích tách bậc trong Bước 2. Ví dụ 3.3.1. Trong Bước 1 có một đa thức Pi(X) là Pi(X) = (X2−1) ( (X2+1)2−X2)(X3+2). Đa thức này có phân tích Pi = Pi,1 . . .Pi,n như trong Bước 2, trong đó Pi,1(X) = (X−1)(X+1) = X2−1 (tích các ước bất khả quy bậc 1) Pi,2(X) = (X2+1−X)(X2+1+X) = (X2+1)−X2 (tích các ước bất khả quy bậc 2) Pi,3(X) = X3+2 (tích các ước bất khả quy bậc 3) Trong thuật toán trên, bước 1 được thực hiện bằng cách sử dụng thuật toán Yun. Trong những phần tiếp theo ta sẽ môt tả cụ thể các bước còn lại. 40 3.3.2 Phân tích tách bậc Ta xét một đa thức không chứa bình phương P(X) ∈ Fp[X ]. Ta sẽ nhóm các ước bất khả quy cùng bậc của P(X) bằng thuật toán tách bậc. Trước hết ta có mệnh đề sau về các đa thức bất khả quy trên Fp. Mệnh đề 3.3.2. Cho Q(X) ∈ Fp[X ] là một đa thức bất khả quy bậc d. Khi đó P(X) | X pd −X . Ngược lại, nếu P(X) là ước bất khả quy của X pd −X và không là ước của X p d −X với e< d thì degP(X) = d. Chứng minh. Vì Q(X) là bất khả quy nên I := (Q(X)) là iđêan cực đại của Fp[X ]. Do đó Fp[X ]/I là một mở rộng trường hữu hạn của Fp. Ngoài ra dimFp Fp[X ]/(Q(X)) = d nên số phần tử của Fp[X ]/(Q(X)) bằng pd . Do đó mọi phần tử y của trường này thỏa mãn yp d = y. Với y= X thì X p d −X = 0 mod Q(X). Do đó Q(X) | X pd −X . Bây giờ ta sẽ trình bày thuật toán. Mục đích là với mỗi P(X) ∈ Fp[X ] không chứa bình phương, thuật toán cho ta ứng với từng số d ≤ degP(X) một đa thức Pd là tích các ước bất khả quy, monic và có bậc d của P(X). Thuật toán phân tích tách bậc trong Fp[X] Bước 1. Đặt Q= P, Y = X , d = 0. Bước 2. Đặt e= degQ. • Nếu d+1> 12e: với e> 0 ta đặt Pe := Q và Pi = 1 với mọi i> d, i 6= e, và dừng thuật toán ở đây. 41 • Nếu d+1≤ 12e, đặt d := d+1, Y := Y p mod Q Bước 3. Đặt Pd := gcd(Y −X ,Q). Nếu Pd 6= 1 thì đặt Q := Q Pd , Y := Y mod Q và quay lại Bước 2. Định lí 3.3.3. Thuật toán cho ta phân tích tách bậc của đa thức P(X). Chứng minh. Ta chứng minh bằng quy nạp theo d. Lặp lại từng bước của thuật toán trên như sau: • d = 0. Nếu 1= d+1> 12e nghĩa là e ∈ {0,1} thì ta dừng (do degP(X) = e). Nếu 1= d+1≤ 12e nghĩa là e≥ 2 thì ta đặt d := d+1= 1, Y = Y p mod P(X). Đặt P1 := gcd(Y −X ,Q) = gcd(X p−X ,P(X)), thì P1 chính là tích các ước bất khả quy bậc 1 (không liên hợp của P(X)) (theo Mệnh đề 3.3.2). Ta có nhận xét: Xét d > 0, sau bước d, Q(X) không có ước bất khả quy bậc 1,2, . . . ,d. Ta chứng minh rằng Pd+1 là tích các ước bất khả quy bậc d+ 1 của P(X). • Nếu d+1> 12e. Vì Q(X) không có ước bất khả quy bậc 1,2, . . . ,d nên Q(X) là bất khả quy. Thật vậy, nếu Q(X) = Q1Q2 với degQi ≥ 1 (với i= 1,2) thì degQi ≥ d+1, với i= 1,2. Nhưng khi đó deg(Q1Q2)≥ 2(d+1)> e= degQ. 42 Suy ra Q 6= Q1Q2. Điều này mâu thuẫn. Do đó thuật toán dừng, và đặt Pe = Q, Pi = 1 với mọi i> d, i 6= e. • Nếu d+1≤ 12e. Ta có Y := X p d+1 mod Q(X). Đặt Pd+1 := gcd(Y −X ,Q(X)) = gcd ( X p d+1−X ,Q(X) ) . Chú ý rằng Q(X) không có ước bất khả quy bậc 1,2, . . . ,d. Do đó Pd+1 là tích các ước bất khả quy bậc d+ 1 của Q(X) do đó là ước của P(X) (do Mệnh đề 3.3.2). Định lý do đó được chứng minh. Hệ quả 3.3.4. Cho đa thức P(X) ∈ Fp[X ] có bậc degP(X) = d > 0. Đa thức P(X) bất khả quy khi và chỉ khi P(X) | X pd −X và với mỗi ước nguyên tố q của d, ta có gcd ( P(X),X p d/q−X ) = 1. 3.3.3 Phân tích đồng bậc Cho đa thức P(X)∈ Fp[X ] là tích các đa thức bất khả quy có cùng bậc d và đôi một không liên hợp. Mục đích của bước này là tìm phân tích bất khả quy của P(X). Bổ đề sau được suy ra dễ dàng. Bổ đề 3.3.5. Ta có degP(X) = dr với r là số ước bất khả quy đôi một không liên hợp của P(X). Nói riêng, P(X) là bất khả quy khi và chỉ khi degP(X) = d. Mệnh đề 3.3.6. Cho p là số nguyên tố lẻ và P(X) là đa thức như trên. Với mọi đa thức Q(X) ∈ Fp[X ] ta có P(X) = gcd(P,Q)gcd ( P,Q pd−1 2 +1 ) gcd ( P,Q pd−1 2 −1 ) . 43 Chứng minh. Do P(X) có đủ nghiệm (đều là nghiệm đơn) trong Fpd và Qp d −Q nhận tất cả các phần từ của Fpd là nghiệm nên P(X) | Qp d −Q do P(X). Ngoài ra ta có Y p d −Y = Y ( Y p d−1−1 ) = Y ( Y pd−1 2 +1 )( Y pd+1 2 −1 ) với Y, Y pd−1 2 −1, Y p d+1 2 +1 đôi một nguyên tố cùng nhau, nên từ P(X) | Qpd −Q= Q ( Q pd−1 2 −1 )( Q pd+1 2 +1 ) ta suy ra P(X) = gcd(P,Q)gcd ( P,Q pd−1 2 −1 ) gcd ( P,Q pd+1 2 +1 ) . Phép chứng minh được kết thúc. Nhận xét 3.3.7. Ta có nhận xét là đa thức X pd −X có đúng pd nghiệm khác nhau trong Fpd . Do đó xác suất để P(X) và đa thức X pd−1 2 − 1 có nghiệm chung trong Fpd , hay nói cách khác có ước chung không tầm thường trong Fp[X ], là xấp xỉ 1 2 . Do đó nếu Q(X) ∈ Fp[X ] là đa thức monic chuẩn ngẫu nhiên có bậc nhỏ hơn hoặc bằng 2d−1 thì xác suất để P(X) và Q p d−1 2 −1 có ước chung không tầm thường là xấp xỉ 12 . Từ Nhận xét 3.3.7 ta có thuật toán tách Cantor-Zassenhaus như sau. Mục đích của thuật toán này là đưa ra một phân tích bất khả quy của đa thức P(X) nếu biết trước P(X) là tích các đa thức bất khả quy có cùng bậc d và đôi một không liên hợp. Thuật toán gồm ba bước. Thuật toán Cantor-Zassenhaus (phân tích đồng bậc) 44 Bước 1. Đặt r = degPd . Nếu r = 1 thì cho P1 = P và dừng. Bước 2. Chọn Q(X) ∈ Fp[X ] ngẫu nhiên là monic với degQ(X)≤ 2d−1. Đặt B= gcd ( P,Q pd−1 2 −1 ) . Nếu degB= 0 hoặc degB= degP thì quay lại Bước 2. Nếu 0< degB< degP thì đặt P := PB . Bước 3. Lặp lại phân tích đối với P và B. Chú ý rằng trường hợp p= 2 ta cũng có thuật toán tương tự. Ở đây ta không nhắc tới vì p lẻ là đủ khi ta xét phân tích bất khả quy trên Z. 3.4 Phân tích bất khả quy trên Z[X] Trong phần đầu của chương ta đã xét thuật toán Kronecker tìm phân tích bất khả quy của một đa thức nguyên. Tuy nhiên thuật toán này không hiệu quả vì số lượng tính toán quá lớn. Trong tiết này chúng ta sẽ xét một thuật toán hiệu quả hơn. 3.4.1 Chặn cho hệ số của các ước trong vành đa thức nguyên Chomột đa thức nguyên P(X)= a0+a1X+a2X2+. . .+anXn với (a1,a2, . . . ,an)= 1. Ta có khẳng định rất thú vị sau cho một chặn trên và dưới cho hệ số của các ước nguyên của P(X). Đặt |P(X)|= √ |a0|2+ |a1|2+ . . .+ |an|2. Định lí 3.4.1. Cho các đa thức nguyên P(X) = n ∑ i=0 aiX i ∈ Z[X ] và Q(X) = m ∑ i=0 biX i ∈ Z[X ]. Giả sử Q(X) | P(X) trong Z[X ]. Khi đó |b j| ≤C jm−1|P(X)|+C j−1m−1|an|. 45 Chọn B là số lớn nhất trong các số C jm−1|P(X)|+C j−1m−1|an|. Ta suy ra các hệ số b j của đa thức Q(X) đều nằm trong [−B,B]. Để chứng minh Định lí 3.4.1 ta cần các kết quả sau đây. Ta sẽ trình bày các kết quả này dưới dạng các bổ đề và hệ quả của chúng. Bổ đề 3.4.2. Cho x1,x2, . . . ,xm ≥ 1 là các số thực. Đặt σm,k = ∑ 1≤i1<...<ik≤m xi1xik với 0< k ≤ m, M = σm,m = x1 . . .xm. Khi đó σm,k ≤Ck−1m−1M+Ckm−1. Chứng minh. Ta viết σm,k(x1, . . . ,xm) = σm,k. Ta giả sử x1 ≤ . . .≤ xm. Ta có σm,k(x1, . . . ,xm−2,1,xm−1,xm) = σm,k(x1, . . . ,xm)+σm−2,k−1(x1, . . . ,xm−2)(xm−1−1)(xm−1) ≥ σm,k(x1, . . . ,xm). Tương tự σm,k(x1, . . . ,xm)≤ σm,k(1,1, . . . ,1,x1 . . .xm︸ ︷︷ ︸ M ) = σm,k(1,1, . . . ,1,M) ≤Ck−1m−1M+Ckm−1. Bổ đề được chứng minh xong. Bổ đề 3.4.3. Cho các đa thức P(X) = ∑ni=0aiX i ∈ C[X ]. Với α ∈ C thì ta có |(X−α)P(X)|= |(αX−1)P(X)|. 46 Chứng minh. Ta có |(X−α)P(X)|2 = |(X−α)(a0+a1X+ . . .+anXn)|2 = ∣∣∣−αa0+(a0−αa1)X+(a1−αa2)X2+ + . . .+(an−1−αan)Xn+anXn+1 ∣∣∣2 = n+1 ∑ i=−1 |ai−αai+1|2 , với a−1 = an+1 = 0. = n+1 ∑ i=−1 |ai|2+ |α|2a2i+1−2Re(αai+1ai). Ta lại có |(αX−1)P(X)|2 = |α|2 ∣∣∣∣(X− 1α ) P(X) ∣∣∣∣2 = |α|2 m+1 ∑ i=−1 ( |ai|2+ ∣∣∣∣ 1α ∣∣∣∣2 |ai+1|2−2Re( 1α ai+1ai )) = m+1 ∑ i=−1 (|α|2|ai|2+ |ai+1|2−2Re(ai+1ai)) = |(X−α)P(X)|. Bổ đề được chứng minh xong. Hệ quả 3.4.4. Với mọi α1,α2, . . . ,αr ∈ C ta có∣∣∣∣∣ r∏i=1(X−αi)P(X) ∣∣∣∣∣= ∣∣∣∣∣ r∏i=1(αi−1)P(X) ∣∣∣∣∣ . Chứng minh. Bởi Bổ đề 3.4.3 ta biến đổi như sau. |(X−α1)(X−α2) . . .(X−αr)P(X)| = |(α1X−1)(X−α2) . . .(X−αr)P(X)| = |(α1X−1)(α2X−1)(X−α3) . . .(X−αr)P(X)| . Phép chứng minh kết thúc. 47 Chứng minh Định lí 3.4.1. Vì đa thức P(X) có đủ nghiệm trong C nên ta viết P(X) = an(X−α1)(X−α2) . . .(X−αn), α1,α2, . . . ,αn ∈ C = an ∏ |α j|≥1 (X−α j) ∏ |α j|<1 (X−α j) Đặt P1(X) = an ∏ |α j|≥1 (X−α j) ∏ |α j|<1 (α jX−1) với α j ∈ C. Ta suy ra |P(X)|2 = |P1(X)|2 ≥ |an|2 (|Cn|2+ |Cn−1|2+ . . .+ |C0|2) với P1(X) = an(CnXn+Cn−1Xn−1+ . . .+C1X+C0). Ta có m(P) = |Cn|= ∣∣∣∣∣∣ ∏|α j|<1α j ∣∣∣∣∣∣ , M(P) = |C0|= ∣∣∣∣∣∣ ∏|α j|≥1α j ∣∣∣∣∣∣ . Áp dụng Định lí Viete ta có ai−1 an = (−1)iσm,i(α1,α2, . . . ,αn). Suy ra |ai−1| an ≤ σm,i(|α1|, |α2|, . . . , |αn|)≤ σn,i(P1,P2, . . . ,Pn). Ta có β j =max{1, |α j|}. Chú ý rằng β1β2 . . .βn = ∏ |α j|≥1 |α j|=M(P). Ta có |an−1| |an| ≤C m−1 n−1 M(P)+C i n−1. Áp dụng cho Q(X), |bm−i| ≤ bm ( Ci−1n−1M(Q)+C i m−1 ) ≤ |an| ( Ci−1n−1M(P)+C i m−1 ) 48 =Ci−1n−1|an|M(P)+Cim−1|an| ≤ |P| với |bm| ≤ |an|, M(Q)≤M(P). 3.4.2 Phân tích bất khả quy mod pe Phần này là ứng dụng của Bổ đề Hensel. Định lí 3.4.5 (Bổ đề Hensel). Cho p là một số nguyên tố, e ≥ 1. Giả sử P(X), Ke(X), He(X),U(X), V (X) là các đa thức nguyên thỏa mãn • P≡ HeKe mod pe. • UHe+VKe = 1 mod p. • He là đa thức monic. • degU < degK, degV < degHe. Khi đó tồn tại các đa thức He+1, Ke+1 thỏa mãn He+1 ≡ He mod pe, Ke+1 ≡ HKe mod pe, P≡ He+1Ke+1 mod pe. Ngoài ra, He+1, Ke+1 là duy nhất theo mod pe+1. Chứng minh. Đặt D= 1 pe (P−HeKe) ∈ Z[X ], He+1 = He+ peS(X), Ke+1 = Ke+ peT (X), với S, T thuộc Z[X ] là các đa thức cần tìm. 49 Từ P≡ He+1Ke+1 mod pe suy ra P= (He+ peS)(Ke+ peT )+ pe+1R(X) = HeKe+ pe(SKe+THe)+ p2eST + pe+1R(X) = HeKe+ pe(SKe+THe)+ pe+1(R+ pe−1ST ). Suy ra D= P−HeKe pe = SKe+THe+ p(R+ pe−1ST ), hay là D= SKe+THe mod p. TừUHe+VKe = 1 trong Fp[X ], DVKe+DUHe = D suy ra S= DV +WHe và T = DU−WKe vớiW nào đó. Như vậy tồn tại He+1 và Ke+1. Một dạng khác của Bổ đề Hensel rất hữu ích trong bài toán phân tích đa thức thàn nhân tử như sau. Định lí 3.4.6. Cho hai số nguyên p và q. Đặt r = gcd(p,q). Cho P, H, K, U , V2 thuộc Z[X ] thỏa mãn P= HK mod p và UH+VK = 1 mod p. Giả sử (r, `(H)) = 1, degU < degK, degV < degH và degP= degH+degK. Khi đó tồn tại H1, K1 ∈ Z[X ] sao cho H1 ≡ H mod q, K1 ≡ K mod q và `(H1) = `(H), degH1 = degH, degK1 = degK sao cho P≡ H1K1 mod qr. Hơn nữa H1K1 là duy nhất theo mod qr nếu r là nguyên tố. 50 Chứng minh. Phép chứng minh tương tự như Định lí 3.4.5. Ta sẽ trình bày lại Định lí 3.4.6 dưới dạng thuật toán như sau. Bước 1 (Chia Euclid). Đặt f = 1q(P−HK) mod r, suy ra f ∈ Z/rZ[X ]. Theo giả thiết (r, `(H)) = 1 suy ra `(H) khả nghịch trong Z/rZ[X ]. Từ UH+VK = 1 mod p trong Z/rZ[X ], chia V f cho H ta được V f = Ht+ t0 với deg t0 < degH. Bước 2 (Kết thúc). Gọi H0 ∈ Z[X ] là nâng của V f −Ht = t0 sao cho deg(t0) = deg(H0). Tương tự K0 ∈ Z[X ] là nâng của U f +Kt sao cho deg(K0) = deg(H f +Kt). Đặt H1 = H+qH0 và K1 = K+qK0. Thuật toán đến đây dừng. Chú ý 3.4.7. Từ thuật toán ta suy ra H1K1 = HK+q(H0K+HK0)+q2H0K0. Do đó H1K1 = HK+qK(V f −Ht)+qH(U f +Kt)+qrKA+qrHB+q2H0K0 = HK+q f (KV +HU)+qrKA+qrHB+q2H0K0 = HK+q f (KV +HU)+qrKA+qrHB+q2H0K0 = HK+(P−HK)(KV +HU)+qrKA+qrHB+q2H0K0. Ta có KV +HU = 1+ pC và P= HK+qD suy ra vế phải của đẳng thức trên bằng P−qD(1+qC)+qrKA+qrHB+q2H0K0 51 = P+ pqCD+qrKA+qrHB+q2H0K0. Từ đây suy ra H1K1 = P+ pqCD+qrKA+qrHB+q2H0K0 ≡ P mod qr (do r | p suy ra pq ... qr). 3.4.3 Thuật toán Zassenhaus Sử dụng các kết quả đã trình bày trong phần trước, chúng ta đi đến thuật toán tìm phân tích bất khả quy của một đa thức trong vành các đa thức nguyên. Thuật toán này được gọi là thuật toán Zassenhaus. Cho một đa thức P0(X) trong Z[X ]. Bước 1 (Đưa về đa thức không chứa bình phương). Tính d = content(P0(X)) := gcd(a j) với a j là các hệ số của đa thức P0(X). Thế P0(X) := 1 d P0(X). Tìm gcd(P0(X),P′0(X)) và thế P(X) = P0(X) gcd(P0(X),P′0(X)) . Khi đó P(X) không chứa bình phương và chứa tất cả các ước nguyên tố của đa thức ban đầu. Bước 2 (Phân tích không chứa bình phương mod p). Với mỗi số nguyên tố p, tính gcd(P(X),P′(X)) trong Fp[X ]. Chọn p nếu gcd(P(X),P′(X)) = 1 và bậc của P(X) không đổi. Với số p đó, tìm một phân tích bất khả quy (vẫn không chứa bình phương) của P(X) trong Fp[X ] P(X) = `(P)P1(X)P2(X) . . .Pr(X) với `(P) ∈ Z là hệ số bậc cao nhất của P(X), Pi(X) là các đa thức nguyên monic và bất khả quy trên Fp. 52 Bước 3 (Tìm chặn). Tìm số B> 0 nhỏ nhất sao cho với mọi ước nguyên của P(X) với bậc không vượt qua 12 degP(X) đều có hệ số nằm trong [−B,B]. Chọn e > 0 sao cho pe > 2`(P)B với `(P) ∈ Z là hệ số bậc cao nhất của P(X). Bước 4 (Nâng Hensel). Dùng thuật toán nâng trong Bổ đề Hensel (Định lí 3.4.5) ta nâng phân tích trong Bước 2 lên mod pe P(X) = `(P)P1(X)P2(X) . . .Pr(X) mod pe Pi(X) là các đa thức nguyên monic và bất khả quy mod pe. Đặt d = 1. Bước 5 (Tổ hợp lại và chọn). Xét tất cả các tổ hợp Q= Pi1(X)Pi2(X) . . .Pid(X) trong Fp[X ] với 1≤ i1 < .. . < id ≤ r (chú ý là id = 1 nếu d = 12r). Tìm đa thức duy nhất Q(X) ∈ Z[X ] sao cho thỏa mãn • các hệ số Q nằm trong [−12 pe, 12 pe]. • Q(X) = `(P)Q(X) mod pe nếu degQ ≤ 12 degP và Q(X) = P(X)Q(X) mod pe nếu degQ> 12 degP. NếuQ | `(P)P trong Z[X ] thì đặt F là lũy thừa cao nhất củaQ trong P0(X). Khi đó • Đặt P := PF . • Bỏ Pi1,Pi2, . . . ,Pid ra khỏi phân tích mod pe ở trên. • Đặt r := r−d nếu d ≤ 1 2r d nếu d > 12r và dừng lại. 53 Bước 6 Đặt d := d+1. Nếu d ≤ 12r thì quay về Bước 5. Nếu d > 12r thì dừng thuật toán. Thu được F lũy thừa của Q(X) trong P0(X). 54 Kết luận Trong luận văn chúng tôi đã trình bày một số kết quả sau: 1. 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. Thuật toán Kronecker phân tích đa thức nguyên thành nhân tử bất khả quy. 3. Phân tích không bình phương và thuật toán Yun. 4. Thuật toán phân tích bất khả quy trên trường hữu hạn Fp. 5. Thuật toán phân tích bất khả quy trong vành các đa thức nguyên Z[X ]. 55 Tài liệu tham khảo Tiếng Việt [1] Đoàn Trung Cường (2014), Thu gọn mod p và đa thức bất khả quy. Tiền ấn phẩm. [2] Lê Thị Thanh Nhàn (2015), Giáo trình Lý thuyết đa thức (Giáo trình Sau đại học), Nhà xuất bản Đại học Quốc gia Hà Nội. Tiếng Anh [3] H. Cohen (1993), A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics 138, Springer-Verlag Berlin New York. [4] M. Filaseta (1998), The theory of irreducible polynomials,Math788F Course Note, University of South Carolina. [5] Factorization of polynomials, wikipedia.org.