Tài liệu Về đa thức bất khả quy trên trường hữu hạn

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- VŨ VĂN HẢO VỀ ĐA THỨC BẤT KHẢ QUY TRÊN TRƯỜNG HỮU HẠN LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- VŨ VĂN HẢO VỀ ĐA THỨC BẤT KHẢ QUY TRÊN TRƯỜNG HỮU HẠN Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Ngô Thị Ngoan THÁI NGUYÊN - 2019 i Mục lục Lời cảm ơn 1 Mở đầu 2 1 Trường hữu hạn 1.1 Một số khái niệm . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Đa thức tương hỗ . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Công thức nghịch đảo Möbius . . . . . . . . . . . . . . . . . 2 Đa thức bất khả quy trên trường 2.1 Đa thức xp − x + a . . . . . . . 2.2 Dãy các đa thức bất khả quy . . 2.2.1 Q−phép biến đổi và vết 2.2.2 Dãy đa thức bất khả quy số 2 . . . . . . . . . . . . 2.2.3 Dãy đa thức bất khả quy số lẻ . . . . . . . . . . . hữu hạn . . . . . . . . . . . . . . . . . . . . . . . . . . . trên trường hữu . . . . . . . . . trên trường hữu . . . . . . . . . . . . . . . . . . . . . hạn có . . . . hạn có . . . . 4 4 13 14 18 . . . 18 . . . 21 . . . 22 đặc . . . 25 đặc . . . 30 Kết luận 36 Tài liệu tham khảo 37 1 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 TS. Ngô Thị Ngoan. 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ả cũng đã học tập được rất nhiều kiến thức chuyên ngành bổ ích cho công tác và nghiên cứu của bản thân. Tác giả xin bày tỏ lòng cảm ơn sâu sắc tới các thầy giáo, cô giáo đã tham gia giảng dạy lớp Cao học Toán K11D (khóa 2017–2019); Nhà trường và các phòng chức năng của Trường; Khoa Toán – Tin, trường Đại học Khoa học – Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Tác giả cũng xin gửi lời cảm ơn sâu sắc tới Trường Trung học phổ thông Quang Hà đã giúp đỡ, tạo mọi điều kiện thuận lợi giúp tôi có thể hoàn thành luận văn 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 K11D (khóa 2017–2019) đã luôn động viên và giúp đỡ tác giả rất nhiều trong quá trình học tập, nghiên cứu. Cuối cùng, tôi xin gửi lời cảm ơn chân thành tới gia đình, bạn bè, lãnh đạo đơn vị công tác và đồng nghiệp đã động viên, giúp đỡ và tạo điều kiện tốt nhất cho tôi khi học tập và nghiên cứu. Thái Nguyên, tháng 5 năm 2019 Tác giả Vũ Văn Hảo 2 Mở đầu Đa thức bất khả quy là khái niệm đóng vai trò quan trọng và có nhiều áp dụng. Đây cũng là vấn đề kinh điển trong lý thuyết đa thức nói riêng và trong toán học nói chung. Các bài toán về đa thức bất khả quy và bài toán phân tích một đa thức thành nhân tử bất khả quy đã được đưa vào giảng dạy ngay từ THCS. Việc phân tích trên cho phép học sinh chuyển việc giải một phương trình đại số về các phương trình có bậc thấp hơn. Trong chương trình toán học cao cấp, khái niệm đa thức bất khả quy được đưa vào giảng dạy trong các năm đầu tiên của chương trình đào tạo Đại học. Lúc này, sinh viên được tiếp xúc với những tiêu chuẩn về tính bất khả quy của các đa thức trên Z[x], Q[x] như tiêu chuẩn Eisenstein, tiêu chuẩn Person, tiêu chuẩn Dumas. Đặc biệt có thể sử dụng một kỹ thuật quan trọng là xét tính bất khả quy của đa thức hệ số nguyên thông qua việc rút gọn theo modulo p nguyên tố. Trong khuôn khổ luận văn này, tôi trình bày những tìm hiểu về đa thức bất khả quy trên trường hữu hạn: Một số lớp đa thức bất khả quy; việc xây dựng được những đa thức bất khả quy mới từ hai đa thức bất khả quy đã cho; việc xây dựng được dãy vô hạn các đa thức bất khả quy với bậc tăng dần từ một đa thức bất khả quy ban đầu trên các trường hữu hạn. Nội dung luận văn bao gồm hai chương: Chương 1 của luận văn trình bày về trường hữu hạn. Nội dung chương 1 được tham khảo chủ yếu từ các tài liệu [1] và [6]. Chúng ta sẽ trình bày về mở rộng trường, trường phân rã của đa thức, cấu trúc của trường hữu hạn và công thức nghịch đảo Möbius [6] giúp ta xác định các đa thức dạng chuẩn (đa thức monic) bất khả quy trên trường hữu hạn Fq bất kỳ có bậc n. Chương 2 của luận văn trình bày về đa thức bất khả quy trên trường hữu hạn. Chúng ta sẽ trình bày một lớp đa thức bất khả quy trên trường Fq [x] 3 với q = pn ; xây dựng những đa thức bất khả quy từ hai đa thức bất khả quy đã cho; xây dựng được dãy vô hạn những đa thức bất khả quy trên trường hữu hạn có đặc số 2 bằng cách sử dụng Q− biến đổi; xây dựng dãy vô hạn những đa thức bất khả quy có bậc tăng dần trên trường hữu hạn có đặc số lẻ bằng cách sử dụng R− biến đổi từ một đa thức bât khả quy ban đầu. Thái Nguyên, ngày 25 tháng 5 năm 2019 Tác giả luận văn Vũ Văn Hảo 4 Chương 1 Trường hữu hạn 1.1 Một số khái niệm Ta nhắc lại, một trường F là một vành giao hoán khác không và không có ước của 0. Một trường có hữu hạn phần tử được gọi là một trường hữu hạn. Định nghĩa 1.1.1. Trường F được gọi là một trường nguyên tố nếu nó không có trường con nào ngoài bản thân nó. Nhận xét 1.1.2. (i) Cho F là trường nguyên tố. Khi đó chỉ có thể xảy ra một trong hai trường hợp: nếu F có đặc số 0 thì F ∼ = Q; nếu F có đặc số p thì F ∼ = Zp . Trường hợp F ∼ = Zp . Ta thường kí hiệu Fp thay cho F. (ii) Cho E là một trường tùy ý, khi đó nếu gọi F là giao của mọi trường con của E thì F cũng là một trường con của E, rõ ràng F là trường con nhỏ nhất của E , do đó F là trường nguyên tố. Trong trường hợp này, ta nói F là trường con nguyên tố của E . Như vậy, mọi trường đều chứa một trường con nguyên tố. Bổ đề 1.1.3 (Cấu trúc trường hữu hạn). (i) Cho F là trường hữu hạn có q phần tử. Khi đó tồn tại số nguyên tố p sao cho q = pn với số tự nhiên n nào đó. (ii) Với mỗi số nguyên tố p và số tự nhiên n 6= 0, tồn tại duy nhất một trường hữu hạn có pn phần tử (sai khác một đẳng cấu trường). 5 Chứng minh. (i) Gọi p là đặc số của trường F , khi đó p là số nguyên tố. Gọi Fp là trường con nguyên tố của F , khi đó Fp ∼ = Zp . Ta biết rằng F là Fp −không gian vectơ hữu hạn chiều. Giả sử dimFp (F ) = n < ∞, khi đó F có một cơ sở là {e1 , . . . , en } n P ai ei với a1 , . . . , an ∈ Fp . Từ đó và vì thế mỗi phần tử của F có dạng x = i=1 suy ra số phần tử của F bằng số các bộ phần tử (a1 , . . . , an ) ∈ Fp × . . . × Fp (n lần). Do đó q = pn . (ii) Sự tồn tại của trường có q = pn phần tử. Xét đa thức f (x) = xq − x ∈ Fp [x] với Fp ∼ = Zp là trường nguyên tố có đặc số nguyên tố p. Gọi E là trường phân rã của f (x) trên Fp . Đặt K = {α ∈ E | f (α) = 0} đó chính là tập hợp các nghiệm của f (x). Khi đó K là một trường con của E . Thật vậy, với mọi α, β ∈ K ta có (α − β)q = αq − β q = α − β, (αβ)q = αq β q = αβ Do đó α − β, αβ ∈ K . Nếu α ∈ K ∗ thì (α−1 )q = (aq )−1 = α−1 suy ra α−1 ∈ K. Ngoài ra, rõ ràng 1q = 1 nên 1 ∈ K. Cuối cùng, ta thấy rằng mọi n a ∈ Fp đều thỏa mãn ap = a do đó aq = ap = a chứng tỏ Fp ⊆ K. Như vậy K chính là trường phân rã của f (x) trên Fp , trường này có q = pn phần tử (lưu ý rằng f (x) không có nghiệm bội). Tính duy nhất của trường có q = pn phần tử. Giả sử Fq là trường có q = pn phần tử. Khi đó Fq có đặc số là p (giả sử p1 là đặc số của Fq thì theo (i) suy 0 0 ra q = pn1 ; do đó pn = pn1 vì thế p = p1 ). Vì F∗q = Fq \ {0} là nhóm với phép nhân nên αq−1 = 1 với mọi α ∈ F∗q ; do đó αq = α với mọi α ∈ Fq . Chứng tỏ mọi phần tử của Fq đều là nghiệm của đa thức f (x) = xq − x ∈ Fp [x] với Fp là trường nguyên tố của Fq . Suy ra trường Fq chính là trường phân rã của f (x) trên Fp . Điều đó khẳng định tính duy nhất của Fq sai khác một đẳng cấu trường. Trong luận văn, chúng ta sẽ quan tâm nghiên cứu về đa thức bất khả quy trên trường hữu hạn Fq . Đa thức bất khả quy trên trường Fq chính là phần tử bất khả quy của vành đa thức Fq [x]. 6 Định nghĩa 1.1.4. Một đa thức với hệ số trên một trường được gọi là bất khả quy nếu nó có bậc dương và không phân tích được thành tích của hai đa thức có bậc thấp hơn. Định lý 1.1.5. Cho F là trường hữu hạn có đặc số p. Khi đó ta có n n n n n n (a + b)p = ap + bp , (a − b)p = ap − bp với mọi a, b ∈ F, n ∈ N \ {0}. Chứng minh. Ta có khai triển (a + b)p = p X k=0 p k ! p k ak bp−k với ! = Cpk , ! p với mỗi 0 < k < p vì vậy (a + b)p = ap + bp . Bằng quy nạp k n n−1 n n n theo n, biến đổi (a + b)p = ((a + b)p )p suy ra (a + b)p = ap + bp . Để n n n chứng minh (a − b)p = ap − bp , ta biến đổi mà p | n n n n (a − b)p = (a + (−b))p = ap + (−b)p . n n Nếu p lẻ thì ta có (−1)p = −1, nếu p chẵn thì p = 2 và (−1)p = 1 = −1. Cho p là số nguyên tố, và 1 ≤ n ∈ Z. Đặt q = pn . Khi đó ta có định lý sau. Định lý 1.1.6. Nhóm nhân F∗ q của trường hữu hạn F là xyclic cấp q − 1. Để chứng minh Định lý 1.1.6 ta cần các bổ đề sau đây. P Bổ đề 1.1.7. Nếu 1 ≤ m ∈ Z, thì m = d|m ϕ(d), trong đó ϕ(d) là kí hiệu cho hàm Euler. Chứng minh. Nếu d chia hết m, thì ta kí hiệu Cd là nhóm con duy nhất của Zm có cấp d, và kí hiệu Φd là tập tất cả các phần tử sinh của Cd . Vì mỗi phần tử bất kì của Zm đều sinh ra một trong các nhóm Cd nào đó, nên nhóm Zm là hợp rời của các tập Φd ; từ đó ta có X X m = |Zm | = |Φd | = ϕ(d). d|m d|m 7 Bổ đề 1.1.8. Cho H là một nhóm hữu hạn cấp n. Giả sử rằng, với mỗi ước d của n, tập các phần tử x ∈ H sao cho xd = 1 có nhiều nhất là d phần tử. Khi đó H là nhóm xyclic. Chứng minh. Cho d là một ước của m. Nếu tồn tại x ∈ H có cấp d, thì nhóm con (x) = {1, x, . . . , xd−1 } là nhóm xyclic cấp d; mặt khác theo giả thiết, có không quá d phần tử y ∈ H thỏa mãn y d = 1. Vì thế mọi y ∈ H sao cho y d = 1 đều thuộc vào (x). Đặc biệt, mọi phần tử của H có cấp d đều sinh ra (x) và có tất cả ϕ(d) phần tử cấp d. Vì thế số phần tử của H có cấp d hoặc là 0 hoặc ϕ(d). Lưu ý rằng với trường hợp nhóm H hữu hạn bất kì có cấp n, ta cũng luôn có [ H= Φ(d0 ) d0 |m,∃x0 ∈H có cấp d0 trong đó Φ(d0 ) là kí hiệu cho tập tất cả các phần tử của H có cấp d0 . Do đó X X m = |H| = |Φ(d0 )| = ϕ(d0 ). d0 |m,∃x0 ∈H có cấp d0 d0 |m,∃x0 ∈H có cấp d0 Nếu tồn tại d|m mà không có phần tử nào của H có cấp d thì công thức trên cho thấy X X 0 ϕ(d ) < ϕ(d0 ) m≤ d0 |n, d0 6=d d0 |n P trong khi đó d0 |m ϕ(d0 ) = m theo Bổ đề 1.1.7. Từ đó suy ra mâu thuẫn. Vậy mọi ước d của n đều có phần tử của H có cấp d. Đặc biệt, có một phần tử x ∈ H có cấp m, và do đó H trùng với nhóm xyclic (x). Chứng minh Định lý 1.1.6. Định lý này được suy ra từ Bổ đề 1.1.8 áp dụng cho H = F∗q và m = q − 1. Thật vậy với mọi d|(q − 1), ta có phương trình xd − 1 = 0 có bậc d và có hệ số trên một trường Fp , nên nó có nhiều nhất là d nghiệm trong Fq . Chú ý 1.1.9. Từ chứng minh trên cho thấy một kết quả tổng quát hơn đó là mọi nhóm con hữu hạn của nhóm nhân của một trường đều là xyclic. Định lý 1.1.10. Cho Fq là trường hữu hạn và đa thức f ∈ Fq [x] bất khả quy trên Fq , deg f = n. Khi đó trường phân rã của f trên Fq là Fqn . Hơn 8 nữa, nếu α là một nghiệm của f thì các nghiệm còn lại của f được cho bởi n−1 αq , . . . , αq . Chứng minh. Với n = 1 khẳng định hiển nhiên đúng. Ta chứng minh khẳng định đúng với n > 1. Chọn α là một nghiệm trong trường phân rã của f, α 6= 0 vì f bất khả quy. [Fq (α) : Fq ] = n vì vậy theo Bổ đề 1.1.3 n n P P k n F . Giả sử f (x) = a x , do đó f (α) = ak αk = 0. Theo Định Fq (α) ∼ = q k k=0 k=0 lý 1.1.5, với 0 < i < n ta có: !qi n n n X X X i i q i kq i k ak (αq )k = f (αq ), ak α = ak α = 0= k=0 k=0 k=0 vì aqk = ak do ak ∈ Fq . Chúng ta cần chỉ ra rằng αq = αq , 0 ≤ i, j < n i kéo theo i = j (*). Tức là chúng ta thu được {αq , i = 0, . . . , n − 1} là n nghiệm khác nhau của f , lúc đó ta có thể kết luận trường phân rã của f là Fq (α) ∼ = Fqn . i j Muốn chứng minh (*), trước tiên, ta khẳng định tính chất một đa thức n bất khả quy f (x) bậc m trên trường Fq là ước của xq − x khi và chỉ khi m | n. Thật vậy, nếu m | n thì Fqm là trường con của trường Fqn . Vì Fqn n chứa các nghiệm của xq − x nên mỗi nghiệm của f (x) đều là một nghiệm n của xq − x. Mặt khác mọi nghiệm của f (x) đều là nghiệm đơn nên ta suy n ra f (x) chia hết xq − x. n Ngược lại, nếu f (x) | xq − x và α là một nghiệm của f (x) trong Fqm , vì n f (x) bất khả quy bậc m nên ta có Fqm = Fq (α). Mặt khác vì f (x) | xq − x n nên α cũng là nghiệm của xq − x suy ra α ∈ Fqn . Vậy ta có Fq < Fq m < Fq n và m | n theo tháp mở rộng trường hữu hạn. i j Bây giờ, ta giả sử phản chứng αq = αq , 0 ≤ i < j < n. Khi đó, vì α 6= 0 ta có j i j−i j−i i i αq = αq ⇔ αq (q −1) = 1 ⇔ (αq −1 )q = 1. j−i n Lũy thừa cả hai vế q n−i lần và nhân α vào hai vế ta nhận được (αq −1 )q = j−i 1 ⇔ αq = α ⇒ α là nghiệm của xj−i − x ⇒ n | j − i mâu thuẫn với 0 < j − i < n. 9 Chú ý 1.1.11. Trong chứng minh của định lý trên ta nhận thấy rằng một đa thức bất khả quy có bậc m trên một trường hữu hạn phải có m nghiệm khác nhau. Do đó ta có thể khẳng định có các dạng đa thức không là bất khả quy: Cho Fq là trường hữu hạn có đặc số p và xét đa thức xp + a với a ∈ Fq . Chọn α là nghiệm của xp + a = 0 với α ∈ Fqp . Khi đó (x − α)p = xp − αp = xp + a và ta thấy chỉ có duy nhất nghiệm của xp + a = 0 là α và vì p > 1 đa thức xp + a khả quy trên Fq vì nếu nó bất khả quy thì nó phải có p nghiệm khác nhau. Định nghĩa 1.1.12. Cho F là một trường và K ⊆ F . Tự đẳng cấu σ của F được gọi là một tự đẳng cấu của F trên K nếu σ(a) = a với mọi a ∈ K . Định lý 1.1.13. Cho Fq và Fqm , m > 1 là các trường hữu hạn. Khi đó các i tự đẳng cấu của Fqm trên Fq chính là σi , i = 1, . . . , m trong đó σi (α) = αq với mọi α ∈ Fqm . Chứng minh. Dễ dàng nhận thấy σi là các tự đẳng cấu của Fqm trên Fq . Giả sử ϕ là một tự đẳng cấu của Fqm trên Fq . Gọi θ là một phần tử sinh của nhóm nhân Fqm . Nếu chúng ta có thể xác định ảnh của θ, chúng ta hoàn toàn có thể xác định được tự đẳng cấu (vì ta có thể xét ϕ là ánh xạ tuyến tính của Fqm được coi như một không gian vectơ trên Fq ). Bây giờ, gọi f là đa thức cực tiểu của θ trên Fq , deg f = m. Vì ϕ tuyến tính nên ta có 0 = ϕ(f (θ)) = f (ϕ(θ)). Suy ra ϕ(θ) là một nghiệm của f (x). Theo Định lý k 1.1.10, ta có ϕ(θ) = θp với k ∈ {1, . . . , m}. Chú ý 1.1.14. Cho K là một trường và F là một mở rộng hữu hạn của K . Khi đó mở rộng F/K được gọi là chuẩn tắc nếu [F : K] = |Aut(F/K)|, trong đó Aut(K/F) là nhóm các tự đẳng cấu của F trên K . Những mở rộng này có vai trò quan trọng trong lý thuyết Galois. Theo định lý trên, ta thấy rằng một mở rộng hữu hạn của một trường hữu hạn luôn là mở rộng chuẩn tắc. Định nghĩa 1.1.15. Cho F = Fqm và K = Fq là các trường hữu hạn. Một n−1 cơ sở chính tắc của F trên K là một cơ sở có dạng {α, αq , . . . , αq } với α ∈ F. 10 Chú ý 1.1.16. Theo Định lý 1.1.13, tự đẳng cấu của F trên K là σi (α) = i αq , 0 ≤ i < m, một cơ sở chính tắc của F trên K là một cơ sở của F trên K có dạng {α, σ1 (α), . . . , σm−1 (α)} với α ∈ F . Hai định lý được phát biểu dưới đây dùng để chứng minh mọi trường hữu hạn đều có một cơ sở chính tắc trên mọi trường con. Định lý 1.1.17. Cho F là một trường hữu hạn và V là một F − không gian hữu hạn chiều với dim V = n và T : V → V là ánh xạ tuyến tính. V là T −cyclic, nghĩa là có một cơ sở của V có dạng {ν, T (ν), . . . , T n−1 (ν)} với ν ∈ V khi và chỉ khi đa thức đặc trưng χT của T trùng với đa thức cực tiểu µT của T . Chứng minh. Áp dụng Mệnh đề 13, trang 474, chương 12 trong tài liệu [3], ta có đẳng cấu V ∼ = F [x]/(a1 (x)) ⊕ F [x]/(a2 (x)) ⊕ · · · ⊕ F [x]/(am (x)) như các F [x]−modules, trong đó a1 (x), a2 (x), . . . , am (x) là các đa thức có bậc ≥ 1 thỏa mãn a1 (x) | a2 (x) | . . . | am (x). Đặc biệt, ta có am (x)V = am (T )V = 0. Từ đây suy ra đa thức cực tiểu µT của T là ước của am (x) suy ra µT = am (x). Ta có n = dimF V = deg a1 +deg a2 +· · ·+deg am ≥ deg am = deg µT = deg χT = n Vậy ta phải có dấu “=”, tức là m = 1 và V ∼ = F [x]/(a1 (x)), V là cyclic như F [x]−module. Vậy V có một cơ sở là {ν, T (ν), . . . , T n−1 (ν)} với ν ∈ V \ {0}. Định lý 1.1.18. Cho G là một nhóm. Đặt ϕ1 , . . . , ϕm là các tự đồng cấu khác nhau từ G đến F∗q và đặt a1 , . . . , am ∈ Fq không đồng thời bằng 0. Khi đó ϕ1 , . . . , ϕm là độc lập tuyến tính nghĩa là tồn tại g ∈ G sao cho a1 ϕ1 (g) + · · · + am ϕm (g) 6= 0. Chứng minh. Ta chứng minh bằng quy nạp theo m. Nếu m = 1 thì ta có a1 ϕ1 (g) = 0 với mọi g ∈ G. Từ đó suy ra a1 = a1 ϕ1 (1) = 0, nên định lý đúng với m = 1. Giả sử định lý đúng với m − 1 và giả sử có a1 , . . . , am ∈ Fq 11 sao cho m P ai ϕi (g) = 0 với mọi g ∈ G. Ta giả sử phản chứng rằng tồn tại i=1 ai 6= 0. Khi đó có hai khả năng xảy ra: thứ nhất nếu có aj nào đó bằng 0 (j 6= i), khi đó theo giả thiết quy nạp ta suy ra ai = 0, điều này mâu thuẫn. Thứ hai tất cả các aj đều khác 0, với giả thiết này ta chia hai vế cho am 6= 0 ta được đẳng thức m−1 X bi ϕi (g) + ϕm (g) = 0, ∀g ∈ G (bi 6= 0, ∀i). (1.1) i=1 Do ϕ1 6= ϕm nên ta có thể chọn được a ∈ Fq sao cho ϕ1 (a) 6= ϕm (a). Thay g = ag vào (1.1) ta được m−1 X bi ϕi (a)ϕi (g) + ϕm (a)ϕm (g) = 0, ∀g ∈ G; (bi 6= 0, ∀i). i=1 Từ đó suy ra m−1 X bi ϕi (a)ϕm (a)−1 ϕi (g) + ϕm (g) = 0, ∀g ∈ G. (1.2) i=1 Từ (1.1) và (1.2), bằng cách trừ vế cho vế ta được m−1 X bi (ϕi (a)ϕm (a)−1 − 1)ϕi (g) = 0 + ϕm (g), ∀g ∈ G, i=1 từ đây theo giả thiết quy nạp suy ra bi (ϕi (a)ϕm (a)−1 − 1) = 0 với mọi i = 1, . . . , m − 1. Nói riêng với i = 1 ta có b1 (ϕ1 (a)ϕm (a)−1 − 1) = 0. Vì theo cách chọn a, ta có ϕ1 (a) 6= ϕm (a) nên phải có b1 = 0, điều này mâu thuẫn. Định lý sau chỉ ra rằng mọi trường hữu hạn đều có một cơ sở chính tắc trên tất cả các trường con. Định lý 1.1.19. Cho F = Fqm và K = Fq là các trường hữu hạn. Khi đó tồn tại một cơ sở chính tắc của F trên K . i Chứng minh. Xét các tự đẳng cấu σi (α) = αq , 0 ≤ i < m của F trên K . Khi đó có m đồng cấu nhóm khác nhau từ F ∗ đến F ∗ . Hơn nữa, các σi là 12 các ánh xạ tuyến tính của F được xem như một không gian vectơ trên K . Để chứng minh F có một cơ sở chính tắc trên K ta chứng minh F là σ1 − cyclic. Chúng ta xét đa thức đặc trưng χ và đa thức cực tiểu µ của σ1 . Đa thức f (x) = xm −1 thoả mãn f (σ1 ) = 0 ∈ End(F). Chúng ta sẽ chứng minh không có đa thức g(x) có bậc nhỏ hơn m sao cho g(σ1 ) = 0 ∈ End(F). Giả sử g(x) 6= 0, deg g < m. Khi đó, giả sử g(σ1 ) có dạng a0 σ10 + a1 σ11 + · · · + am σ1m−1 = a0 σ0 + a1 σ1 + · · · + am−1 σm−1 trong đó a0 , . . . , am−1 ∈ F không đồng thời bằng 0 và áp dụng Định lý 1.1.18 suy ra ∃ a ∈ F sao cho g(σ1 )(a) 6= 0 do đó g(σ1 ) 6= 0. Như vậy đa thức cực tiểu µ của σ1 là f (x). Măt khác, χ có bậc m; µ | χ cả µ và χ là đa thức dạng chuẩn suy ra: χ = µ = f . Theo Định lý 1.1.17 chúng ta có F là σ1 −cyclic, trong đó F được coi như một không gian vectơ trên K , nghĩa là với a ∈ F sao cho {a, σ1 (a), . . . , σ1m−1 (a)} là một cơ sở của F trên K . Đây là cơ sở chính tắc của F trên K . Định lý tiếp theo được biết đến như một tiêu chuẩn để xác định một phần tử α của trường Fq có đặc số lẻ có là thặng dư bậc hai hay không (tức là có tồn tại một phần tử β ∈ Fq sao cho α = β 2 hay không). Định lý 1.1.20. Cho F là trường hữu hạn có đặc số lẻ, |F | = q . Khi đó α ∈ F ∗ không là thặng dư bậc hai của F khi và chỉ khi α(q−1)/2 = −1.
2 Chứng minh. Với bất kỳ phần tử α khác 0, ta đều có α(q−1)/2 − 1 = 0 nên α(q−1)/2 = ±1, vì đa thức x2 − 1 = 0 chỉ có hai nghiệm trên một trường. Gọi θ là phần tử sinh của F∗q , khi đó α = θk với k là một số tự nhiên. Có hai trường hợp xảy ra: Nếu k chẵn, thì α = (θk/2 )2 là một thặng dư bậc hai trong F và α(q−1)/2 = θk.(q−1)/2 = (θk/2 )q−1 = 1. Nếu k lẻ ta viết α = θ2l+1 với số tự nhiên l, trường hợp này α không là thặng dư bậc hai trong F , và ta có α(q−1)/2 = (θ2l θ)(q−1)/2 = (θl )q−1 θ(q−1)/2 = −1, vì vậy θ(q−1)/2 phải bằng −1 do θ là phần tử sinh của F∗q . 13 Chú ý 1.1.21. Từ định lý trên ta có một phần tử khác không của trường hữu hạn có đặc số lẻ không phải thặng dư bậc hai khi và chỉ khi nó là luỹ thừa bậc lẻ của phần tử sinh của nhóm với phép nhân. Từ đó, ta có kết luận tích của một số không phải thặng dư bậc hai và một số thặng dư bậc hai (khác 0) là một số không phải thặng dư bậc hai, cũng như tích của hai số thặng dư bậc hai là một số thặng dư bậc hai và tích của hai số không phải thặng dư bậc hai là một số thặng dư bậc hai. 1.2 Đa thức tương hỗ Khi xây dựng dãy các đa thức bất khả quy, phần lớn các đa thức được xét đến là đa thức tự tương hỗ. Đa thức tự tương hỗ được định nghĩa như sau. n P Định nghĩa 1.2.1. Đa thức tương hỗ của đa thức f (x) = ak xk ∈ Fq [x] khác 0, có bậc n, ký hiệu là f ∗ , là đa thức f ∗ (x) = n P k=0 ak xn−k . Một đa thức k=0 được gọi là tự tương hỗ nếu f (x) = f ∗ (x). Với đa thức f (x) ∈ Fq [x] chúng ta có thể viết f ∗ (x) := xn f (1/x), (1.3) chú ý rằng f ∗ (x) ∈ Fq [x]. Chú ý 1.2.2. (i) Đa thức f (x) = n P ak xk tự tương hỗ khi và chỉ khi hệ k=0 số trong f đối xứng, nghĩa là ak = an−k , k = 0, . . . , n. (ii) Cho f (x), g(x) ∈ Fq [x], ta có (f g)∗ = xdeg f g f (1/x)g(1/x) = xdeg f f (1/x)xdeg g g(1/x) = f ∗ g ∗ và trong trường hợp cụ thể, (cf )∗ = cf ∗ với c ∈ Fq . Nếu f (0) 6= 0 thì (f ∗ )∗ = f. (iii) Cho f ∈ Fq [x] là đa thức bất khả quy trên Fq , f (0) 6= 0. Khi đó f ∗ bất khả quy trên Fq . 14 Chứng minh. (iii) Vì f (0) 6= 0 nên deg(f ) = deg(f ∗ ) và vì (f ∗ )∗ = f. Giả sử f ∗ = gh, deg(g) < deg(f ∗ ), deg(h) < deg(f ∗ ) khi đó f = (f ∗ )∗ = (gh)∗ = g ∗ h∗ kéo theo g ∗ hoặc h∗ là đa thức hằng. Không mất tổng quát, giả sử h∗ (x) = xdeg h h(1/x) là hằng số. Do đó ta có h(x) = axn với a ∈ Fq , n ∈ N kéo theo f ∗ (0) = 0 dẫn đến deg(f ) < deg(f ∗ ), vô lý. Do đó, n = 0 và f ∗ bất khả quy. 1.3 Công thức nghịch đảo Möbius Định nghĩa 1.3.1. Hàm Möbius µ là hàm số µ : N∗ → N được cho bởi công thức    1 nếu n = 1,   µ(n) = (−1)k nếu n là tích của k số nguyên tố khác nhau,    0 nếu n chia hết cho bình phương của một số nguyên tố. (1.4) Chú ý 1.3.2. Hàm Möbius µ còn có cách biểu diễn khác như sau: Cho ω(n) P 1, vì vậy ω(n) là số các ước số nguyên tố khác là hàm số học với ω(n) = p|n nhau của n. Khi đó    (−1)ω(n)   µ(n) =    0 nếu n không chia hết cho bình phương của (1.5) một số nguyên tố. trong các trường hợp còn lại. Định lý 1.3.3. µ(n) là một hàm số học, nhân tính và P µ(d) bằng 0 nếu d|n n > 1 và bằng 1 nếu n = 1. Chứng minh. Với trường hợp n = 1 hiển nhiên đúng. Ta chứng minh cho trường hợp n > 1. Cho n > 1 ta chỉ tính những số nguyên dương d chia hết n mà µ(d) 6= 0, tức là với d = 1 hoặc d là tích của các số nguyên tố khác nhau. Do vậy, nếu 15 p1 , p2 , . . . , pk là các số nguyên tố khác nhau, là ước của n, thì ta có X µ(d) = µ(1) + k X µ(pi ) + =1+ k 1 µ(pi1 pi2 ) + · · · + µ(p1 p2 . . . pk ) 1≤i1 1. d|n Chứng minh tương tự ta có định lý sau: Định lý 1.3.5. Nếu F, f là các hàm số học thỏa mãn f (n) = P với n ∈ N∗ thì F (n) = f (d) với mọi n ∈ N∗ . P µ(d)F (n/d) d|n d|n Định lý 1.3.6. Cho ϕ : N → C là hàm Euler tổng quát. Khi đó ϕ(n) X µ(d) = . n d d|n Chứng minh. Ta có X d|n ϕ(d) = n := F (n) (1.6) 16 Áp dụng công thức nghịch đảo Möbius ta có: X ϕ(d) = F (n) ⇒ ϕ(n) = X d|n d|n µ(d) n ϕ(n) X µ(d) ⇒ = . d n d d|n Định lý 1.3.7. Cho Fq là trường hữu hạn. Gọi Id (n) là số các đa thức dạng chuẩn bất khả quy trên Fq bậc n. Khi đó 1X µ(d)q n/d . Iq (n) = n d|n n Chứng minh. Với n cho trước, ta xét đa thức g(x) = xq − x. Ta có trường phân rã của g(x) trên Fq là Fqn . Với mỗi đa thức f (x) bậc m, bất khả quy trên Fq theo chứng minh Định lý 1.1.10 ta có f (x) | g(x) khi và chỉ khi m | n. n Chúng ta đã chỉ ra rằng xq − x là tích của tất cả các đa thức dạng chuẩn P bất khả quy trên Fq với bậc là ước của n. Do đó ta có q n = Iq (d)d. Đặt d|n n F (n) = q , f (n) = nIq (n) và áp dụng công thức nghịch đảo Möbius thì ta thu được: X 1X f (n) = µ(d)F n | d ⇒ Iq (n) = µ(d)q n/d . n d|n d|n Ví dụ 1.3.8. (i) Số các đa thức dạng chuẩn bất khả quy trong Fq [x] có bậc 20 được cho bởi công thức: 1 X µ(d)q 20/d Iq (20) = 20 d|20   1 = µ(1)q 20 + µ(2)q 10 + µ(4)q 5 + µ(5)q 4 + µ(10)q 2 + µ(20)q . 20 Trong đó µ(1) = 1, µ(2) = (−1)1 = −1, µ(4) = 0 µ(5) = (−1)1 = −1, µ(10) = (−1)2 = 1, µ(20) = 0. 17 Do đó 1 20 (q − q 10 − q 4 + q 2 ). 20 (ii) Tương tự, chúng ta có thể tính số các đa thức dạng chuẩn bất khả quy trong Fq [x] có bậc 30 được cho bởi công thức:  1 X 1 30/d Iq (30) = µ(d)q = µ(1)q 30 + µ(2)q 15 + 30 30 d|30  + µ(3)q 10 + µ(5)q 6 + µ(6)q 5 + µ(15)q 2 + µ(30)q Iq (20) = = 1 30 (q − q 15 − q 10 − q 6 + q 5 + q 2 − q). 30