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ử

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 min