ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

VŨ ĐỨC CẢNH

Đ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

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2016


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

VŨ ĐỨC CẢNH

Đ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

LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số: 60 46 01 13

NGƯỜI HƯỚNG DẪN KHOA HỌC:
GS.TS. Lê Thị Thanh Nhàn

THÁI NGUYÊN - 2016


i

Mục lục
Lời cảm ơn

ii

Mở đầu

1

Chương 1. Đa thức bất khả quy

3

1.1
1.2

Khái niệm đa thức bất khả quy . . . . . . . . . . . . . . .
Một số tiêu chuẩn bất khả quy trên trường Q . . . . . . . .

3
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
2.2

Trường phân rã của đa thức, trường hữu hạn . . . . . . . .
Thuật toán Berlekamp . . . . . . . . . . . . . . . . . . . .

13
19

2.3

Tính bất khả quy trên Z p 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


ii

Lời cảm ơn


Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học
Thái Nguyên và hoàn thành dưới sự hướng dẫn của GS.TS. Lê Thị Thanh
Nhàn. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người
hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều
thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong
suốt quá trình làm luận văn.
Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học
- Đại học Thái Nguyên, Ban Chủ nhiệm Khoa Toán-Tin, cùng các giảng
viên đã tham gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tác giả học tập
và nghiên cứu.
Tác giả cũng xin chân thành cảm ơn Phòng Giáo dục và Đào tạo huyện
Tiên Lãng, Ban giám hiệu và các đồng nghiệp trường THCS Vinh Quang,
huyện Tiên Lãng, thành phố Hải Phòng đã tạo điều kiện cho tác giả hoàn
thành tốt nhiệm vụ học tập và công tác của mình.
Nhân dịp này, tác giả cũng xin gửi lời cảm ơn tới tập thể lớp cao học
Toán K8B (khóa 2014-2016), cảm ơn gia đình bạn bè đã động viên và giúp
đỡ tác giả rất nhiều trong quá trình học tập.


1

Mở đầu

Luận văn quan tâm đến bài toán phân tích đa thức với hệ số nguyên
thành nhân tử bất khả quy trên Q. Đây là một trong những bài toán quan
trọng nhất của Lí thuyết đa thức.
Ta biết rằng bài toán xét tính bất khả quy của đa thức trên Q có liên
quan mật thiết với bài toán xét tính bất khả quy của đa thức trên trường hữu
hạn. Cho f (x) là đa thức với hệ số nguyên. Nếu tồn tại một số nguyên tố p
sao cho khi chuyển vào Z p [x] bậc của đa thức f (x) không đổi và f (x) bất

khả quy trên Z p , thì f (x) là bất khả quy trên Q. Chú ý rằng điều ngược lại
là không đúng. D. Hilbert đã chỉ ra một đa thức bậc 4 bất khả quy trên Q
nhưng khả quy trên mọi trường Z p . Quan hệ trên về tính bất khả quy trên
Q và trên Z p gợi ý cho chúng ta nghĩ đến việc tìm một thuật toán phân tích
bất khả quy của đa thức trên trường hữu hạn và sử dụng nó để tìm phân tích
bất khả quy của đa thức trên Q.
Mục đích của luận văn 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 gần đây về đa thức bất khả quy và sự phân tích đa thức thành
nhân tử bất khả quy. Trong luận văn này, trước hết chúng tôi xét tính bất khả
quy của đa thức trên trường Z p và thuật toán Berlekamp phân tích đa thức
thành nhân tử bất khả quy trên trường Z p . Sau đó, sử dụng các kết quả thu
được, chúng tôi trình bày một phương pháp phân tích đa thức thành nhân tử
trên trường Q các số hữu tỷ.
Nội dung nghiên cứu của luận văn là hoàn toàn chưa được tiếp cận ở bậc
phổ thông và đại học, nhưng gắn liền với toán sơ cấp, đặc biệt là bài toán
phân tích đa thức thành nhân tử rất được quan tâm ở bậc học phổ thông.
Luận văn gồm phần mở đầu, hai chương và tài liệu tham khảo. Trong
Chương 1, chúng tôi nhắc lại khái niệm đa thức bất khả quy và một số tiêu


2

chuẩn bất khả quy trên Q. Chương 2 là nội dung chính của luận văn. Mục
2.1 dành để nghiên cứu khái niệm trường phân rã của đa thức, từ đó xét cấu
trúc của trường hữu hạn. Mục tiếp theo mô tả huật toán Berlekamp phân
tích đa thức thành nhân tử trên trường hữu hạn. Mục cuối là ứng dụng kết
quả vào bài toán phân tích đa thức trên trường Q.
Thái Nguyên, ngày 25 tháng 5 năm 2016
Tác giả


Vũ Đức Cảnh


3

Chương 1
Đa thức bất khả quy
1.1

Khái niệm đa thức bất khả quy

Trước khi trình bày khái niệm đa thức bất khả quy, chúng ta nhắc lại
khái niệm phần tử bất khả quy trong một miền nguyên. Cho V là một miền
nguyên và a ∈ V . Ta nói a là ước của b nếu tồn tại c ∈ V sao cho b = ac.
Một ước a của b được gọi là ước thực sự nếu b không là ước của a. Phần
tử p ∈ V được gọi là phần từ bất khả quy nếu nó khác 0, không khả nghịch
và không có ước thực sự. Từ đây ta có khái niệm đa thức bất khả quy trong
vành đa thức V [x]. Trong suốt tiết này ta luôn giả thiết V là miền nguyên.
Định nghĩa 1.1.1. Cho f (x) ∈ V [x] là đa thức khác 0 và không khả nghịch.
Ta nói f (x) là bất khả quy trên V nếu nó không có ước thực sự. Ta nói f (x)
khả quy nếu f (x) có ước thực sự.
Bổ đề 1.1.2. Đa thức f (x) là bất khả quy nếu và chỉ nếu f (x + a) là bất khả
quy với mọi a ∈ V.
Chứng minh. Cho a ∈ V . Với mỗi h(x) ∈ V [x] ta đặt h1 (x) = h(x − a). Chú
ý rằng deg h1 (x) = deg h(x). Vì thế f (x + a) = k(x)g(x) là phân tích của
f (x + a) thành tích của hai đa thức có bậc thấp hơn khi và chỉ khi f (x) =
k1 (x)g1 (x) là phân tích của f (x) thành tích của hai đa thức có bậc thấp hơn.
Vì vậy f (x) bất khả quy khi và chỉ khi f (x + a) bất khả quy.
Từ nay đến hết mục này chúng ta làm việc với đa thức có các hệ số
trên một trường K. Trong trường hợp này, các đa thức hằng khác 0 đều khả

nghịch. Do đó ta có ngay kết quả sau:


4

Bổ đề 1.1.3. Đa thức f(x) với hệ số trên trường K là bất khả quy nếu và chỉ
nếu deg f (x) > 0 và f (x) không phân tích được thành tích của hai đa thức
có bậc bé hơn.
Sau đây là tính bất khả quy của các đa thức bậc thấp.
Bổ đề 1.1.4. Trên một trường K, các phát biểu sau là đúng.
(i) Đa thức bậc nhất luôn bất khả quy.
(ii) Đa thức bậc 2 và bậc 3 là bất khả quy nếu và chỉ nếu nó không có
nghiệm trong K.
Chứng minh. (i) Rõ ràng đa thức bậc nhất không thể là tích của hai đa thức
bậc thấp hơn, do đó nó bất khả quy.
(ii) Giả sử f (x) có nghiệm x = a ∈ K. Vì deg f (x) > 1 nên ta có f (x) =
(x − a)g(x), trong đó g(x) ∈ K[x] và deg g(x) = deg f (x) − 1 ≥ 1. Do đó
f (x) khả quy. Ngược lại, giả sử f (x) khả quy. Vì f (x) có bậc 2 hoặc 3 nên
f (x) phân tích được thành tích của hai đa thức có bậc thấp hơn, một trong
hai đa thức đó phải có bậc 1. Rõ ràng đa thức bậc 1 trên một trường có
nghiệm trong trường đó, vì thế f (x) có nghiệm trong K
Chú ý rằng phát biểu (ii) trong bổ đề trên là không đúng cho trường hợp
bậc của đa thức lớn hơn 3. Cụ thể, nếu f (x) bậc lớn hơn 3 và có nghiệm
trong K thì f (x) khả quy. Tuy nhiên, tồn tại những đa thức không có nghiệm
trong K nhưng vẫn khả quy. Chẳng hạn đa thức (x2 + 1)(x2 + 2) không có
nghiệm trong R nhưng nó khả quy trên R.
Từ nay về sau, nếu a là ước của b thì ta kí hiệu là a | b.
Mệnh đề 1.1.5. Cho p(x) ∈ K[x] là đa thức có bậc dương. Khi đó p(x) bất
khả quy nếu và chỉ nếu p(x) | a(x)b(x) kéo theo p(x) | a(x) hoặc p(x) | b(x)
với mọi a(x), b(x) ∈ K[x]. Đặc biệt, nếu đa thức bất khả quy p(x) là ước của

một tích hữu hạn thì đa thức p(x) phải là ước của ít nhất một trong các đa
thức đó.
Chứng minh. Cho p(x) bất khả quy. Giả sử p(x) | a(x)b(x) và a(x), b(x)
đều không là bội của p(x). Do p(x) bất khả quy nên gcd(p(x), a(x)) =
1 và gcd(p(x), b(x)) = 1. Vì thế, tồn tại s(x), r(x), e(x), f (x) sao cho 1 =
s(x)p(x) + r(x)a(x) và 1 = e(x)p(x) + f (x)b(x). Nhân vế với vế của hai


5

đẳng thức này ta có
1 = p(x)g(x) + r(x) f (x)a(x)b(x)
với g(x) là một đa thức nào đó. Vì p(x) là ước của a(x)b(x) nên đa thức bên
vế phải của đẳng thức trên là bội của p(x), trong khi đó đa thức bên vế trái
là 1 không chia hết cho p(x). Điều này là vô lí.
Ngược lại, do p(x) có bậc dương nên p(x) = 0 và không khả nghịch. Giả
sử p(x) = a(x)b(x) với a(x), b(x) ∈ K[x]. Khi đó p(x) | a(x)b(x). Theo giả
thiết, p(x) | a(x) hoặc p(x) | b(x). Vì thế p(x) không có ước thực sự, do đó
p(x) bất khả quy.
Định lý cơ bản của Số học nói rằng mỗi số tự nhiên lớn hơn 1 đều phân
tích được thành tích các thừa số nguyên tố và sự phân tích đó là duy nhất
nếu không kể đến thứ tự các thừa số. Kết quả sau đây là một sự tương tự đối
với đa thức.
Định lý 1.1.6. Mỗi đa thức dạng chuẩn bậc dương trong K[x] có thể phân
tích được thành tích các đa thức bất khả quy dạng chuẩn và sự phân tích
này là duy nhất nếu không kể đến thứ tự các nhân tử.
Chứng minh. Trước hết, ta chứng minh sự tồn tại phân tích bằng quy nạp
theo bậc của đa thức. Giả sử f (x) ∈ K[x] là đa thức dạng chuẩn bậc d > 0.
Nếu d = 1 thì f (x) là bất khả quy, và sự phân tích bất khả quy của f (x) là
f (x) = f (x). Cho d > 1 và giả sử kết quả đã đúng cho các bậc nhỏ hơn d.

Nếu f (x) bất khả quy thì f (x) có sự phân tích bất khả quy là f (x) = f (x). Vì
thế ta giả thiết f (x) không bất khả quy. Khi đó f (x) = g(x)h(x) với degg(x),
deg h(x)Khi đó ta có f (x) = g∗ (x)(ah(x)). Đồng nhất hệ số cao nhất ở hai vế ta suy
ra ah(x) có dạng chuẩn. Do đó f (x) = g∗ (x)h∗ (x) với g∗ (x), h∗ (x) = ah(x)
là các đa thức dạng chuẩn có bậc nhỏ hơn d. Theo giả thiết quy nạp, g∗ (x)
và h∗ (x) phân tích được thành tích của hữu hạn các đa thức bất khả quy
dạng chuẩn. Vì thế, f (x) phân tích được thành tích của hữu hạn đa thức bất
khả quy dạng chuẩn.
Bây giờ ta chứng minh tính duy nhất của phân tích. Giả sử f (x) có hai


6

sự phân tích thành nhân tử bất khả quy dạng chuẩn
f (x) = p1 (x)p2 (x)...pn (x) = q1 (x)q2 (x)...qm (x).
Ta chứng minh bằng sự quy nạp theo n rằng n = m và sau khi đánh lại
thứ tự các nhân tử vế bên phải ta có pi (x) = qi (x) với mọi i = 1, ..., n. Do
p1 (x) | q1 (x)q2 (x)...qm (x) và p1 (x) bất khả quy nên theo mệnh đề trên ta có
p1 (x) | qi (x) với i nào đó. Không mất tính tổng quát ta giả thiết p1 (x) | q1 (x).
Biểu diễn q1 (x) = p1 (x)t1 (x). Vì q1 (x) bất khả quy nên t1 (x) = a ∈ K. Do
đó q1 (x) = ap1 (x). Do p1 (x) và q1 (x) có dạng chuẩn nên a = 1. Vì thế
p1 (x) = q1 (x). Cho n = 1. Nếu m > 1 thì giản ước cả hai vế cho p1 (x) ta
được 1 = q2 (x)...qm (x), điều này là vô lí. Vậy, kết quả đúng cho n = 1. Cho
n > 1. Vì p1 (x) = q1 (x) nên
f (x) = p2 (x)p3 (x)...pn (x) = q2 (x)q2 (x)...qm (x).
Theo giả thiết quy nạp ta có n − 1 = m − 1 và bằng việc đánh số lại thứ tự
các nhân tử bất khả quy ở vế phải ta có pi (x) = qi (x) với i = 2, ..., n., suy ra
pi (x) = qi (x) với mọi i = 2, ..., n.
Từ định lý trên, ta có kết quả sau.

Hệ quả 1.1.7. Cho f (x) ∈ K[x] là đa thức với hệ số cao nhất là an . Khi đó
tồn tại phân tích f (x) = an f1 (x)... fk (x) với f1 (x), ..., fk (x) là các nhân tử
bất khả quy dạng chuẩn, và sự phân tích này là duy nhất nếu không kể đến
thứ tự các nhân tử.
Euclid đã chứng minh rằng có vô hạn số nguyên tố. Kết quả sau đây là
một sự tương tự cho đa thức bất khả quy.
Hệ quả 1.1.8. Trên một trường K bất kỳ, có vô hạn đa thức bất khả quy
dạng chuẩn.
Chứng minh. Chú ý rằng x + 1 ∈ K[x] là đa thức bất khả quy dạng chuẩn.
Giả sử f1 (x), ..., fn (x) ∈ K[x] là tất cả các đa thức bất khả quy dạng chuẩn.
Đặt f (x) = f1 (x)... fn (x) + 1. Theo định lý trên, tồn tại p(x) là ước bất khả
quy dạng chuẩn của f (x). Do đó p(x) = fi (x) với i nào đó. Suy ra p(x) |
f1 (x)... fn (x). Vì p(x) | f( x) nên p(x) | 1, điều này vô lí, tức là phải có vô
hạn các đa thức bất khả quy dạng chuẩn.


7

1.2

Một số tiêu chuẩn bất khả quy trên trường Q

