Luận văn Đa thức hoán vị được

40 trang phuongnguyen 6020

Download

Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Đa thức hoán vị được", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

luan_van_da_thuc_hoan_vi_duoc.pdf

Nội dung text: Luận văn Đa thức hoán vị được

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VƯƠNG THỊ YẾN ĐA THỨC HỐN VỊ ĐƯỢC LUẬN VĂN THẠC SỸ TỐN HỌC Chuyên ngành : PHƯƠNG PHÁP TỐN SƠ CẤP Mã số : 60 46 40 Giáo viên hướng dẫn: PGS.TS. LÊ THỊ THANH NHÀN THÁI NGUYÊN, 2012 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2 Mục lục Mục lục 2 Lời cảm ơn 3 Lời nĩi đầu 4 1 Kiến thức chuẩn bị 6 1.1 Kiến thức chuẩn bị về nhĩm . . . . . . . . . . . . . . . 6 1.2 Kiến thức chuẩn bị về vành . . . . . . . . . . . . . . . . 10 1.3 Kiến thức chuẩn bị về trường . . . . . . . . . . . . . . . 14 1.4 Kiến thức chuẩn bị về đa thức . . . . . . . . . . . . . . 17 2 Đa thức hốn vị được 20 2.1 Khái niệm đa thức hốn vị được . . . . . . . . . . . . . 20 2.2 Một số lớp đa thức hốn vị được trên một trường . . . . 26 2.3 Đa thức hốn vị được modulo 2k . . . . . . . . . . . . 30 Kết luận 39 Tài liệu tham khảo 40 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3 Lời cảm ơn Đề tài được thực hiện tại trường Đại học Khoa học - Đại học Thái Nguyên dưới sự hướng dẫn của PGS.TS Lê Thị Thanh Nhàn. Tơi xin bày tỏ lịng biết ơn sâu sắc, chân thành nhất đối với Cơ. Bởi sự giúp đỡ, chỉ bảo, khuyến khích ân cần của Cơ đã gĩp phần rất lớn cho sự thành cơng của luận văn này. Tơi cũng xin được bày tỏ lịng cảm ơn chân thành nhất tới Ban lãnh đạo, Phịng Đào tạo - Khoa học và Quan hệ quốc tế, Khoa Tốn - Tin Trường Đại học khoa học - Đại học Thái Nguyên đã tạo điều kiện thuận lợi để tơi và các bạn học viên cao học Khĩa 4 (2010 - 2012) được học tập, nghiên cứu. Tơi cũng xin cảm ơn các Thầy, Cơ là GS.TSKH Hà Huy Khối, GS.TSKH Nguyễn Văn Mậu, là những nhà tốn học hàng đầu Việt Nam đã giảng dạy các chuyên đề cho lớp chúng tơi. Cuối cùng, tơi xin được gửi lời cảm ơn tới gia đình, bạn bè, những người thân đã luơn ở bên, động viên, giúp đỡ để tơi cĩ thể hồn thành luận văn. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4 Lời nĩi đầu Ta đã biết rằng một đa thức fpxq trên một vành hữu hạn R được gọi là hốn vị được nếu đa thức đĩ hốn vị được các phần tử của vành R, tức là ánh xạ ϕ : R Đ R cho bởi ϕpaq fpaq phải là một song ánh. Trong cuốn "Finite fields" xuất bản lần đầu tiên năm 1983, Lidl và Niedereiter [LN] đã nghiên cứu các tiêu chuẩn của đa thức hốn vị được, các dạng đặc biệt của đa thức hốn vị được, nhĩm các đa thức hốn vị được, trường hợp ngoại lệ của đa thức hốn vị được và đa thức hốn vị được ở một số dạng bất định. Lidl và Mullen [LM1,2] cũng đã nghiên đa thức hốn vị được trên trường hữu hạn. Năm 1986, R. A. Mollin và C. Small [MS] đã đưa ra tiêu chuẩn đa thức hốn vị được dạng xn. Năm 1999, R. Rivest [Riv] đưa ra tiêu chuẩn đa thức hốn vị được modulo 2k. Trong đề tài này chúng tơi trình bày lại các kết quả trong hai bài báo của R.A.Mollin và C.Small [MS] và của R.Rivest [Riv] về đặc trưng tính hốn vị được của đa thức dạng xn và đa thức dạng xk bxj c với pk ¡ j ¥ 1q trên một trường hữu hạn, đồng thời xét tính hốn vị được n k của đa thức dạng P pxq a0 a1x anx với n 2 trên vành Z2k . Luận văn gồm 2 chương. Chương 1 trình bày kiến thức chuẩn bị về nhĩm, vành, trường và đa thức nhằm phục vụ cho việc chứng minh các kết quả ở chương sau. Trong phần đầu của Chương 2 trình bày khái niệm đa thức hốn vị được và một số ví dụ đơn giản. Phần thứ 2 của Chương 2 giành để chứng minh tiêu chuẩn hốn vị được trên một trường hữu hạn của một số lớp đa thức dạng xn (Định lý 2.1.7) và đa thức dạng xk bxj c với k ¡ j ¥ 1 (Định lý 2.2.1). Phần cuối của Chương 2 nhằm trình bày một điều kiện cần và đủ để một đa thức với hệ số nguyên Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5 k hốn vị được theo modulo 2 , tức là hốn vị được trên vành Z2k (Định lý 2.3.10). Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6 Chương 1 Kiến thức chuẩn bị Chương này trình bày khái niệm và những kết quả chuẩn bị về nhĩm, vành, trường và đa thức phục vụ cho chứng minh các kết quả của chương sau. 1.1 Kiến thức chuẩn bị về nhĩm 1.1.1 Định nghĩa. Nhĩm là một tập G cùng với một phép tốn (kí hiệu theo lối nhân) thoả mãn các điều kiện (i) Phép tốn cĩ tính kết hợp: apbcq pabqc, @a, b, c P G. (ii) G cĩ đơn vị: De P G sao cho ex xe x, @x P G. (iii) Mọi phần tử của G đều khả nghịch: Với mỗi x P G, tồn tại x¡1 P G sao cho xx¡1 x¡1x e. Một nhĩm G được gọi là nhĩm giao hốn (hay nhĩm Abel) nếu phép tốn là giao hốn. Nếu G cĩ hữu hạn phần tử thì số phần tử của G được gọi là cấp của G. Nếu G cĩ vơ hạn phần tử thì ta nĩi G cĩ cấp vơ hạn. Sau đây là một số ví dụ về nhĩm: Z, Q, R, C là các nhĩm giao hốn cấp vơ hạn với phép cộng thơng thường. Với mỗi số nguyên m ¥ 1, tập Zm ta | a P Z, a b nếu và chỉ nếu a ¡ b chia hết cho mu các số nguyên modulo m với phép cộng a b a b là một nhĩm giao Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7 hốn cấp m. Tập ¦ t P | p q u Zm a Zm a, m 1 các số nguyên modulo m nguyên tố cùng nhau với m với phép nhân a b ab là một nhĩm giao hốn cấp ϕpmq, trong đĩ ϕ là hàm Euler, tức là ϕp1q 1 và khi m ¡ 1 thì ϕpmq là số các số tự nhiên nhỏ hơn m và nguyên tố cùng nhau với m. 1.1.2 Định nghĩa. Một nhĩm G được gọi là xyclic nếu tồn tại a P G sao cho mỗi phần tử của G đều là một luỹ thừa của a. Trong trường hợp này ta viết G paq và ta gọi G là nhĩm xyclic sinh bởi a. Phần tử a được gọi là một phần tử sinh của G. 1.1.3 Bổ đề. Nhĩm con của nhĩm xyclic là xyclic. Chứng minh. Giả sử G paq là nhĩm xyclic. Cho H là nhĩm con của G. Nếu H teu thì H là nhĩm xyclic sinh bởi e. Giả sử H teu. Chọn e x P H. Viết x ak. Do x e nên k 0. Vì H là nhĩm con nên a¡k P H. Trong hai số k và ¡k ắt phải cĩ một số nguyên dương. Vì thế H chứa những lũy thừa nguyên dương của a. Gọi r là số nguyên dương bé nhất sao cho ar P H. Rõ ràng H parq. Cho y P H. Viết y at với t rq s, trong đĩ 0 ¤ s r. Ta cĩ y at parqqas. Do đĩ as yparq¡q P H. Từ cách chọn của r ta suy ra s 0. Do đĩ y at parqq P parq. Vậy H parq là nhĩm xyclic. 1.1.4 Định nghĩa. Tập con H của một nhĩm G được gọi là nhĩm con của G nếu e P H, a¡1 P H và ab P H với mọi a, b P H. Cho G là một nhĩm. Khi đĩ teu là nhĩm con bé nhất của G và G là n nhĩm con lớn nhất của G. Cho a P G. Đặt paq ta | n P Zu. Khi đĩ paq là nhĩm con của G, được gọi là nhĩm con xyclic sinh bởi a. Cấp của nhĩm con paq được gọi là cấp của phần tử a. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8 1.1.5 Bổ đề. Cho G là một nhĩm và a là một phần tử của G. Các phát biểu sau là tương đương (i) a cĩ cấp n. (ii) n là số nguyên dương bé nhất sao cho an e. n k (iii) a e và nếu a e thì k là bội của n với mọi k P Z. Chứng minh. (i)đ(ii). Trước hết ta khẳng định tồn tại một số nguyên dương k sao cho ak e. Giả sử ngược lại, với mọi cặp số tự nhiên k k1 1 1 ta cĩ ak ¡k e. Suy ra ak ak . Điều này chứng tỏ paq cĩ cấp vơ hạn, vơ lí với giả thiết (i). Do đĩ, tồn tại những số nguyên dương k sao cho ak e. Gọi r là số nguyên dương bé nhất cĩ tính chất ar e. Ta thấy rằng các phần tử e, a, a2, . . . , ar¡1 là đơi một khác nhau. Thật vậy, nếu ai aj với 0 ¤ i ¤ j r thì aj¡i e và 0 ¤ j ¡ i r, do đĩ theo cách chọn của r ta cĩ i j. Bây giờ ta chứng minh G te, a, a2, . . . , ar¡1u. 2 r¡1 k Rõ ràng G te, a, a , . . . , a u. Cho b P G. Khi đĩ b a với k P Z. Viết k rq s trong đĩ q, s P Z và 0 ¤ s ¤ r ¡ 1. Ta cĩ b ak arq s parqqas as P te, a, a2, . . . , ar¡1u. Vì thế G te, a, a2, . . . , ar¡1u là nhĩm cấp r. Suy ra r n và (ii) được chứng minh. (ii)đ(iii). Giả sử ak e. Viết k nq r với 0 ¤ r n. Vì an e nên e ak anqar ar. Theo cách chọn n ta phải cĩ r 0, suy ra k chia hết cho n. (iii)đ(i). Gọi r là số nguyên dương bé nhất sao cho ar e. Theo (iii), r là bội của n. Do đĩ n là số nguyên dương bé nhất thỏa mãn an e. Tương tự như chứng minh (i)Đ(ii) ta suy ra cấp của a là n. 1.1.6 Hệ quả. Cho G paq là nhĩm xyclic cấp n. Khi đĩ phần tử b ak là phần tử sinh của G nếu và chỉ nếu pk, nq 1. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9 Chứng minh. Giả sử b ak là phần tử sinh của G. Khi đĩ b cĩ cấp n. Đặt d pk, nq. Ta cĩ bn{d panqk{d e. Theo Bổ đề 1.1.5, n{d là bội của n. Vì thế d 1. Ngược lại, giả sử pk, nq 1. Ta cĩ bn panqk e. Giả sử bt e. Khi đĩ akt e. Theo Bổ đề 1.1.5, kt là bội của n. Do pk, nq 1 nên t là bội của n. Theo Bổ đề 1.1.5, b cĩ cấp n. Vậy G pbq. 1.1.7 Định nghĩa. Cho G là nhĩm và H là nhĩm con của G. Với mỗi a P G, kí hiệu Ha tha | h P Hu. Ta gọi Ha là một lớp ghép trái hay lớp kề trái của H trong G ứng với phần tử a. Tập các lớp ghép trái của H trong G được kí hiệu là G{H. Khi H chỉ cĩ hữu hạn lớp ghép trái thì số các lớp ghép trái của H được gọi là chỉ số của H trong G và được kí hiệu là pG : Hq. Trong trường hợp này, chỉ số của H chính là số phần tử của G{H. Đặc biệt, cấp của G chính là pG : eq, chỉ số của nhĩm con tầm thường teu. Với H là nhĩm con của nhĩm G và a, b P G, ta dễ dàng kiểm tra được Ha Hb nếu và chỉ nếu ab¡1 P H. 1.1.8 Định lý. (Lagrange). Trong một nhĩm hữu hạn, cấp và chỉ số của một nhĩm con là ước của cấp của tồn nhĩm. Chứng minh. Giả sử G là nhĩm cĩ cấp n và H là nhĩm con của G cĩ cấp m. Với mỗi a P G ta cĩ a ea P Ha. Vì thế, mỗi phần tử của G đều thuộc một lớp ghép trái của H. Giả sử Ha X Hb H. Khi đĩ tồn tại h, h1 P H sao cho ha h1b. Suy ra a h¡1h1b. Cho xa P Ha, trong đĩ x P H. Khi đĩ xa pxh¡1h1qb P Hb. Suy ra Ha Hb. Tương tự, Hb Ha và do đĩ Ha Hb. Vậy hai lớp ghép trái bất kì của H nếu khác nhau thì phải rời nhau. Với mỗi a P G, rõ ràng ánh xạ f : H ÝĐ Ha xác định bởi fphq ha là một song ánh. Vì thế mỗi lớp ghép trái của H đều cĩ đúng m phần tử. Gọi chỉ số của H là s. Từ các lập luận trên ta suy ra n sm. Vì thế s và m đều là ước của n. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10 1.1.9 Hệ quả. Cho G là nhĩm cấp n và a P G. Khi đĩ cấp của a là ước của n. Hơn nữa, an e. Chứng minh. Gọi cấp của a là r. Khi đĩ nhĩm con xyclic paq cĩ cấp r. Theo Định lí Lagrange, r là ước của n. Theo Bổ đề 1.1.5 ta cĩ ar e. Suy ra an e. 1.1.10 Hệ quả. Mọi nhĩm cấp nguyên tố đều là nhĩm xyclic. Chứng minh. Giả sử G là nhĩm cấp p nguyên tố. Lấy a P G, a e. Theo Định lí Lagrange, a cĩ cấp là ước của p. Vì p nguyên tố nên cấp của a là 1 hoặc là p. Do a e nên cấp của a lớn hơn 1. Vậy cấp của a là p, tức G là nhĩm xyclic sinh bởi a. 1.2 Kiến thức chuẩn bị về vành 1.2.1 Định nghĩa. Vành là một tập V được trang bị hai phép tốn cộng và nhân thỏa mãn các điều kiện sau đây: (i) V là một nhĩm giao hốn với phép cộng; (ii) V là một vị nhĩm với phép nhân: Phép nhân cĩ tính chất kết hợp và tồn tại phần tử 1 P V (gọi là phần tử đơn vị) sao cho 1x x1 x với mọi x P V ; (iii)Phép nhân phân phối đối với phép cộng. Nếu phép nhân là giao hốn thì V được gọi là vành giao hốn. Sau đây là một số ví dụ thường gặp về vành: 1.2.2 Ví dụ. a) Rõ ràng Z, Q, R, C là những vành giao hốn với phép cộng và nhân thơng thường; b) Với mỗi số tự nhiên n ¡ 0, tập Zn các số nguyên modulo n làm thành một vành giao hốn với phép cộng và phép nhân cho bởi: a b a b và a b ab với mọi a, b P Zn. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11 c) Cho R là một vành. Kí hiệu n Rrxs ta0 a1x anx | n P N, ai P R, @iu là tập các đa thức một biến x với hệ số trong R. Khi đĩ Rrxs là một ° ° vành giao hốn với phép cộng và nhân các đa thức: a xi b xi ° ° ° ° ° i i p q i i i k ai bi x và aix bix ckx với ck i jk aibj. Ta gọi Rrxs là vành đa thức một biến x trên R. Rõ ràng R giao hốn nếu và chỉ nếu Rrxs là giao hốn. 1.2.3 Định nghĩa. Cho V là một vành. Một tập con S của V được gọi là vành con của V nếu ¡1 P S và x y, xy P S với mọi x, y P S. Dễ thấy rằng tập con S của vành V là vành con của V nếu và chỉ nếu phép cộng và phép nhân đĩng kín trong S và S làm thành một vành cùng với hai phép tốn này. 1.2.4 Định nghĩa. Cho V là vành và I là tập con của V. Ta nĩi rằng I là iđêan của V nếu I là nhĩm con của nhĩm cộng V và xa, ax P I với mọi a P I, x P V. Cho V là một vành. Dễ thấy rằng t0u là iđêan bé nhất của V và V là iđêan lớn nhất của V. Idêan t0u được kí hiệu là 0. Các iđêan của V khác V được gọi là các iđêan thực sự. 1.2.5 Định nghĩa. Cho V là vành và I là iđêan của V. Xét tập V {I tx I | x P V u - tập các lớp ghép của V theo nhĩm con I. Rõ ràng hai phần tử x I, y I P V {I là bằng nhau nếu và chỉ nếu x ¡ y P I. Trong tập V {I, ta định nghĩa quy tắc cộng px Iq py Iq px yq I và quy tắc nhân px Iqpy Iq xy I. Ta cĩ thể kiểm tra rằng quy tắc cộng và nhân ở trên khơng phụ thuộc vào việc chọn đại diện của các phần tử, tức là nếu x1 I x I và y1 I y I thì x y I x1 y1 I và xy I x1y1 I. Vì thế các quy tắc cộng và nhân này là hai phép Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12 tốn trên V {I. Hơn nữa, tập V {I cùng với phép cộng và nhân xác định như trên là một vành giao hốn, cĩ đơn vị là 1 I và phần tử khơng là 0 I. Vành V {I vừa xây dựng ở trên được gọi là vành thương của V theo iđêan I. Chú ý rằng vành thương của vành Z theo iđêan mZ chính là vành Zm các số nguyên modulo m. 1.2.6 Định nghĩa. Một đồng cấu vành là một ánh xạ f từ vành V đến vành S sao cho (i) fpa a1q fpaq fpa1q với mọi a, a1 P V. (ii) fpaa1q fpaqfpa1q với mọi a, a1 P V. (iii) fp1q 1. Đồng cấu f được gọi là đơn cấu (tồn cấu, đẳng cấu) nếu f là đơn ánh (tồn ánh, song ánh). Vành V được gọi là đẳng cấu với vành S nếu tồn tại một đẳng cấu giữa chúng. Một đồng cấu (đơn cấu, tồn cấu, đẳng cấu) từ vành S đến S được gọi là một tự đồng cấu (tự đơn cấu, tự tồn cấu, tự đẳng cấu). Mệnh đề sau đây cho ta tính chất của vành con và iđêan khi tác động qua một đồng cấu vành. 1.2.7 Mệnh đề. Cho f : V ÝĐ S là đồng cấu vành, B là vành con của V và J là iđêan của S. Các phát biểu sau là đúng. (i) fpBq là vành con của S. (ii) f ¡1pJq là iđêan của V. Chứng minh. piq. Cho s, r P fpBq. Khi đĩ s fpbq và r fpcq với b, c P B. Vì b c, bc P B nên s r fpbq fpcq fpb cq P fpBq và sr fpbqfpcq fpbcq P fpBq. Vì ¡1 P B nên ¡1 ¡fp1q fp¡1q P fpBq. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13 Vậy fpBq là vành con của S. piiq. Do fp0q 0 P J nên 0 P f ¡1pJq. Cho a, b P f ¡1pJq. Khi đĩ fpaq, fpbq P J. Suy ra fpa ¡ bq fpaq ¡ fpbq P J. Do đĩ ta cĩ a ¡ b P f ¡1pJq. Vì thế f ¡1pJq là nhĩm con của nhĩm cộng V. Cuối cùng, cho a P f ¡1pJq và x P V. Khi đĩ fpaq P J. Suy ra fpaxq fpaqfpxq P J, tức là ax P f ¡1pJq. Tương tự, xa P f ¡1pJq. Vậy f ¡1pJq là iđêan của V. 1.2.8 Định nghĩa. Cho f : V ÝĐ S là một đồng cấu vành. Vì V là vành con của V nên fpV q là vành con của S. Vành con fpV q được gọi là ảnh của f và được kí hiệu bởi Im f. Đặt Ker f ta P V | fpaq 0u. Khi đĩ Ker f f ¡1p0q. Vì 0 là iđêan của S nên theo Mệnh đề 1.2.7, Ker f là iđêan của V. Ta gọi Ker f là hạt nhân của f. 1.2.9 Mệnh đề. Cho f : V ÝĐ S là đồng cấu vành. Khi đĩ f là đơn cấu nếu và chỉ nếu Ker f 0. Trong trường hợp này, V đẳng cấu với vành con Im f của S. Chứng minh. Giả sử f là đơn cấu. Rõ ràng 0 P Ker f. Cho a P Ker f. Khi đĩ fpaq 0 fp0q. Suy ra a 0. Vì thế Ker f 0. Giả sử Ker f 0. Cho a, b P V sao cho fpaq fpbq. Khi đĩ fpa ¡ bq 0. Suy ra a ¡ b P Ker f 0. Vì thế a ¡ b 0 hay a b. Vậy f là đơn cấu. 1.2.10 Định lý. (Định lí đồng cấu vành). Cho f : V ÝĐ S là đồng cấu vành. Khi đĩ V { Ker f Im f. 1.2.11 Định nghĩa. Cho V là vành. Giả sử tồn tại số nguyên n 0 sao cho n1 0. Khi đĩ p¡nq1 0. Trong hai số n và ¡n ắt phải cĩ một số nguyên dương. Trong trường hợp này, ta gọi đặc số của V là số nguyên dương n nhỏ nhất sao cho n1 0. Nếu n1 0 chỉ xảy ra khi n 0 thì ta nĩi V cĩ đặc số 0. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14 Dễ thấy rằng vành Z các số nguyên, vành Q các số hữu tỷ, vành R các số thực, vành C các số phức đều cĩ đặc số 0. Vành Zm các số nguyên modulo m cĩ đặc số m. 1.2.12 Mệnh đề. Cho V là một vành. Các phát biểu sau là đúng. piq Nếu V cĩ đặc số 0 thì V chứa một vành con đẳng cấu với vành Z. piiq Nếu V cĩ đặc số m thì V chứa một vành con đẳng cấu với Zm. Chứng minh. Xét ánh xạ f : Z ÝĐ V xác định bởi fpnq n1 với mọi n P Z. Dễ thấy rằng f là đồng cấu vành. Giả sử V cĩ đặc số 0. Khi đĩ fpnq 0 khi và chỉ khi n 0. Vì thế f là đơn cấu. Do đĩ Z Im f. Vì thế Im f là vành con của V đẳng cấu với Z. Giả sử V cĩ đặc số m. Khi đĩ Ker f mZ. Theo Định lí 1.2.10, Z{mZ Im f. Vì thế Im f là vành con của V đẳng cấu với Zm. 1.3 Kiến thức chuẩn bị về trường 1.3.1 Định nghĩa. Một phần tử a của vành giao hốn R được gọi là khả nghịch nếu tồn tại b P R sao cho ab 1. Trường là một vành giao hốn, khác 0 và mọi phần tử khác 0 đều khả nghịch. Chú ý rằng vành Z6 khơng là trường vì 2 P Z6 khơng khả nghịch. Vành Z khơng là trường vì 2 P Z khơng khả nghịch. Các vành Q, R và C đều là trường. 1.3.2 Bổ đề. Đặc số của trường là 0 hoặc là số nguyên tố. Chứng minh. Giả sử T là trường cĩ đặc số n 0. Vì 1 0 nên n ¡ 1. Nếu n khơng nguyên tố thì n ab với 1 a, b n. Vì n là số nguyên dương bé nhất thoả mãn n1 0 nên a1, b1 0. Do đĩ tồn tại các phần tử x, y P T sao cho xpa1q 1 ypb1q. Vì thế ta cĩ 0 pn1qxy xpa1qypb1q 1.1 1. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15 Điều này là vơ lí. 1.3.3 Bổ đề. Vành Zn là trường khi và chỉ khi n là số nguyên tố. Chứng minh. Cho Zn là trường. Vì Zn cĩ đặc số n nên theo Bổ đề 1.3.2, n là số nguyên tố. Cho n là số nguyên tố. Khi đĩ n ¡ 1. Vì thế Zn 0. Cho 0 a P Zn. Khi đĩ a khơng là bội của n. Vì n nguyên tố nên a và n nguyên tố cùng nhau, tức là tồn tại x, y P Z sao cho 1 ax ny. Suy ra 1 a x, tức là a khả nghịch. Vậy Zn là trường. 1.3.4 Định nghĩa. Một tập con A của trường T được gọi là một trường con nếu phép cộng và nhân là đĩng kín trong A và A làm thành một trường cùng với hai phép tốn này. Giả sử T là một trường cĩ đặc số m ¡ 0. Theo Bổ đề 1.3.2, m phải là số nguyên tố. Theo Mệnh đề 1.2.12, T chứa một trường con đẳng cấu với trường Zm. Trong phần cuối của mục này, chúng ta nghiên cứu số phần tử của một trường hữu hạn. Trước hết ta cần nhắc lại một số khái niệm và tính chất của khơng gian véc tơ. 1.3.5 Định nghĩa. Cho K là một trường. Một tập V cĩ trang bị một phép cộng và một ánh xạ K ¢V ÝĐ V (gọi là phép nhân với vơ hướng) được gọi là một khơng gian véc tơ trên trường K hay một K-khơng gian vec tơ nếu pV, q là một nhĩm giao hốn và tích vơ hướng thoả mãn các tính chất sau đây: với mọi x, y P K và mọi α, β P V ta cĩ (i) Phân phối: px yq.α x.α y.α và x.pα βq x.α x.β; (ii) Kết hợp: xpyαq px.yq.α; (iii) Unita: 1α α. 1.3.6 Định nghĩa. Giả sử V là một K-khơng gian véc tơ. (i) Một hệ véc tơ tviuiPI trong V được gọi là một hệ sinh của V nếu mọi phần tử x P V đều cĩ thể biểu thị tuyến tính theo hệ đĩ, tức là Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16 tồn tại hữu hạn phần tử v , . . . , v của hệ tv u P và hữu hạn phần tử i1 ° ik i i I k ai1, . . . , aik của K sao cho x j1aijvij. Nếu V cĩ một hệ sinh gồm hữu hạn phần tử thì V được gọi là K-khơng gian hữu hạn sinh. (ii) Một hệ véc tơ tv u P trong V được gọi là một hệ độc lập tuyến i i I ° k tính nếu từ mỗi ràng buộc tuyến tính của hệ j1aijvij 0 ta đều cĩ aij 0 với mọi j 1, . . . , k. (iii) Một hệ véc tơ trong V được gọi là một cơ sở của V nếu nĩ là một hệ sinh và độc lập tuyến tính. Chú ý rằng một hệ véc tơ của V là một cơ sở của V nếu và chỉ nếu mỗi véc tơ của V đều cĩ thể biểu thị tuyến tính một cách duy nhất qua hệ đĩ. Ta cĩ thể chỉ ra rằng mỗi K-khơng gian véc tơ V 0 đều cĩ ít nhất một cơ sở và các cơ sở của V đều cĩ cùng lực lượng. Lực lượng chung này được gọi là số chiều của V và kí hiệu là dimK V. Đặc biệt, nếu V cĩ một cơ sở gồm n phần tử thì các cơ sở khác của V cũng cĩ n phần tử và ta cĩ dimK V n. 1.3.7 Mệnh đề. Cho T là trường hữu hạn cĩ n phần tử. Khi đĩ T cĩ đặc số p nguyên tố và n là lũy thừa nào đĩ của p. Chứng minh. Theo Bổ đề 1.3.2, đặc số của T là 0 hoặc là số nguyên tố. Nếu T cĩ đặc số 0 thì theo Mệnh đề 1.2.12, T chứa một vành con đẳng cấu với Z, do đĩ T cĩ vơ hạn phần tử, vơ lí. Vì thế T cĩ đặc số p ¡ 0. Theo Bổ đề 1.3.2, p là số nguyên tố. Theo Mệnh đề 1.2.12, T chứa một vành con đẳng cấu với Zp. Chú ý rằng Zp là trường theo Bổ đề 1.3.3. Vì thế ta dễ dàng kiểm tra rằng T cĩ cấu trúc tự nhiên là một khơng gian véc tơ trên trường Zp. Do T cĩ hữu hạn phần tử nên khơng gian này cĩ chiều hữu hạn. Giả sử dimZp T k. Khi đĩ số phần tử của T là n pk. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17 1.4 Kiến thức chuẩn bị về đa thức Trong mục này ta giả thiết K là một trường. Nhắc lại rằng một đa thức một biến x với hệ số trong K là một biểu thức dạng fpxq n n¡1 anx an¡1x a0 trong đĩ ai P K. Nếu an 0 thì an được gọi là hệ số cao nhất của fpxq và số tự nhiên n được gọi là bậc của fpxq. Ta kí hiệu bậc của fpxq là deg fpxq. Kí hiệu Krxs là tập các đa thức ° ° một biến x với hệ số trong K. Giả sử fpxq a xi và gpxq b xi, ° i ° i ta định nghĩa fpxq gpxq pa b qxi và fpxqgpxq c xk, trong ° i i k r s đĩ ck i jk aibj. Khi đĩ K x là một vành, gọi là vành đa thức một biến x với hệ số trong K. 1.4.1 Chú ý. Với fpxq, gpxq P Krxs ta luơn cĩ degpfpxq gpxqq ¤ maxtdeg fpxq, deg gpxqu degpfpxq.gpxqq deg fpxq deg gpxq. Tiếp theo là định lí phép chia với dư cho đa thức một biến. 1.4.2 Định lý. Cho fpxq, gpxq P Krxs với gpxq 0. Khi đĩ tồn tại duy nhất một cặp đa thức qpxq, rpxq P Krxs sao cho fpxq gpxqqpxq rpxq, với rpxq 0 hoặc deg rpxq deg gpxq. Chứng minh. Chứng minh tính duy nhất. Giả sử fpxq gpxqqpxq rpxq gpxqq1pxq r1pxq, trong đĩ rpxq, r1pxq bằng 0 hoặc cĩ bậc nhỏ hơn bậc của gpxq. Khi đĩ gpxqpqpxq ¡ q1pxqq r1pxq ¡ rpxq. Nếu r1pxq rpxq thì gpxqpqpxq ¡ q1pxqq 0. Vì gpxq 0 và K là trường nên qpxq ¡ q1pxq 0, tức là qpxq q1pxq. Nếu rpxq r1pxq thì ¨ degpr ¡ r1q deg gpq ¡ q1q deg g degpq ¡ q1q. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18 Chú ý rằng degpr ¡ r1q ¤ maxtdeg r, deg r1u deg g ¤ deg g degpq ¡ q1q. Điều này mâu thuẫn với đẳng thức trên. Ta chứng minh sự tồn tại của qpxq và rpxq. Nếu deg fpxq deg gpxq thì ta chọn qpxq 0 và rpxq fpxq. Giả sử deg fpxq ¥ deg gpxq. Cho m n fpxq amx a0 và gpxq bnx b0 với am, bn 0 và am m¡n n ¤ m. Chọn hpxq x . Đặt f1pxq fpxq ¡ gpxqhpxq. Khi đĩ bn f1pxq 0 hoặc f1pxq cĩ bậc thực sự bé hơn bậc của fpxq. Trong trường hợp f1pxq 0, ta tìm được dư của phép chia fpxq cho gpxq là rpxq 0 và thương là qpxq hpxq. Nếu f1pxq 0 thì ta tiếp tục làm tương tự với f1pxq và ta được đa thức f2pxq. Cứ tiếp tục quá trình trên ta được dãy đa thức f1pxq, f2pxq, , nếu chúng đều khác 0 thì chúng cĩ bậc giảm dần. Vì thế sau hữu hạn bước ta được một đa thức cĩ bậc bé hơn bậc của gpxq và đĩ chính là đa thức dư rpxq. Nếu một đa thức của dãy bằng 0 thì dư rpxq 0. Cụ thể, ta cĩ f1pxq fpxq ¡ gpxqhpxq f2pxq f1pxq ¡ gpxqh1pxq fkpxq fk¡1pxq ¡ gpxqhk¡1pxq với fkpxq 0 hoặc deg fkpxq deg gpxq. Cộng vế với vế các đẳng thức đĩ lại, ta được fpxq gpxqphpxq h1pxq hk¡1pxqq fkpxq. Từ đĩ ta cĩ qpxq hpxq h1pxq hk¡1pxq và rpxq fkpxq. Trong định lý trên, nếu rpxq 0 thì qpxq được gọi là thương hụt và rpxq được gọi là dư của phép chia fpxq cho gpxq. Nếu rpxq 0 thì ta nĩi rằng fpxq chia hết cho gpxq hay gpxq là ước của fpxq. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19 1.4.3 Hệ quả. Cho K là một trường và a P K. Khi đĩ dư của phép chia fpxq P Krxs cho x ¡ a là fpaq. Chứng minh. Chia fpxq cho x ¡ a, dư hoặc bằng 0 hoặc là một đa thức bậc 0 vì bậc của px ¡ aq bằng 1. Vì vậy, dư là một phần tử r P K. Ta cĩ fpxq px¡aqqpxq r. Thay x a vào đẳng thức ta được r fpaq. Một phần tử a P K được gọi là nghiệm của fpxq P Krxs nếu fpaq 0. Từ Hệ quả 1.4.3 ta cĩ ngay kết quả sau. 1.4.4 Hệ quả. Cho K là một trường và a P K. Khi đĩ a là nghiệm của đa thức fpxq P Krxs nếu và chỉ nếu tồn tại đa thức gpxq P Krxs sao cho fpxq px ¡ aqgpxq. Từ Hệ quả 1.4.4 ta cĩ ngay kết quả sau. 1.4.5 Hệ quả. Cho fpxq P Krxs là đa thức khác 0 và a1, a2, . . . , ar P K là các nghiệm phân biệt của fpxq. Khi đĩ deg fpxq ¥ r. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20 Chương 2 Đa thức hốn vị được 2.1 Khái niệm đa thức hốn vị được 2.1.1 Định nghĩa. (i) Cho R là một vành giao hốn cĩ hữu hạn phần tử. Cho fpxq P Rrxs. Ta nĩi rằng fpxq là đa thức hốn vị được trên R nếu ánh xạ ϕ : R Đ R cho bởi ϕpaq fpaq là một song ánh. (ii) Giả sử fpxq là đa thức với hệ số nguyên. Với n là một số nguyên dương cho trước, xét fpxq như đa thức trong Znrxs. Ta nĩi fpxq là hốn vị được modulo n nếu nĩ là đa thức hốn vị được trên Zn. Dưới đây là một số ví dụ về đa thức hốn vị được. 2.1.2 Ví dụ. Xét R Z2 - trường các số nguyên modulo 2. Cho fpxq 2 3 2 1 5x 2x 3x và gpxq 1 x 4x . Trong Z2rxs, đa thức fpxq cĩ dạng fpxq 1 x x3 và đa thức gpxq cĩ dạng gpxq 1 x. Ta cĩ fp0q 1 và fp1q 1. Vì thế ánh xạ ϕ : Z2 Đ Z2 cho bởi ϕpaq fpaq khơng phải là song ánh. Ta cĩ gp0q 1 và gp1q 0. Vì thế ánh xạ ϕ : Z2 Đ Z2 cho bởi ϕpaq gpaq là một song ánh. Do đĩ fpxq là đa thức khơng hốn vị được modulo 2 và gpxq là đa thức hốn vị được modulo 2. 2.1.3 Ví dụ. Xét R Z4 - vành các số nguyên modulo 4. Cho fpxq 2 3x 2x2 và gpxq 3 2x x2. Ta cĩ fp0q 2, fp1q 3, fp2q 0 và fp3q 1. Vì thế ánh xạ ϕ : Z4 Đ Z4 cho bởi ϕpaq fpaq là song Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21 ánh. Ta cĩ gp0q 3, gp1q 2, gp2q 3 và gp3q 2. Vì thế ánh xạ ϕ : Z4 Đ Z4 cho bởi ϕpaq gpaq khơng là một song ánh. Do đĩ fpxq là đa thức hốn vị được modulo 4 và gpxq là đa thức khơng hốn vị được modulo 4. Một bài tốn rất tự nhiên đặt ra là: Cho trước đa thức fpxq n a0 a1x anx . Với điều kiện nào của các hệ số a0, . . . , an, đa thức fpxq là hốn vị được. Vì những ứng dụng của đa thức hốn vị được, cĩ rất nhiều người quan tâm đến bài tốn này. Tuy nhiên, cho đến nay, bài tốn này mới chỉ được giải quyết cho một số trường hợp đặc biệt. Bài tốn tổng quát vẫn đang là một vấn đề mở thách thức các nhà tốn học trên thế giới. Phần cịn lại của mục này là trình bày tính hốn vị được cho các đa thức bậc khơng quá 2 và đa thức dạng xn. Trước hết chúng ta đưa ra tiêu chuẩn hốn vị được của các đa thức bậc khơng quá 1. 2.1.4 Mệnh đề. Các phát biểu sau là đúng. (i) Trên một vành nhiều hơn 1 phần tử, mọi đa thức bậc khơng đều khơng hốn vị được. (ii) Trên một trường T hữu hạn, mọi đa thức bậc nhất là hốn vị được. Chứng minh. (i) Giả sử fpxq a là đa thức bậc 0 trên vành R cĩ nhiều hơn 1 phần tử. Khi đĩ fpbq a với mọi b P R. Do đĩ ánh xạ ϕ : R ÝĐ R xác định bởi ϕpbq fpbq khơng là tồn ánh. Vì thế fpxq khơng hốn vị được. (ii) Giả sử fpxq a bx P T rxs là đa thức bậc nhất. Khi đĩ b 0. Vì T là trường nên tồn tại phần tử b¡1 P T là nghịch đảo của b. Do đĩ với mỗi c P T , phương trình a bx c luơn cĩ nghiệm là x b¡1pc¡aq P T. Điều này chứng tỏ ánh xạ ϕ : T Đ T cho bởi ϕpαq fpαq a bα là Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
22 một tồn ánh. Do T là hữu hạn nên ϕ là song ánh. Vậy fpxq là hốn vị được trên T . Phần tiếp theo, chúng ta sẽ đưa ra tiêu chuẩn hốn vị được cho những đa thức dạng fpxq xn. Trước hết, ta cần hai bổ đề hỗ trợ sau. Nhắc lại rằng hàm Euler ϕ được định nghĩa trên tập các số nguyên dương như sau: ϕp1q 1 và ϕpnq là số các số nguyên dương nhỏ hơn n và nguyên tố cùng nhau với n. 2.1.5 Bổ đề. Cho G là một nhĩm cĩ cấp n. Khi đĩ G là nhĩm xyclic nếu và chỉ nếu với mỗi ước d của n tồn tại nhiều nhất một nhĩm con xyclic cấp d. Chứng minh. Giả sử G paq là xyclic. Cho d là ước của n. Đặt b an{d. Ta cĩ bd an e. Nếu bk e thì ank{d e. Do đĩ nk{d là bội của n. Suy ra k là bội của d. Theo Bổ đề 1.1.5, b cĩ cấp d. Đặt H pbq. Khi đĩ H là nhĩm xyclic cấp d. Giả sử H1 cũng là một nhĩm con xyclic cấp d của G. Viết H1 pcq và biểu diễn c at. Do H1 cĩ cấp d nên cd e. Suy ra atd e. Vì thế td là bội của n và do đĩ t là bội của n{d. Vì thế c at P H. Suy ra H1 H. Do H và H1 cùng cĩ số phần tử là d nên H H1. Vậy G cĩ duy nhất một nhĩm con xyclic cấp d. Ngược lại, giả sử mỗi ước d của n cĩ nhiều nhất một nhĩm con xyclic cấp d của G. Ta xét quan hệ trên G như sau: x y nếu và chỉ nếu pxq pyq. Dễ thấy là quan hệ tương đương trên G. Với mỗi x P G, kí hiệu clpxq là lớp tương đương của x. Khi đĩ ta cĩ clpxq ty P G | pxq pyqu ty P G | y là phần tử sinh của pxqu. Giả sử x cĩ cấp dx. Theo Định lí Lagrange, dx là ước của n. Theo Hệ quả 1.1.6, phần tử y xk là phần tử sinh của nhĩm xyclic pxq nếu và chỉ nếu pk, dxq 1. Vì thế clpxq cĩ đúng ϕpdxq phần tử với ϕ là hàm Euler. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23 Gọi clpx1q, . . . , clpxtq là tất cả lớp tương đương. Khi đĩ G clpxiq i1, ,t và clpxiq X clpxjq H với mọi i j. Do đĩ ta cĩ p q p q n ϕ dx1 ϕ dxt . Chú ý rằng dx1 , . . . , dxt đều là ước của n. Theo giả thiết, mỗi ước d của n chỉ cĩ đúng một nhĩm con xyclic cấp d nên các nhĩm px1q, , pxtq phải cĩ cấp đơi một khác nhau. Do đĩ dx1 , . . . , dxt là các số tự nhiên đơi một khác nhau. Bây giờ ta xét nhĩm Zn. Khi đĩ với mỗi ước d của n, tồn tại duy nhất một nhĩm con xyclic cấp d của . Do đĩ ta cĩ ° Z°n p q p q p q ¤ p q n d|n ϕ d . Vì thế n ϕ dx1 ϕ dxt d|n ϕ d n. Vì thế dx1 , . . . , dxt là tất cả các là ước của n. Đặc biệt, trong các ước P dxi , i 1, . . . , t, ắt cĩ một ước bằng n. Do đĩ tồn tại phần tử xi G cĩ p q cấp dxi n. Vì vậy G xi là xyclic. Nhắc lại rằng nếu T là một trường thì mỗi đa thức một biến bậc n với hệ số trong T cĩ nhiều nhất n nghiệm trong T . 2.1.6 Bổ đề. Cho T là trường hữu hạn. Đặt T ¦ T zt0u. Khi đĩ T ¦ là nhĩm xyclic với phép nhân. Chứng minh. Giả sử T cĩ q phần tử. Khi đĩ T ¦ cĩ q ¡ 1 phần tử. Trước hết ta chứng minh T ¦ là nhĩm với phép nhân. Cho a, b P T ¦. Khi đĩ a, b 0. Do đĩ tồn tại c, d P T sao cho ac 1 bd. Suy ra pabqpsdq 1 0. Vì thế ab 0, tức là ab P T ¦. Do đĩ phép nhân đĩng kín trong T ¦. Rõ ràng phép nhân trong T ¦ cĩ tính chất kết hợp. Do 1 0 nên 1 P T ¦. Cho a P T ¦. Khi đĩ a 0. Vì thế a cĩ nghịch đảo a¡1 P T. Rõ ràng a¡1 0. Suy ra a¡1 P T ¦. Vì thế mỗi phần tử trong T ¦ đều khả nghịch. Vậy, T ¦ là một nhĩm nhân với cấp là q ¡ 1. Tiếp theo ta chứng minh T ¦ là nhĩm xyclic. Giả sử d là một ước của q ¡ 1. Theo Bổ đề 2.1.5, để chứng minh T ¦ là xyclic, ta chỉ cần chứng Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
24 minh T ¦ cĩ nhiều nhất một nhĩm con xyclic cấp d. Giả sử H paq và H1 pbq là hai nhĩm con xyclic cấp d khác nhau của G. Khi đĩ ad 1 và bd 1. Vì thế các phần tử của H và H1 đều là nghiệm của đa thức xd ¡ 1 P T rxs. Vì H và H1 khác nhau nên H Y H1 cĩ ít nhất d 1 phần tử. Điều này chứng tỏ đa thức bậc d cĩ ít nhất d 1 nghiệm. Điều này là vơ lí. Bây giờ chúng ta trình bày tiêu chuẩn hốn vị được của đa thức xn. 2.1.7 Định lý. Trên một trường cĩ q phần tử, đa thức fpxq xn là hốn vị được nếu và chỉ nếu q ¡ 1 và n là nguyên tố cùng nhau. Chứng minh. Giả sử q ¡ 1 và n là nguyên tố cùng nhau. Khi đĩ tồn tại các số nguyên r, s sao cho 1 rpq ¡ 1q sn. Giả sử T là trường cĩ q phần tử. Với mỗi 0 c P T, ta cĩ c c1 crpq¡1qpcsqn. Ta khẳng định crpq¡1q 1. Thật vậy, đặt T ¦ T zt0u. Khi đĩ T ¦ là một nhĩm nhân với cấp là q ¡ 1 và nhĩm nhân này là xyclic. Theo Hệ quả 1.1.9 ta cĩ cq¡1 1. Suy ra crpq¡1q 1. Khẳng định được chứng minh. Do đĩ c pcsqn fpcsq. Khi c 0 thì ta luơn cĩ c pcqn fpcq. Suy ra ánh xạ ϕ : T Đ T cho bởi ϕpaq an là tồn ánh. Vì T là tập hữu hạn nên ϕ là song ánh. Do đĩ đa thức fpxq xn là hốn vị được. Giả sử xn là hốn vị được trên trường T cĩ q phần tử. Ta chứng minh q ¡ 1 và n nguyên tố cùng nhau. Gọi d là ước chúng lớn nhất của q ¡ 1 và n. Theo Bổ đề 2.1.6, T ¦ là nhĩm xyclic cấp q ¡ 1 với phép nhân. Giả sử T ¦ paq. Vì T ¦ cĩ cấp q ¡ 1 nên aq¡1 1 theo Hệ quả 1.1.9. Do đĩ paq¡1qn{d 1. Vì thế papq¡1q{dqn 1 1n. Đặt fpxq xn. Khi đĩ ta cĩ fpapq¡1q{dq fp1q. Do fpxq hốn vị được theo giả thiết nên ta cĩ apq¡1q{d 1. Do a cĩ cấp q ¡ 1 nên theo Bổ đề 1.1.5, pq ¡ 1q{d là bội của q ¡ 1. Vì thế d 1. Sử dụng Định lí 2.1.7, ta cĩ thể đặc trưng tính hốn vị được của các Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
25 đa thức bậc 2 như sau. 2.1.8 Mệnh đề. Đa thức fpxq ax2 bx c với a 0 là hốn vị được trên một trường hữu hạn T nếu và chỉ nếu b 0 và T cĩ đặc số 2. Chứng minh. Giả sử b 0 và T cĩ đặc số 2. Khi đĩ fpxq ax2 c. Giả sử T cĩ q phần tử. Do T cĩ đặc số 2 nên theo Mệnh đề 1.3.7, tồn tại số tự nhiên k sao cho q 2k. Do đĩ q ¡ 1 là số lẻ. Vì thế q ¡ 1 nguyên tố cùng nhau với 2. Theo Định lí 2.1.7, đa thức x2 là hốn vị được trên T . Giả sử fprq fpsq với r, s P T. Khi đĩ ar2 c as2 c. Suy ra ar2 as2. Do a 0 và T là trường nên a khả nghịch. Nhân hai vế với nghịch đảo của a ta được r2 s2. Vì đa thức x2 là hốn vị được trên T nên r s. Vậy fpxq là hốn vị được trên T . Ngược lại, giả sử fpxq là hốn vị được trên T . Trước hết ta chứng minh b 0. Giả sử b 0 và ta cần tìm mâu thuẫn. Do a 0 nên tồn tại phần tử a¡1 P T sao cho aa¡1 1. Vì thế ta cĩ fp¡a¡1bq ap¡a¡1bq2 bp¡a¡1bq c a¡1b2 ¡ a¡1b2 c c. Rõ ràng fp0q c. Do fpxq là hốn vị được trên T nên 0 a¡1b. Vì b 0 nên tồn tại b¡1 P T sao cho bb¡1 1. Nhân cả hai vế của đẳng thức 0 a¡1b với ab¡1 ta được 0 1, điều này là vơ lí. Vậy b 0. Tiếp theo ta chứng minh đặc số của T là 2. Do T là trường nên T cĩ đặc số 0 hoặc đặc số p nguyên tố. Nếu T cĩ đặc số 0 thì với mọi số tự nhiên n m ta cĩ pm ¡ nq1 0, tức là n.1 m.1. Vì thế T chứa một tập con tn.1 | n P Zu gồm vơ hạn phần tử, điều này là vơ lí. Vì thế T cĩ đặc số p nguyên tố. Ta cần chứng minh p 2. Nếu p 2 thì p là số nguyên tố lẻ. Do số phần tử của T là một lũy thừa của p nên q là số lẻ. Vì thế q ¡ 1 là số chẵn. Vì thế q ¡ 1 và 2 khơng nguyên tố cùng nhau. Theo Định lí 2.1.7, đa thức x2 khơng hốn vị được trên T . Vì thế tồn tại hai phần tử r s trong T sao cho r2 s2. Suy ra ar2 c as2 c, Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
26 tức là fprq fpsq, trong khi đĩ r s. Do đĩ fpxq khơng hốn vị được trên T , vơ lí. 2.2 Một số lớp đa thức hốn vị được trên một trường Mục này dành để trình bày tiêu chuẩn hốn vị được trên một trường của một số lớp đa thức. Trước hết, chúng ta trình bày một mở rộng của Mệnh đề 2.1.8. 2.2.1 Định lý. Cho T là trường cĩ q phần tử. Giả sử k, j là các số nguyên dương sao cho k ¡ j ¥ 1 và gcdpk ¡ j, q ¡ 1q 1. Khi đĩ đa thức fpxq axk bxj c với a 0 là hốn vị được trên T nếu và chỉ nếu b 0 và gcdpk, q ¡ 1q 1. Chứng minh. Giả sử fpxq hốn vị được trên T . Trước hết ta chứng minh b 0. Giả sử b 0 và ta cần tìm mâu thuẫn. Đặt gpxq xk a¡1bxj. Ta khẳng định gpxq hốn vị được trên T . Cho r, s P T sao cho gprq gpsq. Khi đĩ agprq c agpsq c. Suy ra fprq fpsq. Do fpxq hốn vị được trên T nên r s. Vì thế gpxq hốn vị được. Ta cĩ gpxq xjpxk¡j a¡1bq. Vì j ¥ 1 nên gp0q 0. Theo giả thiết, gcdpk ¡ j, q ¡ 1q 1. Do đĩ tồn tại các số nguyên m, n sao cho 1 mpk ¡jq npq ¡1q. Đặt d ¡a¡1b. Do b 0 và a 0 nên d P T ¦. Ta cĩ d d1 pdmqk¡jpdq¡1qn. Do T ¦ là nhĩm cấp q ¡ 1 với phép nhân và d P T ¦ nên dq¡1 1. Vì thế d pdmqk¡j. Suy ra gpdmq pdmqjppdmqk¡j ¡ dq pdmqjppdmqk¡j ¡ pdmqk¡jq 0. Do d 0 nên dm 0. Như vậy, gp0q gpdmq, trong khi đĩ dm 0. Điều này chứng tỏ gpxq khơng hốn vị được trên T , vơ lí. Vậy b 0. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
27 Tiếp theo, ta chứng minh gcdpk, q ¡ 1q 1. Do b 0 nên fpxq axk c. Đặt hpxq xk. Cho hprq hpsq với r, s P T. Khi đĩ rk sk. Suy ra ark c ask c, tức là fprq fpsq. Do fpxq hốn vị được trên T nên r s. Vì thế hpxq là hốn vị được trên T . Theo Định lí 2.1.7, gcdpk, q ¡ 1q 1. Ngược lại, giả sử b 0 và gcdpk, q ¡1q 1. Ta cần chứng minh fpxq hốn vị được trên T . Vì b 0 nên fpxq axk c. Do gcdpk, q ¡ 1q 1 nên theo Định lí 2.1.7, đa thức xk là hốn vị được trên T . Giả sử fprq fpsq. Khi đĩ ark c ask c. Suy ra rk sk. Do xk hốn vị được trên T nên r s. Vậy fpxq là hốn vị được trên T . Hệ quả sau đây cho ta một lớp các đa thức hốn vị được. 2.2.2 Hệ quả. Cho T là trường cĩ q phần tử. Giả sử q ¡ 1 khơng là bội của 3, 5, 7. Khi đĩ đa thức x8 bxt, với t là một số lẻ nhỏ hơn 8, là đa thức hốn vị được trên T nếu và chỉ nếu b 0 và T cĩ đặc số 2. Chứng minh. Xét đa thức fpxq xk axt với k 8. Vì t lẻ và t 8 nên k ¡ t 8 ¡ t P t7, 5, 3, 1u. Theo giả thiết, q ¡ 1 khơng là bội của 3, 5, 7. Do đĩ gcdpk ¡ t, q ¡ 1q 1. Theo Định lí 2.2.1, đa thức fpxq là hốn vị được trên T nếu và chỉ nếu a 0 và gcdpk, q ¡ 1q gcdp8, q ¡ 1q 1. Chú ý rằng gcdp8, q ¡ 1q 1 nếu và chỉ nếu q là số chẵn. Gọi p là đặc số của T . Khi đĩ p là số nguyên tố và q là một lũy thừa của p. Vì thế q là số chẵn nếu và chỉ nếu T cĩ đặc số nguyên tố chẵn, tức là đặc số của T bằng 2. Vậy, fpxq là hốn vị được trên T nếu và chỉ nếu a 0 và T cĩ đặc số 2. 2.2.3 Hệ quả. Cho T là trường cĩ q phần tử. Cho fpxq axk bxj c là một đa thức trên T , trong đĩ a 0, k ¡ j ¥ 1 và ¡ba¡1 là một lũy thừa bậc k ¡ j của một phần tử trong T . Khi đĩ fpxq là hốn vị được trên T nếu và chỉ nếu b 0 và gcdpk, q ¡ 1q 1. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
28 Chứng minh. Giả sử fpxq hốn vị được trên T . Theo giả thiết, tồn tại phần tử r P T sao cho ¡ba¡1 rk¡j. Đặt gpxq xk ba¡1xj. Ta khẳng định gpxq là hốn vị được trên T . Thật vậy, giả sử gpsq gps1q với s, s1 P T. Khi đĩ agpsq c agps1q c. Do đĩ fpsq fps1q. Vì fpxq hốn vị được trên T nên s s1. Do đĩ gpxq hốn vị được trên T . Ta cĩ gpxq xjpxk¡j ¡ p¡a¡1bqq xjpxk¡j ¡ rk¡jq. Do j ¥ 1 nên gp0q 0. Rõ ràng gprq 0. Vì gpxq hốn vị được nên r 0. Suy ra ¡a¡1b 0. Vì a 0 nên b 0. Do đĩ gpxq xk. Vì gpxq hốn vị được nên theo Định lí 2.1.7 ta cĩ gcdpk, q ¡ 1q 1. Ngược lại, giả sử b 0 và gcdpk, q ¡ 1q 1. Khi đĩ fpxq axk c. Do gcdpk, q ¡ 1q 1 nên theo Định lí 2.1.7 ta suy ra xk là hốn vị được trên T . Giả sử fprq fpsq với r, s P T. Khi đĩ ark c ask c. Suy ra rk sk. Do gpxq hốn vị được trên T nên r s. Vì thế fpxq là hốn vị được trên T . Trong phần cuối của mục này, chúng ta trình bày một số ví dụ về đa thức hốn vị được. 2.2.4 Ví dụ. Các phát biểu sau là đúng: 8 3 (i) Đa thức x ¡ 2x hốn vị được trên trường Z11. 8 (ii) Đa thức x 4x hốn vị được trên trường Z29. Chứng minh. Trong Hệ quả 2.2.2, với giả thiết T là trường cĩ q phần tử với q ¡ 1 khơng là bội của 3, 5, 7 thì đa thức fpxq x8 bxt, trong đĩ t lẻ nhỏ hơn 8, là hốn vị được trên T nếu và chỉ nếu b 0 và T cĩ đặc số 2. Ví dụ 2.2.4 chỉ ra rằng giả thiết q ¡ 1 khơng là bội của 3, 5, 7 là khơng thể bỏ đi được. Mặc dù đa thức x8 ¡ 2x3 trong mệnh đề (i) cĩ hệ số b ¡2 0 và đặc số của trường T Z11 là 11 2, nhưng đa Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
29 thức này vẫn hốn vị được trên T vì q ¡ 1 10 là một bội của 5. Thật vậy, xét đa thức fpxq x8 ¡ 2x3 ta cĩ fp0q 0, fp1q 10, fp2q 9, fp3q 6, fp4q 2, fp5q 7, fp6q 1, fp7q 5, fp8q 4, fp9q 8 và fp10q 3 . Vì thế ánh xạ ϕ : Z11 Đ Z11 cho bởi ϕpaq fpaq là song ánh. Do đĩ fpxq là đa thức hốn vị được modulo 11. Tương tự như vậy, mặc dù đa thức x8 4x trong mệnh đề (ii) cĩ hệ số b 4 0 và đặc số của trường T Z29 là 29 2, nhưng nĩ vẫn hốn vị được trên Z29. Sở dĩ như vậy vì q ¡ 1 28 là một bội của 7. Thật vậy, xét đa thức fpxq x8 4x ta cĩ fp0q 0, fp1q 5, fp2q 3, fp3q 19, fp4q 12, fp5q 15, fp6q 18, fp7q 6, fp8q 23, fp9q 27, fp10q 7, fp11q 2, fp12q 20, fp13q 10, fp14q 21, fp15q 25, fp16q 22, fp17q 11, fp18q 1, fp19q 14, fp20q 13, fp21q 17, fp22q 8, fp23q 28, fp24q 4, fp25q 9, fp26q 24, fp27q 16 và fp28q 26 . Vì thế ánh xạ ϕ : Z29 Đ Z29 cho bởi ϕpaq fpaq là song ánh. Do đĩ fpxq là đa thức hốn vị được modulo 29 2.2.5 Ví dụ. Xét đa thức fpxq x8 ¡ 3x. Khi đĩ (i) fpxq khơng hốn vị được trên trường Z5; (ii) fpxq khơng hốn vị được trên trường Z11; (iii) fpxq khơng hốn vị được trên trường Z13. Chứng minh. Ở ví dụ (i) đa thức fpxq x8 ¡ 3x cĩ q ¡ 1 4 khơng là bội của 3, 5, 7 nhưng b ¡3 0 và đặc số của trường T Z5 là 5 2. Đồng thời đa thức fpxq cĩ fp0q 0, fp1q 3, fp2q 0, fp3q 2 và fp4q 4. Vì thế ánh xạ ϕ : Z5 Đ Z5 cho bởi ϕpaq fpaq khơng là song ánh. Do đĩ fpxq là đa thức khơng hốn vị được modulo 5. Ở ví dụ (ii) đa thức fpxq x8 ¡ 3x cĩ q ¡ 1 10 là bội của 5 và cĩ b ¡3 0 và đặc số của trường T Z11 là 11 2. Đồng thời đa thức fpxq cĩ fp0q 0, fp1q 9, fp2q 8, fp3q 7,fp4q 8, fp5vq 0, fp6q 8, fp7q 10, fp8q 3, fp9q 9 và fp10q 4. Vì thế ánh xạ ϕ : Z11 Đ Z11 cho Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
30 bởi ϕpaq fpaq khơng là song ánh pfp2q fp4q fp6q 8q. Do đĩ fpxq là đa thức khơng hốn vị được modulo 11. Tương tự như vậy, ở ví dụ (iii) đa thức fpxq x8 ¡3x cĩ q ¡1 12 là bội của 3 và cĩ b ¡3 0 và đặc số của trường T Z13 là 13 2. Đồng thời đa thức fpxq cĩ fp0q fp3q 0, fp1q fp6q 11, fp2q fp8q 3, fp4q fp12q 4 và fp9q fp11q 2 Vì thế ánh xạ ϕ : Z13 Đ Z13 cho bởi ϕpaq fpaq khơng là song ánh. Do đĩ fpxq là đa thức khơng hốn vị được modulo 13 2.3 Đa thức hốn vị được modulo 2k Mục đích của mục này là trình bày tiêu chuẩn hốn vị được của đa thức với hệ số nguyên theo modulo 2k trong bài báo của Ronald Rivest [R]. Từ nay đến hết luận văn, ta luơn giả thiết fpxq là đa thức với hệ số nguyên. Nhắc lại rằng fpxq được gọi là hốn vị được modulo n nếu ánh xạ ϕ : Zn Đ Zn cho bởi ϕpaq fpaq là một song ánh. 2.3.1 Chú ý. Giả sử X là một tập hữu hạn. Khi đĩ một ánh xạ ϕ : X ÝĐ X là song ánh nếu và chỉ nếu nĩ là đơn ánh, nếu và chỉ nếu nĩ là tồn ánh. Do đĩ, đa thức fpxq hốn vị được modulo n nếu và chỉ nếu ánh xạ ϕ : Zn Đ Zn cho bởi ϕpaq fpaq là đơn ánh, nếu và chỉ nếu fpaq fpbq pmod nq kéo theo a b pmod nq với mọi a, b P Z. 2.3.2 Ví dụ. Cho fpxq 3 7x 8x2 3x3 4x4 và gpxq 2 2x 2x2. 3 Ta xét tính hốn vị được của fpxq và gpxq theo modulo 2 . Trong Z8rxs, đa thức fpxq cĩ dạng fpxq 3 7x 3x3 4x4. Ta cĩ fp0q 3, fp1q 1, fp2q 4, fp3q 7, fp4q 6, fp5q 2, fp6q 0 và fp7q 5. Vì thế ánh xạ ϕf : Z8 Đ Z8 cho bởi ϕf paq fpaq là song ánh. Ta cĩ gp0q 2, gp1q 6, gp2q 6, gp3q 2, gp4q 2, gp5q 6, gp6q 6 và gp7q 2. Vì thế ánh xạ ϕg : Z8 Đ Z8 cho bởi ϕgpaq gpaq khơng Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
31 là song ánh. Vậy, fpxq hốn vị được modulo 23 và gpxq khơng hốn vị được modulo 23. Trước hết chúng ta trình bày một tiêu chuẩn để đa thức fpxq là hốn vị được modulo 2. d 2.3.3 Bổ đề. Đa thức fpxq a0 a1x adx với hệ số nguyên là hốn vị được modulo 2 nếu và chỉ nếu a1 ad là lẻ. Chứng minh. Ta luơn cĩ fp0q a0 P Z2. Ta xét hai trường hợp. a) Giả sử a0 chẵn. Khi đĩ fp0q 0 P Z2. Vì thế, fpxq là hốn vị được modulo 2 nếu và chỉ nếu fp1q 1 P Z2. Ta cĩ fp1q a0 a1 ad. Vì a0 chẵn nên fp1q 1 P Z2 nếu và chỉ nếu a1 ad là lẻ. Do đĩ fpxq là hốn vị được modulo 2 nếu và chỉ nếu a1 ad là lẻ. b) Giả sử a0 lẻ. Khi đĩ fp0q 1 P Z2. Vì thế, fpxq là hốn vị được modulo 2 nếu và chỉ nếu fp1q 0 P Z2. Ta cĩ fp1q a0 a1 ad. Vì a0 lẻ nên fp1q 0 P Z2 nếu và chỉ nếu a1 ad là lẻ. Do đĩ fpxq là hốn vị được modulo 2 nếu và chỉ nếu a1 ad là lẻ. d 2.3.4 Bổ đề. Cho fpxq a0 a1x adx là đa thức với hệ số nguyên. Cho n 2m với m là một số nguyên chẵn. Giả sử fpxq là hốn vị được modulo n. Khi đĩ a1 là số lẻ. Chứng minh. Ta cĩ 0 m P Zn. Vì fpxq hốn vị được modulo n nên fp0q fpmq P Zn. Ta cĩ ¨ 2 d fpmq a0 a1m a2m adm . Do m là số chẵn nên m2 chia hết cho n. Do đĩ fpmq a0 a1m pmod nq. Giả sử a1 là chẵn. Vì m chẵn nên a1m 0 pmod nq. Do đĩ fpmq a0 pmod nq. Rõ ràng fp0q 0 pmod nq. Vì thế fpmq fp0q P Zn, trong Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
32 khi đĩ 0 m P Zn. Vì thế fpxq khơng hốn vị được modulo n, vơ lí. Vậy, a1 là số lẻ. 2.3.5 Ví dụ. Cho fpxq 2x 4x2 6x3. Ta xét tính hốn vị được của fpxq theo modulo n 8. Rõ ràng n 2.m, với m 4 là số chẵn. Ta cĩ a1 2 là số chẵn. Vì thế, theo Bổ đề 2.3.4, đa thức fpxq khơng hốn vị được modulo 8. Điều này cũng cĩ thể thấy dễ dàng từ định nghĩa đa thức hốn vị được. Trong Z8 ta cĩ fp0q 0, fp1q 4, fp2q 4, fp3q 4, fp4q 0, fp5q 4, fp6q 4 và fp7q 4. Vì thế ánh xạ ϕg : Z8 Đ Z8 cho bởi ϕf paq fpaq khơng là song ánh. d 2.3.6 Bổ đề. Cho fpxq a0 a1x adx là đa thức với hệ số nguyên. Cho n 2k với k ¡ 0 và cho m 2k¡1 n{2. Nếu fpxq hốn vị được modun n thì nĩ hốn vị được modulo m. Chứng minh. Giả sử fpxq hốn vị được modulo n. Với mỗi a P Z ta cĩ d fpa mq a0 a1px mq adpx mq d a0 a1a ada mt, với t là một số nguyên nào đĩ d a0 a1a ada pmod mq fpaq pmod mq. Giả sử fpxq khơng hốn vị được modulo m. Khi đĩ cĩ hai giá trị r s P Zm sao cho fprq fpsq P Zm. Suy ra r s pmod mq và fprq fpsq pmod mq. Vì vậy, theo tính chất vừa chứng minh ở trên ta cĩ fprq fpr mq fpsq fps mq pmod mq. Do đĩ, tồn tại các số nguyên t1, t2 sao cho fprq ¡ fpr mq mt1 và fprq ¡ fpsq mt2. Vì pr mq ¡ r khơng là bội của n 2m nên ta cĩ r m r P Zn. Do fpxq hốn vị được modulo n nên fpr mq fprq pmod nq. Do đĩ t1 lẻ. Theo giả thiết, r s pmod mq. Vì thế Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
33 r s pmod nq. Vì fpxq hốn vị được modulo n nên fprq fpsq pmod nq. Vì thế t2 là lẻ. Suy ra t2 ¡ t1 chẵn. Do đĩ ¨ ¨ fpr mq ¡ fpsq fprq ¡ fpsq ¡ fprq ¡ fpr mq mpt2 ¡ t1q 0 pmod nq. Do fpxq hốn vị được modulo n nên r m ¡ s 0 pmod nq. Do m là ước của n nên r m ¡ s 0 pmod mq. Vì thế r ¡ s 0 pmod mq. Điều này là vơ lí với cách chọn của r và s. Nhìn chung, bài tốn kiểm tra (theo định nghĩa) tính khơng hốn vị được của fpxq modulo 2k khi k lớn là rất khĩ. Vì thế, trong nhiều trường hợp ta cĩ thể sử dụng Bổ đề 2.3.6 để giải quyết bài tốn này. Dưới đây là một ví dụ minh họa. 2.3.7 Ví dụ. Cho đa thức fpxq 1 2x x2. Khi đĩ fpxq khơng hốn vị được modulo 128. Chứng minh. Trong vành Z8 ta cĩ fp0q 1, fp1q 4, fp2q 1, fp3q 0, fp4q 1, fp5q 4, fp6q 1. Đặc biệt, ta cĩ 0 2 P Z8, nhưng fp0q fp2q 1 P Z8. Vì thế ánh xạ ϕf : Z8 Đ Z8 cho bởi ϕf paq fpaq khơng là song ánh. Vì thế fpxq khơng hốn vị được modulo 8. Theo Bổ đề 2.3.6, fpxq khơng hốn vị được modulo 16. Tiếp tục áp dụng Bổ đề 2.3.6, ta suy ra fpxq khơng hốn vị được modulo 2k với mọi k ¥ 3. Đặc biệt, vì 128 là lũy thừa của 2 nên fpxq khơng hốn vị được modulo 128. d 2.3.8 Bổ đề. Cho fpxq a0 a1x adx là đa thức với hệ số nguyên. Cho n 2m. Giả sử fpxq hốn vị được modulo n. Khi đĩ fpa mq fpaq m pmod mq với mọi số nguyên a. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
34 Chứng minh. Cho a P Z. Theo chứng minh Bổ đề 2.3.6, tồn tại số nguyên t sao cho fpa mq ¡ fpaq mt. Vì n 2m nên pa mq ¡ a khơng là bội của n, tức là a m a P Zn. Do fpxq hốn vị được modulo n nên fpa mq fpaq P Zn. Do đĩ fpaq fpa mq pmod nq. Vì thế mt khơng là bội của n. Suy ra t là số lẻ. Vì thế fpa mq fpaq mt fpaq m pmod 2mq fpaq m pmod nq. d 2.3.9 Bổ đề. Cho fpxq a0 a1x adx là đa thức với hệ số nguyên. Cho n 2m với m là một số chẵn. Giả sử fpxq hốn vị được modulo m. Khi đĩ fpxq hốn vị được modulo n nếu và chỉ nếu a1 là số lẻ và a3 a5 a7 là số chẵn. Chứng minh. Do m là số chẵn nên m2 chia hết cho n 2m. Do đĩ với mỗi i 2, . . . , d và với mỗi số nguyên a ta cĩ pa mqi ai imai¡1 tm2 với số nguyên t nào đĩ ai imai¡1 pmod nq. Vì i ¥ 2 nên i ¡ 1 ¥ 1. Do đĩ nếu cĩ ít nhất một trong 3 số i, a, ai là i¡1 chẵn thì aiima là bội của n. Trong trường này ta cĩ i i aipa mq aia pmod nq. i¡1 Cịn nếu cả 3 số i, a, ai đều là số lẻ thì aipima q m pmod nq và do đĩ ta cĩ i i aipa mq aia m pmod nq. Bây giờ ta xét hai trường hợp. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
35 Trường hợp 1: a là số chẵn. Theo trên ta cĩ 2 d fpa mq a0 a1pa mq pa2a ada q fpaq a1m pmod nq. Trường hợp 2: a là số lẻ. Theo trên ta cĩ ¨ 2 4 fpa mq a0 a1pa mq a2a a4a 3 5 pa3a mq pa5a mq fpaq pa1 a3 a5 qm pmod nq. Bây giờ ta chứng minh bổ đề. Giả sử fpxq hốn vị được modulo n. Theo Bổ đề 2.3.4, hệ số a1 là lẻ. Chú ý rằng a m a pmod nq với mọi số nguyên a. Vì thế fpa mq fpaq pmod nq với mọi số nguyên a. Chọn a là một số lẻ (chẳng hạn a 1). Theo Trường hợp 2 ta cĩ fpa mq ¡ fpaq pa1 a3 a5 qm pmod nq. Do đĩ ta cĩ pa1 a3 a5 qm 0 pmod nq. Suy ra a1 a3 a5 phải là số lẻ. Vì a1 lẻ nên a3 a5 a7 là số chẵn. Ngược lại, giả sử a1 là số lẻ và a3 a5 a7 là số chẵn. Giả sử phản chứng rằng fpxq khơng hốn vị được modulo n. Khi đĩ tồn tại a b P Zn sao cho fpaq fpbq P Zn. Do đĩ cĩ hai số nguyên a b pmod nq sao cho fpaq fpbq pmod nq. Vì m là ước của n nên fpaq fpbq pmod mq. Theo giả thiết, fpxq hốn vị được modulo m, vì thế a b pmod mq. Do a b pmod nq và n 2m nên a ¡ b mt với t là một số lẻ. Vì thế cĩ một số nguyên t1 sao cho b a ¡ mt a m ¡ 2t1m a m pmod nq. Suy ra b a m P Zn. Vì fpaq fpbq pmod mq nên ta cĩ fpaq fpa mq pmod nq. Nếu a là số chẵn thì theo Trường hợp 1 ta cĩ fpa mq fpaq a1m pmod nq. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
36 Do đĩ a1m là bội của n. Suy ra a1 chẵn, điều này mâu thuẫn với giả thiết a1 lẻ. Do đĩ a là số lẻ. Theo Trường hợp 2 ta cĩ fpa mq fpaq pa1 a3 a5 qm pmod nq. Do đĩ pa1 a3 a5 qm là bội của n. Suy ra a1 a3 a5 là chẵn. Theo giả thiết a1 là số lẻ. Vì thế a3 a5 là số lẻ, điều này là mâu thuẫn với giả thiết a3 a5 chẵn. Vậy fpxq hốn vị được modulo n. Định lí sau đây là kết quả chính của mục này, và là một trong 3 kết quả chính của luận văn. d 2.3.10 Định lý. Cho fpxq a0 a1x adx là một đa thức với hệ số nguyên. Cho n 2k với k ¥ 2. Khi đĩ fpxq hốn vị được modulo n nếu và chỉ nếu a1 là số lẻ, a2 a4 a6 là số chẵn và a3 a5 a7 là số chẵn. k¡1 Chứng minh. Giả sử fpxq hốn vị được modulo n. Đặt m1 2 . Khi đĩ n 2m1. Do k ¥ 2 nên m1 là số chẵn. Do đĩ theo Bổ đề 2.3.4, hệ số a1 là số lẻ. Do fpxq hốn vị được modulo n 2m1 nên theo Bổ đề 2.3.6, đa thức fpxq hốn vị được modulo m1. Vì thế, áp dụng Bổ đề 2.3.9, ta cĩ a3 a5 a7 là số chẵn. Tiếp theo, ta khẳng định bằng quy nạp theo i 1, . . . , k ¡ 1 rằng fpxq là hốn vị được modulo 2k¡i. Với i 1, ta đã chứng minh ở phần k¡1 trên rằng fpxq hốn vị được modulo m1 2 , do đĩ khẳng định đúng với i 1. Giả sử kết quả đã đúng cho i ¡ 1 với i ¤ k ¡ 1, tức là fpxq k¡i 1 k¡i k¡i 1 hốn vị được modulo 2 . Đặt mi 2 và mi¡1 2 . Khi đĩ mi¡1 2mi. Do fpxq hốn vị được modulo mi¡1 nên theo Bổ đề 2.3.6, k¡i fpxq hốn vị được modulo mi 2 . Khẳng định được chứng minh. Với i k ¡ 1, từ khẳng định trên ta suy ra fpxq hốn vị được modulo Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
37 2. Do đĩ theo Bổ đề 2.3.3 ta cĩ a1 a2 a3 ad là số lẻ. Vì a1 lẻ nên pa2 a4 a6 q pa3 a5 a7 q là số chẵn. Do a3 a5 a7 là số chẵn nên a2 a4 a6 là số chẵn. Ngược lại, giả sử a1 là số lẻ, a2 a4 a6 là số chẵn và a3 a5 a7 là số chẵn. Ta cần chứng minh fpxq hốn vị được modulo n 2k. Ta chứng minh điều này bằng quy nạp theo k. Cho k 1. Vì a1 là số lẻ, a2 a4 a6 là số chẵn và a3 a5 a7 là số chẵn nên a1 a2 a3 ad là số lẻ. Do đĩ, theo Bổ đề 2.3.3 ta suy ra fpxq hốn vị được modulo 2 21. Vậy, kết quả đúng cho trường hợp k 1. Cho k ¡ 1 và giả thiết kết quả đã đúng cho trường hợp k ¡ 1, k¡1 tức là fpxq hốn vị được modulo 2 trong trường hợp a1 là số lẻ, a2 a4 a6 là số chẵn và a3 a5 a7 là số chẵn. Đặt k¡1 m 2 . Khi đĩ n 2m. Do k ¡ 1 nên m là số chẵn. Vì a1 là số lẻ, a3 a5 a7 là số chẵn và fpxq hốn vị được modulo m nên theo Bổ đề 2.3.9 ta suy ra fpxq hốn vị được modulo n. Phần cuối của mục này trình bày một số ví dụ về đa thức hốn vị được modulo 2k. 2.3.11 Ví dụ. Các đa thức sau là hốn vị được modulo 2k (i) ax bx2 với mọi số lẻ a và mọi số chẵn b. (ii) x x2 x4. (iii) 1 x x2 xd, trong đĩ d 1 pmod 4q. Chứng minh. (i) Ta cĩ a1 a lẻ, a2 b chẵn. Theo Định lí 2.3.10, ax bx2 hốn vị được modulo 2k. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
38 2 4 (ii) Ta cĩ a1 1 lẻ, a2 a4 2 chẵn. Theo Định lí 2.3.10, x x x hốn vị được modulo 2k. (iii) Từ giả thiết ta suy ra d là số lẻ. Ta cĩ a1 1 lẻ, a2 a4 ad¡1 pd ¡ 1q{2 và a3 a5 ad pd ¡ 1q{2. Do d 1 pmod 4q nên d ¡ 1 là bội của 4. Vì thế pd ¡ 1q{2 là số chẵn. Theo Theo Định lí 2.3.10, 1 x x2 xd hốn vị được modulo 2k. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
39 Kết luận Luận văn trình bày một số kết quả về đa thức hốn vị được trong hai bài báo: 1. R. Rivest, Permutation polynomials modulo 2w, Finite fields and their applications, 7 (2001), 287-292. 2. R. A. Mollin and C. Small, On permutation polynomials over finite fields, Inter. J. Math. and Math. Sciences, 10 (1987), 535-544. Nội dung chính của luận văn là: Trình bày một số kiến thức chuẩn bị về nhĩm, vành, trường, đa thức phục vụ chứng minh các kết quả chính ở Chương 2. Đưa ra tiêu chuẩn để đa thức dạng xn là hốn vị được trên một trường hữu hạn (Định lí 2.1.7). Từ đĩ suy ra tiêu chuẩn hốn vị được của đa thức bậc khơng quá hai. Chứng minh một điều kiện cần và đủ cho các đa thức dạng xk bxj c, trong đĩ k ¡ j ¥ 1 là hốn vị được trên một trường hữu hạn (Định lí 2.2.1). Từ đĩ thu được tính chất hốn vị được của một số đa thức đặc biệt. Giải quyết trọn vẹn bài tốn về tính hốn vị được modulo n cho các đa thức với hệ số nguyên trong trường hợp n là lũy thừa của 2 (Định lí 2.3.10). Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
40 Tài liệu tham khảo [C] Nguyễn Tự Cường, Đại số hiện đại, tập 1, NXB ĐHQGHN, 2001. [HT] Bùi Huy Hiền và Phan Dỗn Thoại, Bài tập Đại số và số học, Tập 2, NXB Giáo dục, 1986. [La] Ngơ Thúc Lanh, Đại số và số học, Tập 2, NXB Giáo dục, 1986. [LN] R. Lidl and H. Niedereiter, Finite Fields, Addison - Wesley, 1983 [LM1] R. Lidl and G. L. Mullen, When does a polynomial over a finite field permute the elements of the field? The American Math, Monthly, 3 (1988), 243-246 [LM2] R. Lidl and G. L. Mullen, When does a polynomial over a finite field permute the elements of the field? II. The American Math, Monthly, 1 (1993), 71-74 [MS] R. A. Mollin and C. Small, On permutation polynomials over finite fields, Inter. J. Math. and Math. Sciences, 10 (1986), 535- 544. [Riv] R. Rivest, Permutation polynomials modulo 2w, Finite fields and their applications, 7 (1999), 287-292. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên