Xem mẫu
- KỈ YẾU HỘI NGHỊ SINH VIÊN NGHIÊN CỨU KHOA HỌC NĂM HỌC 2013-2014
MỘT SỐ TÍNH CHẤT CỦA TRƢỜNG HỮU HẠN
ĐA THỨC TRÊN TRƢỜNG HỮU HẠN
Phạm Bá Đức, Nguyễn Thị Ngọc Anh, Lớp K61CLC, Khoa Toán – Tin
GVHD: ThS. Nguyễn Hữu Kiên
Tóm tắt: Trường hữu hạn là một vấn đề hay của Đại số hiện đại, nó có nhiều ứng dụng trong hình
học hữu hạn, trong đại số tổ hợp, hay trong lí thuyết mật mã... Do đó đề tài báo cáo lần này chủ yếu
xoay quanh một số tính chất của trường hữu hạn và của đa thức trên trường hữu hạn. Đây là những
kiến thức cơ sở và cơ bản nhất để chúng ta có thể tiếp tục tìm hiểu về ứng dụng của trường hữu hạn
trong Toán học. Các kết quả chính bao gồm cấu trúc một trường hữu hạn, phân tích một đa thức
thành các nhân tử bất khả quy.
Từ khóa: Trường hữu hạn, đa thức trên trường hữu hạn, phân tích đa thức thành nhân tử trên trường
hữu hạn.
I. MỞ ĐẦU
Cho F là một trƣờng có hữu hạn phần tử. Khi đó char F là số nguyên tố và số
lƣợng phần tử của F là p n . Ngƣợc lại, với p, n cố định thì luôn tồn tại một trƣờng hữu
hạn có p n phần tử (sai khác một đẳng cấu). Kí hiệu trƣờng hữu hạn có q p n phần tử là
Fq . Khi đó ta xét các đa thức trên Fq .
Đề tài đặt ra vấn đề tìm hiểu phân tích một đa thức thành các nhân tử bất khả quy,
đánh giá về định lƣợng và định tính của phân tích. Trƣớc hết là định lƣợng thông qua đánh
giá số nghiệm phƣơng trình X q X trên Fq [ x] / ( f ( x)) . Tiếp theo ta đi tìm biểu diễn các
nhân tử của phân tích thông qua các nghiệm của phƣơng trình X q X trên
Fq [ x] / ( f ( x)) . Từ đó mô tả các nhân tử và bậc lũy thừa của các nhân tử trong phân tích.
Các kết quả đƣợc trình bày là các kết quả đã biết về tính chất chung của trƣờng hữu
hạn và đa thức trên trƣờng hữu hạn. Mục đích các tác giả là chứng minh các kết quả một
cách độc lập sơ cấp và ngắn gọn, chỉ sử dụng các kết quả đã học trong học phần ĐSĐC và
lí thuyết Galois. Các kết quả sâu hơn về đề tài đòi hỏi thời gian nghiên cứu dài hơn và các
công cụ mạnh hơn.
Đề tài đƣợc chia thành 3 mục nhỏ. Mục 1 trình bày một số kiến thức về đại số đại
cƣơng. Mục 2 trình bày về những kết quả, tính chất và cấu trúc của trƣờng hữu hạn. Mục 3
dành cho việc phân tích một đa thức bất khả quy trên trƣờng phân rã và phân tích một đa
thức thành các nhân tử bất khả quy. Sau đó tiến hành xem xét 1 đa thức, đặc biệt là đa thức
cyclotomic và việc phân tích đa thức này thành nhân tử bất khả quy.
II. NỘI DUNG
1. Nhắc lại kiến thức về đại số đại cƣơng
Phần này đề tài chủ yếu đƣa ra những kiến thức cơ bản và những tính chất cần thiết sử
dụng đến trong các chứng minh ở các phần tiếp theo về: nhóm, vành, trường.
16
- KỈ YẾU HỘI NGHỊ SINH VIÊN NGHIÊN CỨU KHOA HỌC NĂM HỌC 2013-2014
Ở đây khi nhắc đến vành ta chỉ xét vành có đơn vị 1.
Ngoài ra ta còn nghiên cứu các tính chất của đa thức nhƣ nghiệm của đa thức, đa
thức bất khả quy và lí thuyết Galois về các mở rộng trƣờng.
Trong đề tài sử dụng kí hiệu đa thức tối thiểu bậc n của c trên trƣờng K là:
p( x) min(n, K , c), n deg p( x) để phân biệt với đa thức bất quả quy bậc m trên F là
f ( x) irr (m, F ) .
2. Một số vấn đề về trƣờng hữu hạn
Ta xem xét các đặc trƣng cần dùng đến của trƣờng hữu hạn qua các định lí sau:
Định lí 2.1: Nếu F là trƣờng hữu hạn thì char F là một số nguyên tố.
Từ đây nếu không nói gì thêm, ta gọi đặc số của các trƣờng hữu hạn là p, p nguyên tố.
F * F \{0} là nhóm các phần tử khả nghịch trong trƣờng hữu hạn F .
Fq*r {x r | x Fq* , r *
}.
Nhận xét 2.2 a Fq a q a,| Fq | q .
Bổ đề 2.3: Cho F là trƣờng hữu hạn chứa trƣờng con K , charK q, n [ F : K ] thì
| F | q n .
Định lí 2.4: Cho Fq $,$ K là trƣờng con của Fq . Khi đó, đa thức
f ( x) x q x K[ x] thì x q x ( x a ), x a F [ x] và F
ai Fq
i i q q là trƣờng phân rã
của đa thức f ( x) trên K .
Định lí 2.5: | Fq | p n , n N .
*
Định lí 2.6: Cho Fq , p( x) irr (n, Fq [ x]) thì Fq [ x] / ( f ( x)) là trƣờng hữu hạn có q n
phần tử.
Định lí 2.7: Với mỗi số nguyên tố p và mỗi số nguyên dƣơng n đều tồn tại trƣờng
hữu hạn cấp p n . Mọi trƣờng hữu hạn có q p n phần tử thì đẳng cấu với trƣờng phân rã
của đa thức x x trên Fq .
q
Định lí 2.8: Mọi trƣờng con của trƣờng có p n phần tử đều có p m phần tử với m | n .
Ngƣợc lại, nếu m | n thì Fp n có duy nhất 1 trƣờng con chứa p m phần tử.
Định lí 2.9: Fq* là cyclic.
q 1
Định lí 2.10: Fq*r Fq* và | Fq*r | . Nếu d gcd (r , q 1) thì
gcd (r , q 1)
Fq*r Fq*d , Fq* : Fq*d d
17
- KỈ YẾU HỘI NGHỊ SINH VIÊN NGHIÊN CỨU KHOA HỌC NĂM HỌC 2013-2014
3. Đa thức trên trƣờng hữu hạn
3.1. Nghiệm của đa thức bất khả quy trên trường hữu hạn
Ta xem xét đa thức bất khả quy f ( x) Fq [ x] . Vì không thể phân tích đa thức này
thành nhân tử thực sự trên Fq [ x] , ta đi tìm trƣờng phân rã của nó và biểu diễn các nghiệm
của nó trên trƣờng phân rã này.
Bổ đề 3.1: Cho f ( x) Fq [ x], f ( x) irr (m, Fq ) và n *
. Khi đó f ( x) chia hết
x q x nếu và chỉ nếu m chia hết n
n
Định lí 3.2: Cho f ( x) Fq [ x], f ( x) irr (m, Fq ) . Khi đó f ( x) phân rã trên Fq m và
m 1
tách đƣợc trên Fq . Hơn nữa nếu là nghiệm của f ( x) thì { , q , q , , q } là tập hợp
2
tất cả các nghiệm của f ( x) .
Hệ quả 3.3: Trƣờng phân rã của đa thức bất khả quy f Fq [ x] là Fq m
m 1
Định nghĩa 3.4: Cho Fqm . Khi đó các phần tử , q , q , , q
2
đƣợc gọi là
các phần tử liên hợp với trên Fq .
Định lí 3.5: Cho trƣờng hữu hạn Fq , Fq* . Khi đó các phần tử liên hợp với trên
trƣờng con bất kì của Fq có cùng cấp trong nhóm Fq* .
Hệ quả 3.6: Nếu là phần tử nguyên thủy của Fq thì mọi phần tử liên hợp với
trên một trƣờng con bất kì của Fq cũng là phần tử nguyên thủy của Fq .
Định lí 3.7: Cho Fqn . Khi đó nếu d là số nguyên dƣơng nhỏ nhất thỏa mãn
d 1
q thì đa thức f ( x) ( x )( x q )( x q ) ( x q ) bất khả quy trên Fq .
d 2
3.2. Phân tích đa thức thành nhân tử
Xét đa thức f ( x) Fq [ x] bất kì. Một câu hỏi tự nhiên đặt ra là phân tích đa thức này
thành nhân tử bất khả quy thì định lƣợng và định tính nhƣ thế nào? Tức số lƣợng các nhân
tử bất khả quy, biểu diễn các nhân tử bất khả quy đó cũng nhƣ lũy thừa của mỗi nhân tử
trong phân tích của đa thức f ( x) là bao nhiêu? Mục này của bài viết sẽ trình bày tƣơng
đối trọn vẹn câu hỏi này.
Bổ đề 3.8: Cho g ( x) Fq [ x] và s1 , s2 là 2 phần tử khác nhau của Fq . Khi đó
gcd ( g ( x) s1 , g ( x) s2 ) 1 .
18
- KỈ YẾU HỘI NGHỊ SINH VIÊN NGHIÊN CỨU KHOA HỌC NĂM HỌC 2013-2014
Bổ đề 3.9: Cho f ( x) là một đa thức có hệ tử của bậc cao nhất là 1 trong Fq [ x] và
g ( x) Fq [ x] . Khi đó g ( x) thỏa mãn g ( x)q g ( x)(mod f ( x)) nếu và chỉ nếu
f ( x) | ( g (x) s) nếu và chỉ nếu f ( x) | gcd ( f ( x), g ( x) s) .
sFq sFq
Định lí 3.10: Cho f ( x) là đa thức có hệ tử của bậc cao nhất là 1 trong Fq [ x] và
g ( x) Fq [ x] sao cho g ( x)q g ( x)(mod f ( x)) . Khi đó
f ( x) gcd ( f ( x), g ( x) s).
sFq
Ta đánh giá định lƣợng số lƣợng nhân tử bất khả quy trong khai triển.
Định lí 3.11: Cho f ( x) là đa thức bậc dƣơng trên Fq . Khi đó số nghiệm của phƣơng
trình X q X trên vành Fq [ x] / ( f ( x) là q r khi và chỉ khi f ( x) phân tích thành tích lũy
thừa của r đa thức bất khả quy trên Fq [ x]
Nhận xét 3.12: f ( x) là đa thức bậc n trên Fq . Khi đó Fq [ x] / ( f ( x)) là không gian
véc tơ với cơ sở 1, x, x 2 ,..., x n .
Đặt V {g ( x) Fq [ x] / ( f ( x)) sao cho g ( x)q g ( x)(modf ( x))} thì V là không
gian con của Fq [ x] / ( f ( x)) chứa mọi nghiệm của X X , dimFqV r số nghiệm của
q
X q X là r
Ta đánh giá định tính qua việc xây dựng các nhân tử.
Bây giờ ta đi chứng minh 1 tập các nghiệm độc lập tuyến tính của X q X trong
Fq [ x] / ( f ( x)) xác định tất cả các nhân tử của f ( x)
Gọi g1 ( x) 1, g 2 ( x),..., g r ( x) là tập nghiệm độc lập tuyến tính của X q X .
Rõ ràng ta có f ( x) gcd ( f ( x), g ( x) s)
sFq
2
m
Khi đó sau khi loại đi các nhân tử có tích bằng 1 thì ta thu đƣợc f ( x) f ( x) trong
i 1
i
đó fi ( x) là biểu thức có dạng gcd ( f ( x), g 2 ( x) s) trong đó fi , f j nguyên tố cùng nhau.
Nếu m r , thì bài toán đã đƣợc giải quyết.
Nếu m r ta chứng minh bổ đề sau.
Bổ đề 3.13: Giả sử m r . Chứng minh i 3, r , j 1, m sao cho
gi ( x) s(mod ( f j ( x))s Fq
19
- KỈ YẾU HỘI NGHỊ SINH VIÊN NGHIÊN CỨU KHOA HỌC NĂM HỌC 2013-2014
Khi đó với việc khai triển một nhân tử chƣa bất khả quy, ta thu đƣợc phân hoạch mịn
hơn với m phần tử.
Bổ đề 3.14: Giả sử m r thì i 4, r , j 1, m sao cho
gi ( x) s(mod f 2 j )s Fq
Tiếp tục quá trình ta thu đƣợc f ( x) có thể phân tích thành tích lũy thừa các đa thức
bất khả quy trên Fq
Bây giờ ta đánh giá nhân tử và lũy thừa của nó qua định lí sau:
Định lí 3.15: Cho f ( x) là lũy thừa của một đa thức bất khả quy trên Fq và giả sử
rằng f ( x) 0
i) Nếu gcd ( f ( x), f ( x)) 1 thì f ( x) là đa thức bất khả quy.
f ( x)
ii) Nếu gcd ( f ( x), f ( x)) 1 thì p( x) là đa thức bất khả quy.
gcd ( f ( x), f ( x))
deg f ( x)
Khi đó f ( x) p( x)m với m
deg p( x)
3.3. Đa thức chia đường tròn
Cho K là trƣờng charK p (p có thể bằng 0) và n *
. Ta gọi trƣờng phân rã
trên K của đa thức x 1 K[ x] là trƣờng n-cyclotomic trên K . Kí hiệu K ( n ) .
n
Mỗi nghiệm trong K ( n ) của đa thức x n 1 đƣợc gọi là một căn bậc n của đơn vị
trên K . Kí hiệu E ( n ) là tập hợp tất cả các căn bậc n trên K của đơn vị.
Cho K là trƣờng char K p, n *
không chia hết cho p . Ta gọi mỗi phần tử
(n)
sinh của nhóm cyclic E là một căn nguyên thủy bậc n trên K của đơn vị.
Cho K là 1 trƣờng có đặc số p, n N * , là căn nguyên thủy của đơn vị. Khi đó ta
n
có đa thức Qn ( X ) ( x
s 1
s
) với (s, n) 1 . Đa thức Qn đƣợc gọi là đa thức chia
đƣờng tròn trên K .
Định lí 3.16: Cho K là trƣờng char K p (p có thể bằng 0) và n *
. Khi đó
E ( n ) là một nhóm cyclic có cấp không chia hết cho p . Cụ thể: \ (i) Nếu p n thì E ( n ) là nhóm cyclic cấp n\ (ii) Nếu p n và n mp s , p m thì K ( m) K ( n ) , E ( n ) E ( m) là nhóm cyclic cấp m .
Nhận xét 3.17: Có tất cả (n) căn nguyên thủy bậc n trên K của đơn vị.
Định lí 3.18: Cho K là một trƣờng đặc số p và n N * sao cho (n, p) 1 . Khi đó
20
- KỈ YẾU HỘI NGHỊ SINH VIÊN NGHIÊN CỨU KHOA HỌC NĂM HỌC 2013-2014
(i) x n 1 Q ( x)
d |n
d
(ii) Hệ số của Qn thuộc trƣờng con nguyên tố của K và thuộc nếu K Q
Định lí 3.19: Trƣờng chia đƣờng tròn K ( n ) là mở rộng đơn của K
(i) Nếu K Q thì Qn bất khả quy và [ K ( n ) : K ] (n)
(ii) K Fq , gcd (q, n) 1 thì Qn tách thành (n) / d đơn thức bậc d . Khi đó K ( n )
là trƣờng phân rã của mọi nhân tử và [ K ( n ) : K ] d với d là số nguyên dƣơng nhỏ nhất
sao cho q d 1(modn)
Hệ quả 3.20 Cho q p k với p là số nguyên tố và giả sử rằng p n . Khi đó Qn là
đa thức bất khả quy trên Fq khi và chỉ khi (n) là số nguyên dƣơng nhỏ nhất sao cho
q ( n) 1(modn)
Bài tập và áp dụng
Đề tài đƣa ra một số bài tập nhằm giúp bạn đọc có thể hiểu sâu và vận dụng tốt hơn
những lí thuyết đã trình bày trong bản báo cáo. Ngoài ra còn có 2 bài tập tác giả đƣa ra
hƣớng đến một cách tiếp cận mới để giải quyết vấn đề giải phƣơng trình bậc 2 trên trƣờng
hữu hạn đặc số 2 .
Xét phƣơng trình: ax 2 bx c 0 trên trƣờng F , a, b, c F , a 0 .
b (b 2 4ac)
Nếu charF 2 thì ta có công thức nghiệm: x .
2a
Nếu charF 2 thì công thức nghiệm trên không còn đúng. Vậy nghiệm của phƣơng
trình bậc hai trên trƣờng hữu hạn F2n là gì?
TÀI LIỆU THAM KHẢO
[1] Dƣơng Quốc Việt, Lê Văn Chua, Cơ sở lí thuyết Galois, NXB ĐHSP.
[2] Dƣơng Quốc Việt, Đàm Văn Nhỉ, Cơ sở lí thuyết số và đa thức, NXB ĐHSP.
[3] Hoàng Xuân Sính, Đại số đại cương, NXB Giáo dục.
[4] Nguyễn Tiến Quang, Cơ sở lí thuyết trường và lí thuyết Galoa, NXB ĐHSP.
[5] Jean Pierre Serre, A course in arithmatic, 1996.
[6] Jurgen Neukirch, Algebraic number theory, 1999, Springer.
[7] H.Lidl, H.Niederreiter, Introduction to finite fields and their applications, Cambridge
University Press, 1986.
[8] Zhe-Xian Wan, Lectures on finite fields and Galois rings, Penguin, 2003.
21
nguon tai.lieu . vn