Trong lí thuyết số, bài toán tìm thuật toán tất định với độ phức tạp đa thức
để kiểm tra tính nguyên tố của các số tự nhiên là một trong những bài toán
quan trọng nhất. Bắt đầu bằng “Sàng Eratosthenes" để tìm các số nguyên
tố nhỏ hơn 100 do nhà toán học cổ Hy Lạp Eratosthenes phát minh ra, trải
qua hàng nghìn năm sau, mãi đến năm 2002 người ta mới tìm được thuật
toán như mong muốn, gọi là Thuật toán kiểm tra nguyên tố AKS. Trong lí
thuyết đa thức, một bài toán quan trọng tương tự là tìm các đa thức bất khả
quy trên các trường Q, R, C. Nhờ Định lí cơ bản của Đại số “mỗi đa thức

bậc dương với hệ số phức đều có ít nhất một nghiệm phức", chúng ta dễ
dàng thấy rằng đa thức bất khả quy trên C là và chỉ là các đa thức bậc nhất.
Từ Định lí cơ bản của Đại số, ta cũng suy ra rằng các đa thức bất khả quy
trên R là và chỉ là các đa thức bậc nhất hoặc bậc hai với biệt thức âm.
Tuy nhiên, bài toán xét tính khả quy của các đa thức trên trường Q các
số hữu tỷ cho đến nay vẫn là bài toán chưa được giải quyết trọn vẹn. Mục
tiêu của mục này là trình bày một số tiêu chuẩn và phương pháp xét tính
bất khả quy của đa thức trên Q như phương pháp sử dụng nghiệm hữu tỷ,
phương pháp sử dụng Bổ đề Gauss, tiêu chuẩn Eisenstein.
Giả sử f (x) ∈ Q[x]. Chú ý rằng f (x) là bất khả quy trên Q khi và chỉ
khi a f (x) là bất khả quy, trong đó a là mẫu số chung của các hệ số của
f (x). Rõ ràng a f (x) ∈ Z[x]. Do đó ta chỉ cần xét tính bất khả quy trên Q
cho các đa thức với hệ số nguyên. Từ nay đến hết mục này, luôn giả thiết
f (x) = an xn + ... + a1 x + a0 ∈ Z[x], trong đó an = 0 và n > 0.
Chú ý rằng một đa thức bậc bậc 1 thì luôn có nghiệm trong Q và cũng
luôn bất khả quy trên Q. Đối với đa thức f (x) bậc lớn hơn 1, khi đó nếu
f (x) có nghiệm hữu tỷ thì nó khả quy trên Q. Vì thế chúng ta có thể sử
dụng tiêu chuẩn có nghiệm hữu tỷ sau đây để xét tính bất khả quy của đa
thức trên Q.
Bổ đề 1.2.1. Cho f (x) = an xn + ... + a1 x + a0 ∈ Z[x]. Nếu phân số tối giản
r/s là nghiệm của f(x) thì r là ước của a0 và s là ước của an . Đặc biệt, nếu
an = ±1 thì mọi nghiệm hữu tỷ của f(x) đều là nghiệm nguyên.
r
Chứng minh. Giả sử là nghiệm của f (x), trong đó r, s ∈ Z và (r, s) = 1.
s


8

Khi đó ta có

r
rn
rn−1
r
0 = f ( ) = an n + an−1 n−1 + . . . + a1 + a0 .
s
s
s
s
Suy ra 0 = an rn + an−1 rn−1 s + . . . + a1 rsn−1 + a0 sn . Vì thế ta có
an rn = −(an−1 rn−1 s + . . . + a1 rsn−1 + a0 sn ).
Vế phải của đẳng thức là bội của s. Vì thế an rn là bội của s. Do (r, s) = 1
nên s là ước của an . Tương tự ta có
a0 sn = −(an rn + an−1 rn−1 s + . . . + a1 rsn−1 ).
Vế phải của đẳng thức này là bội của r. Vì thế a0 sn là bội của r. Do (r, s) = 1
nên r là ước của a0 .
Bổ đề 1.2.2. Cho f (x) = an xn + ... + a1 x + a0 ∈ Z[x] và m ∈ Z. Nếu phân
số tối giản r/s là nghiệm của f (x) thì r − ms là ước của f (m). Đặc biệt,
(r + s) là ước của f (−1) và (r − s) là ước của f (1).
Chứng minh. Bằng cách khai triển các nhị thức ((x − m) + m)k và nhóm các
hạng tử tương ứng, ta có thể phân tích f (x) theo các lũy thừa của (x − m)
theo cách sau
f (x) = f ((x − m) + m)
=an ((x − m) + m)n + . . . + a1 ((x − m) + m) + a0
=an (x − m)n + bn−1 (x − m)n−1 + . . . + b1 (x − m) + b0 ,
trong đó b0 , b1 , . . . , bn−1 ∈ Z. Suy ra f (m) = b0 và ta có
r
0 =f( )
s
r

