Lời cảm ơn ii
Mở đầu 1
Chương 1. Đa thức bất khả quy 3
1.1 Khái niệm đa thức bất khả quy . . . . . . . . . . . . . . . 3
1.2 Một số tiêu chuẩn bất khả quy trên trường Q . . . . . . . . 7
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ử 13
2.1 Trường phân rã của đa thức, trường hữu hạn . . . . . . . . 13
2.2 Thuật toán Berlekamp . . . . . . . . . . . . . . . . . . . . 19
2.3 Tính bất khả quy trên Zp và ứng dụng phân tích bất khả quy
trên Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Kết luận 39
Tài liệu tham khảo 40
44 trang |
Chia sẻ: honganh20 | Ngày: 28/02/2022 | Lượt xem: 644 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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
Các file đính kèm theo tài liệu này:
- luan_van_da_thuc_bat_kha_quy_tren_truong_zp_thuat_toan_berle.pdf