Luận văn Đa thức bất khả quy trên trường zp thuật toán berlekamp và phân tích đa thức trên trường q

tại phân tích f (x) = g(x)h(x) trong đó g(x),h(x) ∈ Z[x] có hệ số cao nhất bằng 1 và degg(x) = 2,degh(x) = 3. Viết g(x) = x2+ ax+ b và h(x) = x3+ cx2+ dx+ e với a,b,c,d,e ∈ Z. Đồng nhất hệ số ở hai vế của đẳng thức f (x) = g(x)h(x) ta được c+a= 0,b+d+ac= 1,bc+ad+ e= 1,ae+bd = 0,be= 3. Vì be= 3 nên chỉ có thể xảy ra 4 trường hợp sau. Trường hợp 1: b= 1,e= 3. Khi đó c+a= 0,d+ac= 0,c+ad =−2,3a+ d = 0. Từ hai phương trình đầu ta được c = −a,d = a2. Thay vào phương trình thứ ba được a(a2−1) =−2 không có a | 2 thỏa mãn. Trường hợp 2: b = −1,e = −3. Khi đó c+ a = 0,d+ ac = 2,−c+ ad = 4,3a+ d = 0. Từ hai phương trình đầu ta được a = −c,d = a2+ 2. Thay vào phương trình thứ ba được a(a2+3) = 4 không có a | 6 thỏa mãn. Trường hợp 3: b= 3,e= 1. Khi đó a+c= 0,d+ac=−2,3c+ad = 0,a+ 3d = 0. Từ hai phương trình đầu ta được a = −c,d = a2− 2. Thay vào phương trình cuối được 3a2+a−6= 0. Suy ra a /∈ Z. Không thỏa mãn. Trường hợp 4: b = −3,e = −1. Khi đó a+ c = 0,d+ ac = 4,−3c+ ad = 2,a+ 3d = 0. Từ hai phương trình đầu ta được a = −c,d = a2+ 4. Thay vào phương trình thứ ba được a(a2+7) = 2. Không có a | 2 thỏa mãn. Vì vậy f (x) bất khả quy. Tiêu chuẩn sau đây cũng rất hay được sử dụng để xét tính bất khả quy của đa thức trên Q. Định lý 1.2.7. (Tiêu chuẩn Eisenstein). Cho f = anxn+ ...+a1x+a0 ∈Z[x]. Giả sử tồn tại một số nguyên tố p thỏa mãn các tính chất (i) p không là ước của hệ số cao nhất an; (ii) p là ước của các hệ số a0,a1, ...,an−1; (iii) p2 không là ước của hệ số tự do a0. Khi đó f(x) là bất khả quy trên Q. Chứng minh. Giả sử f (x) khả quy trên Q. Theo Bổ đề Gauss, tồn tại biểu 12 diễn f (x) = g(x)h(x), trong đó g(x) = bmxm + . . .+ b1x+ b0 ∈ Z[x] và h(x)= ckxk+ ...+c1x+c0 ∈Z[x] với degg(x)=m, degh(x)= k vàm,k< n. Do p là ước của a0= b0c0 nên p | b0 hoặc p | c0. Lại do p2 không là ước của a0 nên trong hai số b0 và c0, có một và chỉ một số chia hết cho p. Giả thiết p | c0. Khi đó b0 không chia hết cho p. Vì an= bmck và an không chia hết cho p nên bm và ck đều không chia hết cho p. Do đó tồn tại số r bé nhất sao cho cr không là bội của p. Ta có ar = b0cr+(b1cr−1+ b2cr−2+ ...+ brc0). Vì r≤ k< n nên p | ar. Theo cách chọn r ta có p | b1cr−1+b2cr−2+ ...+brc0. Suy ra p | b0cr, điều này là vô lí vì cả hai số b0 và cr đều không là bội của p. Vậy f (x) là bất khả quy trên Q.  Ví dụ 1.2.8. (i) Đa thức x2016+2015 là bất khả quy trên Q theo tiêu chuẩn Eisenstein với p= 5. (ii) Đa thức 23x3+ 1970 là bất khả quy trên Q theo tiêu chuẩn Eisenstein với p= 5. (iii) Đa thức 2015x2016−2016x2015+6x30+30x6+6 là bất khả quy trên Q theo tiêu chuẩn Eisenstein với p= 3. (iv) Đa thức f (x) = x4− 8x3+ 10x2− 12x+ 3 là bất khả quy trên Q vì đa thức f (x+ 3) = x4+ 4x3− 8x2− 60x− 78 là bất khả quy trên Q theo tiêu chuẩn Eisenstein với p= 2. 13 Chương 2 Thuật toán Berlekamp và bài toán phân tích đa thức thành nhân tử Trong Lí thuyết số, một trong những bài toán khó nhất và lâu đời nhất là tìm thuật toán hữu hiệu phân tích số tự nhiên ra thừa số nguyên tố. Bài toán này cho đến nay vẫn chưa được giải quyết trọn vẹn. Trong lí thuyết đa thức, bài toán tương tự "tìm thuật toán phân tích đa thức trên một trường thành nhân tử bất khả quy" cũng là một trong những bài toán khó nhất. Bài toán này mới chỉ được giải quyết trong một số trường hợp đặc biệt mà chưa có lời giải tổng quát. Mục tiêu của chương này là trình bày Thuật toán Berlekamp phân tích đa thức thành nhân tử trên trường hữu hạn và ứng dụng để phân tích đa thức thành nhân tử trên trường Q. 2.1 Trường phân rã của đa thức, trường hữu hạn Trong suốt tiết này luôn giả thiết K là một trường. Định nghĩa 2.1.1. (i) Nếu K là một trường con của E thì ta gọi E là một trường mở rộng của K, ký hiệu là E/K. (ii) Giả sử E/K là một mở rộng trường. Xem E là một không gian véc tơ trên K. Nếu E là K- không gian véc tơ hữu hạn chiều thì ta nói E là mở rộng bậc hữu hạn của trường K. Nếu dimK E = n thì n được gọi là bậc của mở rộng E/K và được ký hiệu là [E : K]. 14 Chú ý 2.1.2. Chú ý rằng nếu E/K và K/F là các mở rộng hữu hạn, trong đó E,K,F là các trường thì [E : F ] = [E : K][K : F ]. Cho E/K là mở rộng trường và α ∈ E. Kí hiệu K(α) là giao của tất cả các trường con của E chứa K và α , khi đó K(α) là trường con bé nhất của E chứa K và α . Kí hiệu K[α] là giao của tất cả các vành con của E chứa K và α . Khi đó K[α] là vành con bé nhất của E chứa K và α . Rõ ràng K[α]⊆ K(α). Chú ý 2.1.3. (Xem [1]). Cho E/K là mở rộng trường và α ∈ E. Khi đó (i) K[α] = { f (α) | f (x) ∈ K[x]}. (ii) K(α) = { f (α) g(α) | f ,g ∈ K[x],g(α) 6= 0 } . (iii) Nếu α là đại số trên K (tức α là nghiệm của một đa thức khác 0 với hệ số trong K) thì K(α) = K[α]. (iv) Nếu α là siêu việt trên K (tức α không đại số trên K) thì K(α)∼= K[α]. Định nghĩa 2.1.4. Giả sử E/K là một mở rộng trường và f (x) ∈ K[x] là đa thức bậc n≥ 1. Ta nói f (x) là phân rã trên E nếu f (x) = a(x−α1)...(x−αn) với a là hệ số cao nhất của f (x) và α1, ...,αn ∈ E. Ta nói E là trường phân rã của f (x) trên K nếu f (x) phân rã trên E và không phân rã trên bất cứ trường con thực sự nào của E. Ví dụ 2.1.5. Cho đa thức f (x) = x3−7 ∈Q[x]. Khi đó trường phân rã của f (x) trên Q là Q( 3 √ 7, i). Ở đây ta kí hiệu Q( 3 √ 7, i) là trường con bé nhất của trường số phức chứa 3 √ 7 và i. Bổ đề 2.1.6. Với mọi đa thức f (x) ∈ K[x] bất khả quy trên trường K, tồn tại một trường E chứa K và chứa một nghiệm của f (x). Chứng minh. Xét vành thương T =K[x]/I, trong đó I là iđêan của K[x] sinh bởi f (x). Vì K[x] là một vành giao hoán nên T cũng là một vành giao hoán có đơn vị là 1 = 1+ I. Rõ ràng ta có 1 6= 0, ta sẽ chứng minh T là một 15 trường. Thật vậy, giả sử g(x) = g(x)+ I là một phần tử khác không của T . Vì g(x) 6= 0 nên g(x) /∈ I tức g(x) không chia hết cho f (x). Do f (x) bất khả quy trên K nên f (x) và g(x) nguyên tố cùng nhau. Vì vậy tồn tại các đa thức r(x),s(x) ∈ K[x] sao cho ta có f (x)r(x)+ g(x)s(x) = 1. Lấy các lớp tương ứng trong vành thương ta được f (x).r(x)+g(x).s(x) = 1. Do f (x) = 0 nên g(x).s(x) = 1. Điều này chứng tỏ g(x) khả nghịch trong vành T . Vậy T là trường. Thiết lập ánh xạ ϕ : K→ T cho bởi a 7→ a+ I = a. Rõ ràng, ϕ là một đơn cấu trường. Vậy tập hợp {a ∈ T | a ∈ K} lập thành một trường con đẳng cấu với K. Nếu ta đồng nhất K với ϕ(K) bằng cách đồng nhất a ≡ a thì ta có thể xem K như là một trường con của trường T . Ngoài ra nếu f (x) = a0+a1x+ ...+anxn thì ta có 0= 0= f (x) = a0+a1x+ ...+anxn = a0+a1x+ ...+anxn = f (x). Vậy phần tử x = x+ I ∈ T là một nghiệm của đa thức f (x). Do đó tồn tại trường T chứa K và chứa một nghiệm của f (x)  Định lý 2.1.7. Với mỗi đa thức f (x)∈K[x]) có bậc n≥ 1, tồn tại một trường phân rã f (x) trên K. Chứng minh. Trước hết ta chứng minh sự tồn tại mở rộng trường E củaK sao cho f (x) phân rã trên E. Ta chứng minh điều này bằng quy nạp theo n. Cho n= 1 thì f (x) = ax+b với a 6= 0,a,b∈K. Suy ra f (x) = a(x−α), trong đó α =−ba−1 ∈K. Do đó chỉ việc chọn E =K. Cho n> 1 và giả thiết kết quả đã đúng cho các đa thức bậc nhỏ hơn n. Nếu f (x) bất khả quy thì theo Bổ đề 2.1.6, tồn tại một trường T chứa K và chứa một nghiệm α của f (x). Suy ra f (x) = (x−α)g(x) với g(x) ∈ T [x] có bậc là n− 1. Theo giả thiết quy nạp, có trường mở rộng E của K1 sao cho g(x) có đủ n− 1 nghiệm trong E. Do đó E là trường chứa K và chứa đủ n nghiệm của f (x). Giả sử f (x) không bất khả quy trên K. Khi đó f (x) = g(x)h(x) với degh(x) = n1 < n và degh(x) = n2 < n. Theo giả thiết quy nạp, tồn tại trường F chứa K và chứa đủ n1 nghiệm của g(x). Chú ý rằng h(x) ∈ F [x]. Do đó theo giả thiết quy nạp, tồn tại trường E chứa F và chứa đủ n2 nghiệm của h(x). Do đó E 16 là trường chứa K và chứa đủ n nghiệm. Vậy, khẳng định được chứng minh. Bây giờ ta chứng minh sự tồn tại của trường phân rã. Theo khẳng định trên, tồn tại trường E chứa K và chứa đủ n nghiệm α1, ...,αn của f (x). Gọi K(α1, . . . ,αn) là trường con bé nhất của E chứa K và α1, . . . ,αn. Khi đó K(α1, . . . ,αn) chính là trường phân rã của đa thức f (x) trên K.  Chú ý 2.1.8. (xem [1]). Trường phân rã của một đa thức trên một trường là tồn tại và duy nhất theo nghĩa nếu T và T ′ là hai trường phân rã trên K của đa thức f (x) ∈ K[x] thì T ∼= T ′. Cho K là trường. Đặc số của K là số nguyên dương nhỏ nhất k (nếu tồn tại) sao cho k1= 0, trong đó 1 ∈ K là phần tử đơn vị. Nếu không tồn tại số nguyên dương k thỏa mãn k1= 0 thì ta nói K có đặc số 0. Chú ý rằng mỗi trường hoặc có đặc số 0 hoặc có đặc số là một số nguyên tố. Rõ ràng Q có đặc số 0 và nếu p nguyên tố thì thì trường Zp có đặc số p. Bổ đề 2.1.9. Nếu K là trường hữu hạn có q phần tử thì K có đặc số p nguyên tố và q là một lũy thừa của p. Chứng minh. Giả sử K có đặc số 0. Khi đó n1 6= m1 với mọi n 6= m. Do đó tập {n1 | n ∈ N} là một tập con vô hạn của K, vô lí. Do đó K có đặc số p nguyên tố. Xét ánh xạ ϕ : Z→ K cho bởi ϕ(n) = n1. Khi đó ϕ là một đẳng cấu vành và Kerϕ = {k ∈ Z | k1= 0}= pZ. Suy ra Z/pZ ∼= Imϕ , tức là Zp ∼= Imϕ ⊆ K. Do p nguyên tố nên Zp là trường. Vì thế K là một không gian véc tơ trên trường Zp. Do K có hữu hạn phần tử nên không gian này có chiều hữu hạn. Giả sử dimZpK = d. Suy ra K có q= pd phần tử.  Định lý 2.1.10. (i) Nếu p là số nguyên tố thì với mỗi số nguyên dương d, tồn tại một trường có đúng pd phần tử. (ii) Nếu K và T là hai trường hữu hạn cùng có q phần tử thì chúng có cùng đặc số p và đều là trường phân rã của đa thức g(x) = xq− x trên trường Zp. Hơn nữa, K ∼= T. Chứng minh. (i) Đặt q = pd. Do p nguyên tố nên Zp là trường. Theo định lí trên, tồn tại một trường F chứa Zp và chứa các nghiệm của đa thức g(x) = xq− x ∈ Zp[x]. Đặt E = {α ∈ F | g(α) = 0}. Ta chứng minh E là 17 trường. Ta có g′(x) = qxq−1−1, trong đó g′(x) là đạo hàm của g(x). Khi đó g′(x) = (q1)xq−1−1=−1. Do đó gcd(g(x),g′(x)) = 1. Suy ra g(x) không có nghiệm bội trong F , tức là E có đúng q phần tử. Bây giờ ta cần chỉ ra E là một trường. Nếu p lẻ thì q lẻ và do đó g(−1) =−1+1= 0. Vì thế −1 ∈ E. Nếu p chẵn thì p= 2 (vì p nguyên tố). Suy ra g(−1) = (−1)q+1= 1+1= 2.1= 0. Do đó −1 ∈ E. Vậy trong mọi trường hợp ta đều có −1 ∈ E. Cho a,b ∈ E. Khi đó g(a) = g(b) = 0. Suy ra aq = a và bq = b. Vì vậy (ab)q = ab, tức là g(ab) = 0. Suy ra ab ∈ E. Chú ý rằng (a+b)q = aq+ ( q 1 ) aq−1b+ ...+ ( q q−1 ) abq−1+bq, trong đó ( q k ) = q! k!(q− k)! là số tổ hợp chập k của q phần tử. Vì q= p d và p nguyên tố nên bằng quy nạp ta kiểm tra được ( q k ) là bội của p với mọi k= 1, ...,q−1. Do đó ta có ( q q ) aq−kbk = 0 với mọi k= 1, ...,q−1. Suy ra (a+b)q = aq+bq = a+b, tức là g(a+b) = 0. Vì thế a+b ∈ E. Cho 0 6= a ∈ E. Khi đó aq = a. Chú ý rằng q≥ 2. Do a 6= 0 nên a có nghịch đảo a−1 ∈ F . Vì vậy, từ aq = a ta suy ra aq−1 = 1. Chú ý rằng (aq−2)q = (aq)q−2 = aq−2. Vì thế aq−2 ∈ E và do đó aq−2 là nghịch đảo của a trong E. Vậy E là một trường. (ii) Vì K là trường hữu hạn nên K có đặc số p nguyên tố và q là một lũy thừa của p. Tương tự, do T là trường hữu hạn nên T có đặc số p′ nguyên tố và q 18 là một lũy thừa của p′. Vì thế p, p′ là ước nguyên tố duy nhất của q. Suy ra p= p′. Theo chứng minh Bổ đề 2.1.9, K,T đều chứa trường con Zp. Tương tự lập luận như trong chứng minh (i) ta suy ra đa thức g(x) = xq−x ∈ Zp[x] không có nghiệm bội trong bất cứ mở rộng nào của Zp. Cho a ∈ K. Nếu a= 0 thì rõ ràng a là nghiệm của g(x). Giả sử a 6= 0. Đặt K∗ = K\{0}. Khi đó K∗ là một nhóm với phép nhân. Cấp của K∗ là q−1 và 1 chính là phần tử đơn vị của nhóm nhân K∗. Vì a 6= 0 nên a ∈ K∗. Do đó aq−1 = 1. Suy ra aq = a. Vì thế a là nghiệm của g(x). Vì thế các phần từ của K chính là các nghiệm của g(x). Do đó K là trường phân rã của g(x) trên Zp. Tương tự, T cũng là trường phân rã của g(x) trên Zp. Suy ra K ∼= T .  Như vậy, với q là số tự nhiên, tồn tại (duy nhất) một trường có q phần tử nếu và chỉ nếu q là lũy thừa của một số nguyên tố. Do đó tồn tại trường có 27 (27 = 33) phần tử, nhưng không tồn tại trường có 12 (12 = 22.3) phần tử. Ví dụ 2.1.11. Xây dựng trường có 4 phần tử. Lời giải. Theo xây dựng trong định lí trên, trường F có 4 phần tử là trường phân rã của đa thức x4− x trên Z2. Gọi 4 nghiệm của x4− x là 0,1,a,b. Khi đó a,b là nghiệm của x2+ x+ 1. Theo chứng minh Bổ đề 2.1.6 với I = (x2+ x+1), trường Z2[x]/I = {0+ I,1+ I,x+ I,x+1+ I} chứa Z2 và chứa hai nghiệm của x2+ x+1. Suy ra {a,b} = {x+ I,x+1+ I}. Kí hiệu 0 là phẩn tử 0+ I ∈ Z2[x]/I. Khi đó trường F có 4 phần tử là 0,1,a,b với bảng toán cộng là: 0+0= 0,0+1= 1,0+a= a,0+b= b 1+0= 1,1+1= 0,1+a= b,1+b= a a+0= a,a+1= b,a+a= 0,a+b= 1 b+0= b,b+1= a,b+b= 0,b+a= 1 và bảng toán nhân là 0.0= 0,0.1= 0,0.a= 0,0.b= 0 1.0= 1,1.1= 0,1.a= a,1.b= b 19 a.0= 0,a.1= a,a.a= b,a.b= 1 b.0= 0,b.1= b,b.a= 1,b.b= a. 2.2 Thuật toán Berlekamp Trong suốt tiết này ta vẫn giả thiết K là một trường. Trước hết chúng ta liệt kê một số tính chất quen biết của đa thức trên trường K. Các tính chất này sẽ được sử dụng trong trong chứng minh các kết quả. Chú ý 2.2.1. Cho K là một trường tùy ý. Cho f (x),g(x) ∈ K[x] là hai đa thức không đồng thời bằng 0. (i) Chúng ta luôn thực hiện được phép chia cho đa thức khác 0. Cụ thể, nếu g(x) 6= 0 thì tồn tại duy nhất cặp đa thức q(x),r(x) ∈ K[x] sao cho f (x) = g(x)q(x)+ r(x) với r(x) = 0 hoặc degr(x)< degg(x). (ii) Tồn tại ước chung lớn nhất của f (x) và g(x), tức là tồn tại một đa thức d(x) ∈ K[x] có hệ số cao nhất bằng 1 là ước chung của f (x),g(x) và là bội của mọi ước chung khác của f (x),g(x). Để tìm ước chung lớn nhất của hai đa thức, chúng ta có thuật toán Euclid (xem [1, Chương 1]). (iii) Giả sử deg f (x) = n> 0 và c là hệ số cao nhất của f (x). Nếu a1, . . . ,an là n nghiệm (có thể không phân biệt) của f (x) thì f (x) = c(x−a1) . . .(x−an). (iv) Mỗi iđêan của vành đa thức K[x] đều là iđêan chính. Cụ thể, nếu I là iđêan của K[x] thì tồn tại đa thức h= h(x) ∈ K[x] sao cho I = (h) = {hk | k ∈ K[x]} . (v) Nếu f = gq+ r thì ước chung lớn nhất của f và g chính là ước chung lớn nhất của g và r. (vi) Nếu d(x) là ước chung lớn nhất của f (x) và g(x) thì tồn tại các đa thức 20 h(x),k(x) ∈ K[x] sao cho d(x) = f (x)h(x)+g(x)k(x). Từ đây đến hết luận văn, nếu f ,g ∈ K[x] là hai đa thức thì ta kí hiệu gcd( f ,g) là ước chung lớn nhất của f và g. Như vậy, gcd( f ,g) là một ước chung của f và g, có hệ số cao nhất bằng 1, và là bội của mọi ước chung khác của f và g. Bổ đề 2.2.2. Cho K là một trường. Nếu f (x),g(x),h(x) ∈ K[x] sao cho gcd(g,h) = 1 thì gcd( f ,gh) = gcd( f ,g)gcd( f ,h). Chứng minh. Đặt d = gcd( f ,hg), d1= gcd( f ,g) và d2= gcd( f ,h). Rõ ràng d1,d2 là ước của d. Vì gcd(g,h) = 1 nên gcd(d1,d2) = 1. Vậy d1d2 là ước của d.  Tiếp theo, ta cần nhắc lại kết quả sau đây, được gọi là Định lý thặng dư Trung Hoa. Trước hết, nhắc lại rằng nếu X1, . . . ,Xr là các vành thì tập hợp ⊕ i=1,...,r Xi = X1⊕X2⊕ . . .⊕Xr = {(x1,x2, . . . ,xr) | xi ∈ Xi} làm thành một vành với phép cộng (x1,x2, . . . ,xr)+(x′1,x ′ 2, . . . ,x ′ r) = (x1+ x ′ 1,x2+ x ′ 2, . . . ,xr+ x ′ r). và phép nhân (x1,x2, . . . ,xr)(x′1,x ′ 2, . . . ,x ′ r) = (x1x ′ 1,x2x ′ 2, . . . ,xrx ′ r). Vành X1 ⊕ X2 ⊕ . . .⊕ Xr được gọi là vành tổng trực tiếp của các vành X1, . . . ,Xr. Bổ đề 2.2.3. Cho K là trường và f1, . . . , fr ∈ K[x] là các đa thức sao cho gcd( fi, f j) = 1 với mọi i 6= j. Đặt f = f1 . . . fr. Đặt I = ( f ) là iđêan sinh bởi f và Ii = ( fi) là iđêan sinh bởi fi. Khi đó ta có đẳng cấu vành K[x]/I ∼= ⊕ i=1,...,r K[x]/Ii. 21 Chứng minh. Bằng quy nạp ta chỉ cần chứng minh với r= 2. Đặt X = K[x]. Xét tương ứng ϕ : X/I→ X/I1⊕X/I2 cho bởi ϕ(g+ I) = (g+ I1,g+ I2). Giả sử g+ I = h+ I. Khi đó g− h ∈ I, tức là g−h là bội của f = f1 f2. Suy ra g−h là bội của f1 và cũng là bội của f2. Do đó g−h ∈ I1 và g−h ∈ I2, tức là (g+ I1,g+ I2) = (h+ I1,h+ I2). Vì thế ϕ là ánh xạ. Dễ kiểm tra được ϕ là đồng cấu vành, tức là ϕ((g+ I)+(h+ I)) = ϕ(g+ I)+ϕ(h+ I) ϕ((g+ I)(h+ I)) = ϕ(g+ I)ϕ(h+ I) ϕ((1+ I) = (1+ I1,1+ I2) với mọi g+ I,h+ I ∈ X/I. Giả sử ϕ(g+ I) = ϕ(h+ I). Khi đó (g+ I1,g+ I2) = (h+ I1,h+ I2). Suy ra g−h∈ I1 và g−h∈ I2, tức là g−h vừa là bội của f1 vừa là bội của f2. Theo giả thiết, gcd( f1, f2) = 1. Suy ra g−h là bội của f = f1 f2. Do đó g−h ∈ I, tức là g+ I = h+ I. Do đó ϕ là đơn cấu. Lấy một phần tử bất kỳ g+ I1,h+ I2 ∈ X/I1⊕ X/I2. Vì gcd( f1, f2) = 1 nên theo Chú ý 2.2.1(ii) ta có 1 = f1k+ f2t với k, t ∈ X . Suy ra g+ I1 = f1kg+ f2tg+ I1 và h+ I2 = f1kh+ f2th+ I2 = f1kh+ I2. Do đó (g+ I1,h+ I2) = ( f2tg+ I1, f1kh+ I2) = ( f2tg+ f1kh+ I1, f1kh+ f2tg+ I2) = ϕ( f2tg+ I1, f1kh+ I2). Suy ra ϕ là toàn cấu. Vậy ϕ là đẳng cấu.  Kí hiệu 2.2.4. Như đã chứng minh trong Mục 2.1, tồn tại một trường có q phần tử khi và chỉ khi q là lũy thừa của một số nguyên tố p. Trường có q phần tử nếu tồn tại thì nó là duy nhất sai khác một đẳng cấu, tức là nếu T,T ′ là hai trường cùng có q phần tử thì T ∼= T ′. Trong suốt mục này, luôn giả thiết q là một lũy thừa của một số nguyên tố p và Fq là trường có q phần tử. Mục tiêu của mục này là trình bày Thuật toán Berlekamp phân tích đa thức 22 trên trường Fq thành tích các đa thức bất khả quy. Trước hết chúng ta cần các bổ đề sau đây. Bổ đề 2.2.5. Cho f = f (x) và v= v(x) là hai đa thức với hệ số trên trường Fq. Giả sử rằng vq ≡ v(mod f ). Khi đó f = ∏ a∈Fq gcd( f ,v−a). Chứng minh. Vì tồn tại trường có q phần tử nên q = pk với p là một số nguyên tố và k ≥ 1 là một số nguyên dương. Theo chứng minh định lý về sự tồn tại trường hữu hạn có q phần tử trong Mục 2.1, tồn tại một trường E chứa Zp và chứa q nghiệm của đa thức xq− x. Hơn nữa, trường phân rã của đa thức xq−x trên trường Zp chính là trường gồm q phần tử mà các phần tử của nó chính là các nghiệm trong E của đa thức xq− x. Chú ý rằng đa thức xq−x không có nghiệm bội, tức là q nghiệm của xq−x là đôi một phân biệt. Vì thế, Fq = {a ∈ E | aq−a= 0} . Theo Chú ý 2.2.1(iii) ta suy ra đa thức xq−x= ∏ a∈Fq (x−a). Thay x= v vào đẳng thức trên ta được vq− v= ∏ a∈Fq (v−a). Từ giả thiết vq ≡ v(mod f ) ta suy ra vq− v chia hết cho f . Do đó ta có gcd( f ,vq− v) = f . Do đó f = gcd( f ,vq− v) = gcd( f ,∏ a∈Fq (v−a)). Cho a,b∈ Fq với a 6= b. Khi đó v−a= (v−b)+(b−a), trong đó b−a 6= 0. Theo Chú ý 2.2.1(v), ước chung lớn nhất của v− a và v− b chính là ước chung lớn nhất của v− b và b− a. Do b− a 6= 0 nên khả nghịch trong Fq. Vì thế gcd(v−b,b−a) = 1. Do đó nên theo Bổ đề 2.2.2 ta có gcd( f ,(v−a)(v−b)) = gcd( f ,v−a)gcd( f ,v−b). 23 Do đó ta có f = gcd( f ,∏ a∈Fq (v−a)) = ∏ a∈Fq gcd( f ,v−a).  Từ Bổ đề 2.2.5, nếu ta biết được các đa thức v = v(x) ∈ Fq sao cho vq− v≡ 0(mod f ) thì bằng cách dùng thuật toán Euclid tìm ước chung lớn nhất ta có thể phân tích được f = ∏ a∈Fq gcd( f ,v−a). Như vậy, câu hỏi đặt ra tiếp theo là làm thế nào để tìm các đa thức v như thế. Trước khi trả lời câu hỏi này, chúng ta có chú ý sau. Chú ý 2.2.6. Cho K là một trường và f (x) ∈ K[x] là một đa thức bậc dương với hệ số cao nhất là c. Như đã chứng minh trong Mục 1.1, f (x) có phân tích bất khả quy f (x) = c f e11 . . . f er r , trong đó f1, . . . , fr ∈ K[x] là các đa thức bất khả quy dạng chuẩn (có hệ số cao nhất bằng 1) đôi một phân biệt. Hơn nữa, sự phân tích này là duy nhất nếu không kể đến thứ tự các nhân tử. Một đa thức f (x) ∈ K[x] được gọi là nguyên sơ nếu có dạng f (x) = g(x)t , trong đó g(x)∈K[x] là bất khả quy và t > 0 là một số tự nhiên. Chú ý rằng mỗi đa thức với hệ số trên một trường đều viết được thành tích các đa thức nguyên sơ và số thành phần nguyên sơ không phụ thuộc vào phân tích, tức là nếu f (x) = f e11 . . . f er r = g t1 1 . . .g ts s , trong đó fi 6= f j và gi 6= g j với mọi i 6= j, là hai phân tích của f thành tích các đa thức nguyên sơ đôi một phân biệt thì r = s. Bổ đề 2.2.7. Cho f (x) ∈ Fq[x] là đa thức. Giả sử f = f e11 . . . f err là phân tích của f thành tích các đa thức nguyên sơ. Kí hiệu V là tập các đa thức v(x) ∈ Fq[x] sao cho vq ≡ v(mod f ). Khi đóV là một không gian véc tơ trên trường Fq và chiều của không gian này là r. Chứng minh. Chú ý rằng Fq[x] là một Fq-không gian véc tơ (vô hạn chiều), một cơ sở của nó là { 1,x,x2, . . . ,xn, . . . } . Vì thế, để chứng minh tập con V của Fq[x] là Fq-không gian véc tơ, chúng ta chỉ cần chứng minh V là không gian con của Fq[x], tức là V đóng kín với phép cộng, đóng kín phép nhân vô hướng và chứa đa thức 0. Rõ ràng 0q≡ 0(mod f ). Do đó 0∈V . Cho u1,u2 ∈V . Khi đó uq1≡ u1(mod f ) 24 và uq2 ≡ u2(mod f ). Giả sử q= pk với p là số nguyên tố. Khi đó trường Fq có đặc số p. Suy ra pg(x) = 0 với mọi g(x) ∈ Fq[x]. Đặt Cnq = q! n! (q− n)!. Do q = pk với p nguyên tố nên chúng ta dễ dàng kiểm tra được Cnq là bội của p với mọi n = 1, . . . ,q− 1. Suy ra Cnqg(x) = 0 với mọi g(x) ∈ Fq[x] và mọi i= 1, . . . ,q−1. Do đó (u1+u2)q = u q 1+u q 2 ≡ u1+u2(mod f ). Suy ra u1+u2 ∈V . Cho u ∈V và a ∈ Fq. Nếu a= 0 thì rõ ràng au= 0 ∈V . Giả sử a 6= 0. Khi đó a ∈ Fq\{0}. Chú ý rằng Fq\{0} là một nhóm nhân và cấp của nó(số phần tử của nó) là q− 1. Vì thế aq−1 = 1. Suy ra aq = a. Vì u ∈ V nên uq ≡ u(mod f ). Suy ra (au)q = aquq ≡ au(mod f ). Suy ra au ∈V . Vậy V là một không gian véc tơ trên trường Fq. Cuối cùng, ta chứng minh chiều của V là r. Vì các fi là bất khả quy và fi 6= f j với mọi i 6= j nên gcd( f eii , f e j j ) = 1 với mọi i 6= j. Do đó theo Bổ đề 2.2.3 ta có đẳng cấu ϕ : Fq[x]/ f ∼= ⊕ i=1,...,r Fq[x]/( f eii ). Đặt I = ( f ) và Ii = ( f ei i ) với mọi i. Cho u ∈ Fq[x] tùy ý, ta có ϕ(u+ I) = (u+ I1, . . . ,u+ Ir). Khi đó u ∈ V nếu và chỉ nếu uq ≡ u(mod f ), khi và chỉ khi uq−u ∈ I, khi và chỉ khi (uq−u)+ Ii = 0+ I, khi và chỉ khi (uq−u+ I1, . . . ,uq−u+ Ir) = (0+ I1, . . . ,0+ Ir), khi và chỉ khi uq−u ∈ Ii với mọi i, khi và chỉ khi uq ≡ u(mod fi) với mọi i. 25 Như vậy, giả sử u ∈V thì theo Bổ đề 2.2.5 ta có f eii = ∏ a∈Fq gcd( f eii ,v−a). Vì thế, với mỗi i ta có fi là ước của ∏ a∈Fq gcd( f eii ,v− a). Do fi bất khả quy nên fi là ước của một nhân tử v−c nào đó với c ∈ Fq. Cho b ∈ Fq với b 6= c. Khi đó v− c = (v− b)+ (b− c). Chú ý rằng b− c 6= 0 và vì thế b− c khả nghịch, do đó theo Chú ý 2.2.1(iv) ta có gcd(c− v,v−b) = gcd(v−b,b− c) = 1. Vì fi là ước của v−c nên fi không thể là ước của v−b với mọi b ∈ Fq\{c}. Suy ra gcd( f eii , ∏ c 6=b∈Fq gcd( f eii ,v− c)) = 1. Suy ra f eii là ước của gcd( f ei i ,v− c). Do đó f eii là ước của v− c, tức là v≡ c(mod f eii ). Như vậy, với mỗi u ∈V , tồn tại các phần tử c1, . . . ,cr ∈ Fq sao cho ϕ(u+ I) = (c1+ I1, . . . ,cr+ Ir). Do đó ta có thể đồng nhất ϕ(V )⊂ ⊕ i=1,...,r Fi, trong đó Fi = Fq,∀i= 1, . . . ,r. Ngược lại, cho (c1, . . . ,cr) ∈ ⊕ i=1,...,r Fi, trong đó Fi = Fq,∀i. Vì ϕ là đẳng cấu nên tồn tại u∈ Fq[x] sao cho ϕ(u+ I) = (c1+ I1, . . . ,cr+ Ir). Nếu ci= 0 thì rõ ràng cqi ≡ ci(mod f eii ) với mọi i= 1, . . . ,r. Suy ra uq≡ u(mod f ). Suy ra u ∈V . Vì thế (c1+ I1, . . . ,cr+ Ir) ∈ ϕ(V ). Do vậy, ϕ(V )⊂ ⊕ i=1,...,r Fi, trong đóFi = Fq,∀i= 1, . . . ,r. Vì thế ϕ(V ) là Fq-không gian véc tơ chiều r. Do ϕ là đẳng cấu nên V là Fq-không gian véc tơ chiều r.  26 Để tìm một cơ sở của Fq-không gian véc tơ V xác định như trong Bổ đề 2.2.7, ta chỉ việc giải một hệ phương trình tuyến tính (với các ẩn số của đa thức u ∈ V ) thu được bằng cách đồng nhất các hệ số của hai đa thức ở hai vế của phương trình uq ≡ u(mod f ). Sau đây ta trình bày một ví dụ minh họa. Ví dụ 2.2.8. Cho q = 3 và f (x) = x5+ 5x4+ 4x3+ 16x2+ 8x+ 1. Gọi V là F3-không gian con của F3[x] gồm các đa thức u sao cho u3 ≡ u(mod f ). Hãy xác định chiều và một cơ sở của V . Lời giải. Giả sử u ∈ V với u = f q+ r, trong đó r = 0 hoặc r ≤ 4. Dễ thấy rằng u3 ≡ u(mod f ) nếu và chỉ nếu r3 ≡ r(mod f ). Vì thế ta có thể giả thiết degu < 5, tức là u = a4x4+ a3x3+ a2x2+ a1x+ a0 ∈ V . Chú ý rằng 3ai = 0 với mọi ai ∈ F3 và a3i = a với mọi ai ∈ F3. Do đó u3(mod f ) = a4x12+a3x9+a2x6+a1x3+a0. Suy ra 0≡ u3−u (mod f ) ≡ a4x12+a3x9−a4x4+a2x6+(a1−a3)x3−a2x2−a1x(mod f ) ≡ 2a4x4+(2a4+2a3+a2+a1)x3+2a1x+(a3+a2)(mod f ). Suy ra  2a4 = 0 2a4+2a3+a2+a1 = 0 2a1 = 0 a3+a2 = 0. Giải hệ ta được a4 = a3 = a2 = a1 = 0. Do đó V có số chiều là 1, tức là f là đa thức nguyên sơ. Vì thế, f = ge trong đó g là bất khả quy trên F3 và e là một số tự nhiên. Chúng ta sẽ sử dụng ví dụ này trong Tiết 2.3. Bây giờ chúng ta trình bày Thuật toán Berlekamp, đây chính là một trong các kết quả chính của luận văn này. Elwyn Ralph Berlekamp (sinh ngày 06 tháng 9 năm 1940) ở Dover, Bang 27 Oshio là một nhà toán học người Mỹ. Ông là giáo sư danh dự của Đại học California, Berkeley. Ông nổi tiếng với những công trình trong lí thuyết mã hóa và lí thuyết trò chơi tổ hợp. Ông học đại học tại Viện Công nghệ Massachusetts, nhận bằng đại học và bằng thạc sĩ về kĩ thuật điện năm 1962. Năm 1964 ông nhận băng tiến sĩ về Kĩ thuật điện. Sau đó giảng dạy Kĩ thuật điện tại Đại học California, Berkeley từ năm 1964 đến năm 1966, trong thời gian đó ông quan tâm đến Toán học và trở thành một nhà nghiên