r
r
=an ( − m)n + bn−1 ( − m)n−1 + . . . + b1 ( − m) + f (m).
s
s
s
Từ đó ta có
0 = an (r − ms)n + bn−1 (r − ms)n−1 s + . . . + b1 (r − ms)n−1 sn−1 + f (m)sn .


9

Vì thế ta có
f (m)sn = −an (r − ms)n − bn−1 (r − ms)n−1 s − . . . − b1 (r − ms)n−1 sn−1 .
Vế phải của đẳng thức trên là bội của r −ms. Do đó f (m)sn là bội của r −ms.
Đặt d = gcd(s, r − ms). Vì d là ước chung của s và r − ms nên d là ước của
r
s và r. Vì là phân số tối giản nên d = 1. Suy ra gcd(sn , r − ms) = 1. Vì thế
s
r − ms là ước của f (m). Đặc biệt, khi m = 1 thì r − s là ước của f (1) và khi
m = −1 thì r + s là ước của f (−1).
Sau đây là một số ví dụ minh họa.
Ví dụ 1.2.3. (i) Đa thức f (x) = 4x3 − 16x2 + 11x + 10 là khả quy trên Q.
(ii) Đa thức g(x) = 4x3 + 8x2 − 6x + 5 = 0 là bất khả quy trên Q.
Chứng minh. Ta dùng Bổ đề 1.2.1 và Bổ đề 1.2.2 để chứng minh Ví dụ 1.2.3
như sau.
(i) Giả sử phân số tối giản r/s là nghiệm của f (x). Khi đó ta có r là ước của
10 và s là ước của 4. Suy ra
r ∈ {±1, ±2, ±5, ±10} và s ∈ {±1, ±2, ±4}. Vì f (1) = 9 và f (−1) = −21
1 1 5 5

nên ta có r/s ∈ ± , ± , ± , ± , ±2, ±10 .
2 4 2 4
1 5
Thử lại ta thấy − , 2, là nghiệm của f (x). Vậy f (x) khả quy trên Q.
2 2
(ii) Ta có 2g(x) = 8x3 + 16x2 − 12x + 10 = 0. Khi đó g(x) = 0 nếu và chỉ
nếu 8x3 + 16x2 − 12x + 10 = 0. Đặt y = 2x, phương trình thứ hai trở thành
h(y) = y3 + 4y2 − 6y + 10 = 0, có an = 1, nên h(y) nếu có nghiệm hữu tỷ
thì đó là nghiệm nguyên(theo (1)), giả sử s là nghiệm của h(y) thì theo (1),
s | 10, hay s ∈ {±1, ±2, ±5, ±10}. Thử lại ta thấy không có giá trị nào là
nghiệm của h(y), tức là g(x) không có nghiệm hữu tỷ. Do đó g(x) bất khả
quy trên Q.
Việc xét tính bất khả quy bằng phương pháp tìm nghiệm hữu tỷ gặp rất
nhiều hạn chế. Nếu đa thức có bậc 2 hoặc 3 thì đa thức đó là bất khả quy
trên Q khi và chỉ khi nó có nghiệm hữu tỷ. Tuy nhiên, nếu bậc của đa thức
lớn hơn hay bằng 4 thì phát biểu trên không còn đúng nữa. Chẳng hạn,
(x2 + 2)(x2 + 2) không có nghiệm hữu tỷ, nhưng lại khả quy trên Q.
Một trong những phương pháp hữu hiệu để xét tính bất khả quy của đa
thức trên Q là sử dụng Bổ đề Gauss. Phương pháp này đặc biệt hiệu quả


10

cho các đa thức không có nghiệm hữu tỷ. Trước hết chúng ta phát biểu và
chứng minh Bổ đề Gauss.
Định lý 1.2.4. (Bổ đề Gauss). Cho p(x) ∈ Z[x]. Giả sử p(x) = g(x) f (x)
với g(x), f (x) ∈ Q[x]. Khi đó tồn tại g∗ (x), f∗ (x) ∈ Z[x] sao cho deg g(x) =
deg g∗ (x), deg f (x) = deg f∗ (x) và p(x) = g∗ (x) f∗ (x). Đặc biệt, nếu p(x) là
khả quy trên Q thì nó phân tích được thành hai đa thức với hệ số nguyên có
bậc thấp hơn.

Chứng minh. Viết f (x) = a f1 (x) và g(x) = bg1 (x) trong đó a, b ∈ Q và
f1 (x), g1 (x) là hai đa thức nguyên bản. Rõ ràng p(x) = ab f1 (x)g1 (x) ∈ Z[x].
Ta chứng minh ab ∈ Z. Thật vậy, giả sử ab ∈
/ Z. Khi đó, ab = r/s với r/s
là phân số tối giản và s > 1. Viết f1 (x), g1 (x) = an xn + ... + a1 x + a0 . Vì
f1 (x), g1 (x) là nguyên bản nên gcd(an , an−1 , ..., a0 ) = 1. Vì p(x) ∈ Z[x] nên
ta có
ra1 ra0
ran
, ...,
,
∈ Z.
s
s s
Suy ra s là ước chung của an , . . . , a1 , a0 , điều này là vô lí. Vậy ab ∈ Z. Đặt
f∗ (x) = ab f1 (x) và g∗ (x) = g1 (x). Khi đó p(x) = f∗ (x)g∗ (x) với f∗ (x), g∗ (x) ∈
Z[x] và deg f (x) = deg f∗ (x) và deg g(x) = deg g ∗ (x).
Dưới đây là một số ví dụ xét tính bất khả quy trên Q bằng việc sử dụng
Bổ đề Gauss.
Ví dụ 1.2.5. Đa thức f (x) = x4 + 7x3 + x2 + 7 bất khả quy trên Q.
Chứng minh. Sử dụng Bổ đề 1.2.1 ta suy ra f (x) không có nghiệm hữu
tỷ. Vì thế f (x) không là tích của một đa thức bậc nhất và một đa thức bậc
ba. Giả sử f (x) khả quy trên Q. Theo Bổ đề Gauss, f (x) có sự phân tích
f (x) = g(x)h(x) trong đó g(x), h(x) ∈ Z[x] có bậc hai và có hệ số cao nhất
bằng 1. Viết g(x) = x2 + ax + b và h(x) = x2 + cx + d với a, b, c, d ∈ Z. Đồng
nhất hệ số ở hai vế của đẳng thức f (x) = g(x)h(x) ta được
bd = 7, bc + ad = 0, ac + d + b = 1, c + a = 7.
Vì bd = 7 và vai trò b, d như nhau nên không mất tính tổng quát ta có thể
giả thiết b = 1, d = 7 hoặc b = −1, d = −7. Nếu b = 1, d = 7 thì c + 7a =
7

0, ac = −7, a + c = 7. Suy ra a = − ∈
/ Z, vô lí. Nếu b = −1, d = −7 thì
6


11

7
−c − 7a = 0, ac = 9, a + c = 7. Suy ra a = − ∈
/ Z, vô lí. Như vậy, f (x) bất
6
khả quy trên Q.
Ví dụ 1.2.6. Đa thức f (x) = x5 + x3 + x2 + 3 là bất khả quy trên Q.
Chứng minh. Sử dụng Bổ đề 1.2.1 ta suy ra f (x) không có nghiệm hữu tỷ.
Vì thế f (x) không là tích của một đa thức bậc nhất và một đa thức bậc bốn.
Giả sử f (x) khả quy trên Q. Theo Bổ đề Gauss, tồ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à deg g(x) =
2, deg h(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 = an xn +...+a1 x+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) = bm xm + . . . + b1 x + b0 ∈ Z[x] và
h(x) = ck xk +...+c1 x+c0 ∈ Z[x] với deg g(x) = m, deg h(x) = k và m, k < n.
Do p là ước của a0 = b0 c0 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 = bm ck 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 = b0 cr + (b1 cr−1 + b2 cr−2 + ... + br c0 ). Vì
r ≤ k < n nên p | ar . Theo cách chọn r ta có p | b1 cr−1 + b2 cr−2 + ... + br c0 .
Suy ra p | b0 cr , đ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]}.
f (α)
| f , g ∈ K[x], g(α) = 0 .
(ii) K(α) =
g(α)
(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 = 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 .
/ I tức g(x) không chia hết cho f (x). Do f (x) bất khả
Vì g(x) = 0 nên g(x) ∈
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 → 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 + a1 x + ... + an xn thì ta có
0 = 0 = f (x) = a0 + a1 x + ... + an xn = a0 + a1 x + ... + an xn = 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ủa K 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 = 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 deg h(x) = n1 < n
và deg h(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 Z p 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 = m1 với mọi n = 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à Z p ∼
= Imϕ ⊆ K. Do p nguyên tố nên Z p là
trường. Vì thế K là một không gian véc tơ trên trường Z p . 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ử dimZ p K = 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
Z p . Hơn nữa, K ∼
= T.
Chứng minh. (i) Đặt q = pd . Do p nguyên tố nên Z p là trường. Theo định
lí trên, tồn tại một trường F chứa Z p và chứa các nghiệm của đa thức

g(x) = xq − x ∈ Z p [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 q−1
q
a b + ... +
abq−1 + bq ,
1
q−1

q
q!
là số tổ hợp chập k của q phần tử. Vì q = pd và
=
k!(q − k)!
k

q
p nguyên tố nên bằng quy nạp ta kiểm tra được
là bội của p với mọi
k
q q−k k
k = 1, ..., q − 1. Do đó ta có
a b = 0 với mọi k = 1, ..., q − 1. Suy ra
q

trong đó

(a + b)q = aq + bq = a + b,
tức là g(a + b) = 0. Vì thế a + b ∈ E. Cho 0 = a ∈ E. Khi đó aq = a. Chú ý
rằng q ≥ 2. Do a = 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 Z p . Tương
tự lập luận như trong chứng minh (i) ta suy ra đa thức g(x) = xq − x ∈ Z p [x]
không có nghiệm bội trong bất cứ mở rộng nào của Z p . Cho a ∈ K. Nếu
a = 0 thì rõ ràng a là nghiệm của g(x). Giả sử a = 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 = 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 Z p . Tương tự, T
cũng là trường phân rã của g(x) trên Z p . 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) = 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 deg r(x) < deg g(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 d1 d2 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
Xi = X1 ⊕ X2 ⊕ . . . ⊕ Xr = {(x1 , x2 , . . . , xr ) | xi ∈ Xi }
i=1,...,r

làm thành một vành với phép cộng
(x1 , x2 , . . . , xr ) + (x1 , x2 , . . . , xr ) = (x1 + x1 , x2 + x2 , . . . , xr + xr ).
và phép nhân
(x1 , x2 , . . . , xr )(x1 , x2 , . . . , xr ) = (x1 x1 , x2 x2 , . . . , xr xr ).
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 = 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 ∼
=

K[x]/Ii .

i=1,...,r


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 = f1 k + f2t với k,t ∈ X. Suy ra g + I1 =
f1 kg + f2tg + I1 và h + I2 = f1 kh + f2th + I2 = f1 kh + I2 . Do đó
(g + I1 , h + I2 ) = ( f2tg + I1 , f1 kh + I2 )
= ( f2tg + f1 kh + I1 , f1 kh + f2tg + I2 )
= ϕ( f2tg + I1 , f1 kh + 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