Luận văn Ứng dụng của lí thuyết nhóm trong một số bài toán sơ cấp

ĐẠI HỌC THÁI NGUYấN ĐẠI HỌC KHOA HỌC ================ Nguyễn Tuyết Nga LUẬN VĂN THẠC SĨ TOÁN HỌC ỨNG DỤNG CỦA LÍ THUYẾT NHểM TRONG MỘT SỐ BÀI TOÁN SƠ CẤP Thỏi Nguyờn, năm 2009 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn ĐẠI HỌC THÁI NGUYấN ĐẠI HỌC KHOA HỌC ================ Nguyễn Tuyết Nga ỨNG DỤNG CỦA LÍ THUYẾT NHểM TRONG MỘT SỐ BÀI TOÁN SƠ CẤP Chuyờn ngành: Phương phỏp Toỏn sơ cấp Mó số: 60.46.40 Hướng dẫn: PGS.TS Lờ Thị Thanh Nhàn Thỏi Nguyờn, năm 2009 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Mục lục Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1 Kiến thức chuẩn bị về lí thuyết nhóm 5 1.1 Nhóm, nhóm xylic và nhóm con . . . . . . . . . . . . . . 5 1.2 Định lí Lagrange, đồng cấu nhóm . . . . . . . . . . . . . 7 1.3 Tác động của nhóm lên tập hợp . . . . . . . . . . . . . . 9 1.4 Công thức các lớp và Định lí Burnside . . . . . . . . . . 10 2 Một số ứng dụng vào số học 15 2.1 Một số ứng dụng đơn giản . . . . . . . . . . . . . . . . . 15 2.2 Một số ứng dụng của Định lí Lagrange . . . . . . . . . . 19 2.3 Ư´ng dụng của Công thức các lớp và Định lí Burnside . . 20 3 Ư´ng dụng vào tổ hợp 26 3.1 Nhóm đối xứng . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 Ư´ng dụng vào tổ hợp . . . . . . . . . . . . . . . . . . . 27 3.3 Một số ví dụ minh họa . . . . . . . . . . . . . . . . . . . 31 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . 41 1 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 2Lời cảm ơn Sau hơn nửa năm nghiên cứu miệt mài, luận văn thạc sĩ của tôi với đề tài nghiên cứu “Ư´ng dụng của lý thuyết nhóm trong một số bài toán sơ cấp” đG đ−ợc hoàn thành. Những kết qủa ban đầu mà tôi thu đ−ợc đó là nhờ sự h−ớng dẫn tận tình và nghiêm khắc của cô giáo PGS. TS Lê Thị Thanh Nhàn. Tôi xin đ−ợc bày tỏ lòng biết ơn sâu sắc đối với Cô. Tôi xin chân thành cảm ơn Ban Giám hiệu, phòng Đào tạo và Khoa Toán-Tin của Tr−ờng Đại học Khoa học - Đại học Thái Nguyên đG tạo mọi điều kiện thuận lợi cho tôi hoàn thành đề tài này trong thời gian qua. Đội ngũ cán bộ thuộc phòng Đào tạo và Khoa Toán - Tin đG hết lòng ủng hộ, giúp đỡ lớp cao học Khóa I chúng tôi với một thái độ nhiệt tình, thân thiện nhất. Điều này sẽ mGi là ấn t−ợng rất tốt đẹp trong lòng mỗi chúng tôi đối với nhà Tr−ờng. Tôi cũng rất tự hào rằng trong quá trình học tập đG đ−ợc Tr−ờng Đại học Khoa học - Đại học Thái Nguyên bố trí những nhà toán học hàng đầu Việt nam về lĩnh vực Ph−ơng pháp toán sơ cấp giảng dạy cho chúng tôi nh− GS Hà Huy Khoái, GS Nguyễn Minh Hà, GS Phan Huy Khải... Và cũng là lời cảm ơn chân thành của tôi tới bạn bè, những ng−ời thân đG luôn động viên, cổ vũ tôi trong suốt qúa trình nghiên cứu. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 3Lời nói đầu Lí thuyết nhóm là một trong những lĩnh vực nghiên cứu quan trọng của Đại số hiện đại. Lí thuyết này có những ứng dụng sâu sắc trong nhiều h−ớng khác nhau của toán học, vật lí... Đặc biệt, một số kĩ thuật trong lí thuyết nhóm đG đ−ợc sử dụng để mang lại những kết quả đẹp của toán sơ cấp. Chẳng hạn, tính giải đ−ợc của các đa thức đG đ−ợc giải quyết trọn vẹn bởi E. Galois thông qua việc sử dụng các kiến thức của lí thuyết nhóm phối hợp một cách tài tình với lí thuyết tr−ờng và đa thức. Trong luận văn này, chúng tôi khai thác một số ứng dụng của lí thuyết nhóm vào toán sơ cấp ở 2 lĩnh vực: Số học và Tổ hợp. Công cụ chủ yếu của lí thuyết nhóm đ−ợc vận dụng ở đây là Định lý Lagrange “Cấp và chỉ số của một nhóm con của một nhóm hữu hạn là −ớc của cấp của toàn nhóm” và Định lý Burnside “Nếu nhóm hữu hạn G tác động lên tập hữu hạn X thì số quỹ đạo của tác động là 1 (G : e) ∑ g∈G f(g), trong đó f(g) là số phần tử của X cố định qua tác động của g”. Luận văn đ−ợc trình bày trong 3 ch−ơng. Ch−ơng 1 là những kiến thức chuẩn bị về lý thuyết nhóm nhằm phục vụ cho 2 ch−ơng sau, bao gồm các khái niệm và tính chất cơ bản về nhóm, đồng cấu nhóm, nhóm đối xứng và tác động của nhóm lên tập hợp. Các kiến thức và thuật ngữ của Ch−ơng I đ−ợc tham khảo chủ yếu trong các cuốn sách về lý thuyết nhóm của J. Rotman [Rot] và J. F. Humphreys [Hum]. Ch−ơng 2 là một số ứng dụng vào số học. Một số kết quả ở các Tiết 2.1 và 2.2 là sự tổng hợp lại theo một chủ đề những ứng dụng đG biết của lí thuyết nhóm trong số học (xem 2.1.3, 2.1.4, 2.1.5, 2.2.1, 2.2.2), Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 4nh−ng cũng có những tính chất mà tác giả luận văn tự tìm tòi bằng hiểu biết của mình (xem 2.1.1, 2.1.2). Tiết 2.3, đ−ợc trình bày theo bài báo công bố năm 2005 của T. Evans và B. Holt [EH], chứng minh lại những công thức số học cổ điển bằng ph−ơng pháp sử dụng công thức các lớp và Định lý Burnside trong lí thuyết nhóm. Ch−ơng cuối của luận văn là những ứng dụng của lý thuyết nhóm vào một số bài toán tổ hợp. Thực chất, khi có lí thuyết nhóm soi vào, các bài toán tổ hợp này đG bớt phức tạp hơn, cách giải quyết nó cũng không còn là những mẹo mực hay bí ẩn dễ nhầm lẫn của Toán tổ hợp nữa, mà nó trở thành rõ ràng, hệ thống và dễ hiểu. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Ch−ơng 1 Kiến thức chuẩn bị về lí thuyết nhóm Mục đích của ch−ơng này là nhắc lại một số kiến thức về nhóm, định lí Lagrange, tác động của nhóm lên tập hợp, công thức các lớp và Định lí Burnside. Kiến thức này là cần thiết cho những ứng dụng giải một số bài toán sơ cấp đ−ợc trình bày trong Ch−ơng II và Ch−ơng III. Các kiến thức và thuật ngữ ở đây đ−ợc tham khảo trong các cuốn sách về lí thuyết nhóm [Ash], [Rot] và [Hum]. 1.1 Nhóm, nhóm xylic và nhóm con 1.1.1. Định nghĩa. Nhóm là một tập G cùng với một phép toán thoả mGn các điều kiện (i) Phép toán có tính kết hợp: a(bc) = (ab)c, ∀a, b, c ∈ G. (ii) G có đơn vị: ∃e ∈ G sao cho ex = xe = x, ∀x ∈ G. (iii) Mọi phần tử của G đều khả nghịch: Với mỗi x ∈ G, tồn tại x−1 ∈ G sao cho xx−1 = x−1x = e. Một nhóm G đ−ợc gọi là nhóm giao hoán (hay nhóm Abel) nếu phép toán là giao hoá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. • Một số ví dụ về nhóm. 5 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 6- Tập Z các số nguyên, tập Q các số hữu tỷ, tập R các số thực, tập C các số phức với phép cộng thông th−ờng đều là nhóm giao hoán cấp vô hạn. - Tập S(X) các song ánh từ một tập X đến chính nó với phép hợp thành các ánh xạ là một nhóm, gọi là nhóm đối xứng của X. Nếu X có n phần tử thì S(X) có cấp n! và nhóm này không giao hoán khi n ≥ 3. - Với mỗi số tự nhiên m ≥ 1, tập Zm các lớp thặng d− theo môđun m với phép cộng các lớp thặng d− là một nhóm giao hoán cấp m. Tập Z∗m các lớp thặng d− theo môđun m nguyên tố cùng nhau với m với phép nhân các lớp thặng d− là một nhóm giao hoán cấp ϕ(m), trong đó ϕ là hàm Euler. • Một số tính chất cơ sở: Cho G là một nhóm với đơn vị e. Khi đó - Phần tử đơn vị của G là duy nhất. - Phần tử nghịch đảo của mỗi phần tử của G là duy nhất. - Mọi phần tử của G đều chính quy, tức là thỏa mGn luật giản −ớc. 1.1.2. Đị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 ∈ H và a−1 ∈ H, ab ∈ H với mọi a, b ∈ H. 1.1.3. Định nghĩa. Một nhóm G đ−ợc gọi là xyclic nếu tồn tại a ∈ 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 G đ−ợc gọi là nhóm xyclic sinh bởi a và viết G = . Chú ý rằng nhóm con của nhóm xyclic là xyclic. Cho G là một nhóm và a ∈ G. Đặt = {an | n ∈ Z}. Khi đó 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 đ−ợc gọi là cấp của phần tử a. Dễ thấy rằng a có cấp vô hạn nếu và chỉ nếu an = 0 kéo theo n = 0 với mọi Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 7n ∈ Z. Hơn nữa, a có cấp n nếu và chỉ nếu n là số nguyên d−ơng bé nhất sao cho an = e. 1.1.4. Định nghĩa. Cho A là tập con của một nhóm G. Khi đó tồn tại những nhóm con của G chứa A, chẳng hạn G. Giao của tất cả các nhóm con của G chứa A là nhóm con nhỏ nhất của G chứa A. Nhóm con này đ−ợc gọi là nhóm con sinh bởi tập A và kí hiệu là . Rõ ràng nhóm con sinh bởi tập rỗng là {e}. Nếu A = ∅ thì = {a1a2 . . . an | n ∈ N, a1, . . . , an ∈ A ∪A −1}, trong đó A−1 = {x−1 | x ∈ A}. 1.2 Định lí Lagrange, đồng cấu nhóm 1.2.1. Định nghĩa. Cho H là một nhóm con của một nhóm G. Ta định nghĩa quan hệ ∼ trên G nh− sau: a ∼ b nếu và chỉ nếu ab−1 ∈ H với mọi a, b ∈ G. Dễ kiểm tra đ−ợc ∼ là một quan hệ t−ơng đ−ơng tren G. Với mỗi a ∈ G, gọi a là lớp t−ơng đ−ơng của a. Ta có a = {ha | h ∈ H} = Ha. Mỗi lớp t−ơng đ−ơng Ha đ−ợc gọi là một lớp ghép trái của H trong G. Tập th−ơng của G theo quan hệ t−ơng đ−ơng ∼ đ−ợc kí hiệu bởi G/H. Khi H chỉ có hữu hạn lớp ghép trái thì ta gọi chỉ số của H trong G, kí hiệu là (G : H), là số các lớp ghép trái của H. 1.2.2. Định lý. (Đị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 toàn nhóm. • Sau đây là một số hệ quả trực tiếp của Định lí Lagrange. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 8- Cho G là nhóm cấp n và a ∈ G. Khi đó cấp của a là −ớc của n. Hơn nữa, an = e. - Mỗi nhóm cấp nguyên tố đều là nhóm xylic sinh bởi một phần tử tùy ý khác đơn vị. - Mọi nhóm cấp
5 đều giao hoán. 1.2.3. Định nghĩa. Cho G là một nhóm. Một nhóm con H của G đ−ợc gọi là nhóm con chuẩn tắc nếu Ha = aH với mọi a ∈ G. Cho H là nhóm con chuẩn tắc của một nhóm G. Kí hiệu G/H là tập các lớp ghép trái của H trong G. Khi đó quy tắc nhân HaHb = Hab với mọi Ha,Hb ∈ G/H là một phép toán trên G/H, và cùng với phép toán này, G/H làm thành một nhóm. Nhóm G/H xác định nh− trên đ−ợc gọi là nhóm th−ơng của G theo nhóm con chuẩn tắc H. 1.2.4. Định nghĩa. Cho G và H là các nhóm. A´nh xạ f : G −→ H đ−ợc gọi là đồng cấu nhóm nếu f(xy) = f(x)f(y) với mọi x, y ∈ G. Một đồng cấu nhóm đ−ợc gọi là đơn cấu (toàn cấu, đẳng cấu) nếu nó là đơn ánh (toàn ánh, song ánh). Hai nhóm G và H đ−ợc gọi là đẳng cấu với nhau, viết là G ∼= H, nếu có một đẳng cấu giữa G và H. • Một số tính chất: - Hợp thành của hai đồng cấu nhóm là một đồng cấu nhóm. - Nếu f : G −→ H là đồng cấu nhóm thì f(x−1) = (f(x))−1 và f(e) = e với mọi x ∈ G. - Nếu f : G −→ H là đồng cấu nhóm, A là nhóm con của G và B là nhóm con của H thì f(A) là nhóm con của H và f−1(B) là nhóm con của G. Hơn nữa, nếu B là nhóm con chuẩn tắc thì f−1(B) là nhóm con chuẩn tắc. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 91.2.5. Định nghĩa. Giả sử f : G −→ H là đồng cấu nhóm. Khi đó tập Ker f = {x ∈ G | f(x) = e} là một nhóm con chuẩn tắc của G và đ−ợc gọi là hạt nhân của f . Tập Im f = f(G) là một nhóm con của H và đ−ợc gọi là ảnh của f . 1.2.6. Định lý. (Định lí đồng cấu nhóm). Cho f : G −→ H là đồng cấu nhóm. Khi đó G/Ker f ∼= Im f. 1.3 Tác động của nhóm lên tập hợp 1.3.1. Định nghĩa. Cho S là một tập hợp và G là một nhóm với e là đơn vị của G. Một tác động trái của G lên S là một ánh xạ G ì S −→ S sao cho nếu ta kí hiệu ảnh của phần tử (x, s) ∈ Gì S là xs thì ta có (i) x(ys) = (xy)s với mọi x, y ∈ G, s ∈ S. (ii) es = s với mọi s ∈ S. Hoàn toàn t−ơng tự, chúng ta có khái niệm tác động phải. Khi có một tác động trái từ G lên S thì ta nói S là một G−tập, và ảnh của phần tử (x, s) ∈ Gì S qua tác động này đ−ợc kí hiệu là xs hoặc x • s. Từ nay trở đi chúng ta chỉ xét các tác động trái, và để thuận tiện ta gọi chúng là các tác động. Ta thấy rằng nhóm G tác động lên tập S nếu và chỉ nếu với mỗi x ∈ G, có một ánh xạ từ S đến S cho ứng mỗi s ∈ S với phần tử kí hiệu là xs ∈ S sao cho x(ys) = (xy)s và es = s với mọi x, y ∈ G, s ∈ S. Ta gọi phần tử xs là tác động của x lên s. Với x ∈ G, ánh xạ cho ứng s ∈ S với xs ∈ S đ−ợc gọi là ánh xạ liên kết của x. • Một số ví dụ về tác động của nhóm lên tập hợp. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 10 - Cho G là nhóm. Khi đó G tác động lên chính nó bằng phép liên hợp nh− sau: Với x, a ∈ G, ta dùng kí hiệu x • a cho tác động của x lên a, và đặt x • a = xax−1. Ta gọi xax−1 là liên hợp của a bởi x. - Cho G là nhóm. Kí hiệu S là tập các tập con của G. Khi đó nhóm G tác động lên tập S bằng phép nhân nh− sau: Với x ∈ G và H ∈ S, ta dùng kí hiệu x •H cho tác động của x lên H, và đặt x •H = xH. - Cho G là nhóm và A là nhóm con của G. Nhóm con B của G đ−ợc gọi là liên hợp với A nếu tồn tại x ∈ G sao cho B = xAx−1. Chú ý rằng nếu B liên hợp với A và C liên hợp với B thì C liên hợp với A. Kí hiệu S là tập các nhóm con của G liên hợp với A. Khi đó G tác động lên S bằng cách liên hợp nh− sau: với mỗi x ∈ G,B ∈ S, đặt x •B = xBx−1. 1.4 Công thức các lớp và Định lí Burnside 1.4.1. Bổ đề. Cho G là nhóm và S là một G−tập. Với s ∈ S, đặt Gs = {a ∈ G | as = s}. Khi đó Gs là nhóm con của G. Chứng minh. Cho s ∈ S. Vì es = s nên e ∈ Gs. Cho x, y ∈ Gs. Khi đó xs = s và ys = s. Vì thế (xy)s = x(ys) = xs = s. Suy ra xy ∈ Gs. Cuối cùng, cho x ∈ Gs. Khi đó xs = s. Vì thế s = es = (x−1x)s = x−1(xs) = x−1s. Suy ra x−1 ∈ Gs. Vậy Gs là nhóm con của G. Nhóm con Gs định nghĩa trong Bổ đề 1.4.1 đ−ợc gọi là nhóm con đẳng h−ớng của G ứng với phần tử s. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 11 1.4.2. Định nghĩa. Cho G là nhóm, S là G−tập và s ∈ S. Đặt Gs = {xs | x ∈ G}. Khi đó Gs là bộ phận của S. Ta gọi Gs là quỹ đạo của s trong S. • Sau đây là một số ví dụ về nhóm con đẳng h−ớng và quỹ đạo. - Xét tác động chính quy của G lên chính nó: x • a = xa, với mọi x, a ∈ G. Với a ∈ G, kí hiệu Ga là quỹ đạo của a. Với mỗi y ∈ G ta có y = (ya−1)a ∈ Ga. Do đó Ga = G. Vì thế tác động này chỉ có 1 quỹ đạo, đó là G. Nhóm con đẳng h−ớng ứng với a là Ga = {x ∈ G : xa = a} = {e}. - Xét tác động của nhóm G lên chính nó bằng phép liên hợp: x • a = xax−1 với mọi x, a ∈ G. Với a ∈ G, quỹ đạo của a là Ga = {x • a | x ∈ G} = {xax−1 | x ∈ G}. Nhóm con đẳng h−ớng ứng với a là Ga = {x ∈ G | xax −1 = a} = {x ∈ G | xa = ax}. - Kí hiệu S là tập các nhóm con của một nhóm G. Xét tác động của nhóm G lên S bằng phép liên hợp: x •H = xHx−1 với mọi x ∈ G và mọi H ∈ S. Với H ∈ S, quỹ đạo của H là {xHx−1 | x ∈ G} - tập các nhóm con liên hợp với H; nhóm con đẳng h−ớng của H là GH = {x ∈ G | xH = Hx}. 1.4.3. Mệnh đề. Cho G là nhóm và S là G−tập. Khi đó (i) Gs = ∅ với mọi s ∈ S. (ii) S = ⋃ s∈S Gs. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 12 (iii) Gs = Gr hoặc Gs ∩Gr = ∅ với mọi s, r ∈ S. Chứng minh. (i), (ii). Vì s = es ∈ Gs nên Gs = ∅. Suy ra S = ⋃ s∈S Gs. (iii). Giả sử Gs∩Gr = ∅. Khi đó tồn tại x, y ∈ G sao cho xs = yr. Suy ra s = es = x−1xs = x−1yr. Cho as ∈ Gs. Ta có as = (ax−1y)r ∈ Gr. Do đó Gs ⊆ Gr. T−ơng tự Gr ⊆ Gs, và vì thế Gs = Gr. Mệnh đề 1.4.3 chỉ ra rằng tập các quỹ đạo trong S làm thành một phép phân hoạch trên S. 1.4.4. Định lý. (Công thức các lớp). Cho G là nhóm, S là G−tập và s ∈ S. Kí hiệu G/Gs là tập các lớp ghép trái của nhóm con đẳng h−ớng Gs. Khi đó t−ơng ứng f : G/Gs −→ Gs cho bởi f(xGs) = xs là một song ánh. Giả thiết thêm rằng S là một tập hữu hạn. Khi đó chỉ số của Gs chính là số phần tử của quỹ đạo Gs. Hơn nữa, nếu Gs1, . . . , Gst là các quỹ đạo đôi một rời nhau trong S thì Card(S) = Card ( t⋃ i=1 Gsi ) = t∑ i=1 (G : Gsi), (∗) trong đó Card(S) là số phần tử của S và (G : Gsi), i = 1, . . . , t, là chỉ số của nhóm con đẳng h−ớng Gsi. Chứng minh. Giả sử xGs = yGs ∈ G/Gs. Khi đó x−1y ∈ Gs. Suy ra x−1ys = s. Do đó ys = xs. Vì thế f là ánh xạ. Rõ ràng f là toàn ánh. Cho f(xGs) = f(yGs). Khi đó xs = ys. Do đó (x−1y)s = s. Suy ra x−1y ∈ Gs. Do đó xGs = yGs. Vì thế f là đơn ánh. Suy ra f là song ánh. Giả sử S là tập hữu hạn. Khi đó quỹ đạo Gs là tập hữu hạn với mọi s ∈ S. Do f là song ánh nên (G : Gs) = Card(Gs) với mọi s ∈ S. Vì thế công thức (*) đ−ợc chứng minh. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 13 1.4.5. Định lý. (Định lí Burnside). Giả sử một nhóm hữu hạn G tác động lên một tập hữu hạn X. Với mỗi g ∈ G, kí hiệu f(g) là số phần tử của X cố định qua tác động của g, tức là số phần tử của tập hợp {x ∈ X : gx = x}. Khi đó số quỹ đạo của tác động là 1 (G : e) ∑ g∈G f(g). Ng−ời ta gọi 1 (G : e) ∑ g∈G f(g) là số điểm cố định trung bình qua tác động của các phần tử của G. Theo định lí trên, số quỹ đạo của tác động chính là số điểm cố định trung bình. Chứng minh. Chúng ta dùng một kĩ thuật chuẩn tắc của tổ hợp gọi là “kĩ thuật tính toán theo 2 cách” để chứng minh. Gọi T là tập các cặp sắp thứ tự (g, x) sao cho g ∈ G, x ∈ X và gx = x. Với mỗi x ∈ X, số các phần tử g ∈ G sao cho (g, x) ∈ T chính là cấp của nhóm con đẳng h−ớng Gx của x. Vì thế ta có Card(T ) = ∑ x∈X (Gx : e), trong đó (Gx : e) là cấp của Gx. Với mỗi g ∈ G, số phần tử x ∈ X sao cho (g, x) ∈ T chính là f(g). Vì thế Card(T ) = ∑ g∈G f(g). Từ hai đẳng thức trên ta có∑ x∈X (Gx : e) (G : e) = 1 (G : e) ∑ g∈G f(g). Gọi t là số quỹ đạo. Gọi Gx1, . . . , Gxt là các quỹ đạo. Vì các quỹ đạo là đôi một rời nhau và X là hợp của các quỹ đạo nên ta có∑ x∈X (Gx : e) (G : e) = ∑ x∈Gx1 (Gx : e) (G : e) + . . .+ ∑ x∈Gxt (Gx : e) (G : e) . Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 14 Với mỗi i = 1, . . . , t, theo Định lí 1.4.4, tổng ∑ x∈Gxi (Gx : e) (G : e) bao gồm Card(Gxi) số hạng, mỗi số hạng đều bằng 1 Card(Gxi) . Vì thế ∑ x∈Gxi (Gx : e) (G : e) = 1 với mọi i = 1, . . . , t. Suy ra ∑ x∈X (Gx : e) (G : e) = t. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Ch−ơng 2 Một số ứng dụng vào số học 2.1 Một số ứng dụng đơn giản Nhận xét mở đầu. Giả sử p là số nguyên tố. Khi đó Z∗p = {1, . . . , p− 1} là một nhóm với phép nhân các lớp thặng d− theo môđun p. Vì nghịch đảo của hai phần tử khác nhau trong Z∗p là khác nhau nên ta luôn có {1 −1 , 2 −1 , . . . , (p− 1)−1} = {1, 2, . . . , p− 1}. Bây giờ ta áp dụng nhận xét này để chứng minh một số bài toán về số học liên quan đến số nguyên tố, đ−ợc thể hiện qua các mệnh đề sau. 2.1.1. Mệnh đề. Cho p > 2 là một số nguyên tố. Viết biểu thức 1 1 + 1 2 + . . .+ 1 p− 1 d−ới dạng phân số tối giản a/b. Khi đó p là −ớc của a. Chứng minh. Theo nhận xét trên, trong Zp ta có 1 1 + 1 2 + . . .+ 1 p− 1 = p−1∑ i=1 (i)−1 = p−1∑ i=1 i. Với mọi số tự nhiên n ≥ 1, bằng quy nạp theo n ta có 1 + 2 + . . .+ n = n(n+ 1) 2 . 15 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 16 Vì p > 2 là số nguyên tố nên p− 1 là số chẵn. Do đó p−1∑ i=1 i = p(p− 1) 2 là số nguyên chia hết cho p, tức là p−1∑ i=1 (i)−1 = p−1∑ i=1 i = 0 ∈ Zp. Vì thế p là −ớc của a. Cho k > 1 là số tự nhiên và p là số nguyên tố. Nếu p−1∑ i=1 ik chia hết cho p thì ta có kết quả t−ơng tự đối với tổng 1 1k + 1 2k + . . . + 1 (p− 1)k . Chẳng hạn, với k = 2 hoặc k = 3 ta có kết quả sau. 2.1.2. Mệnh đề. Cho p là số nguyên tố. Giả sử a b = 1 12 + 1 22 + . . .+ 1 (p− 1)2 a′ b′ = 1 13 + 1 23 + . . .+ 1 (p− 1)3 , trong đó a/b và a′/b′ là những phân số tối giản. Khi đó i) Nếu p > 3 thì p là −ớc của a. ii) Nếu p > 2 thì p là −ớc của a′. Chứng minh. (i) Theo nhận xét trên, trong Zp ta có 1 12 + 1 22 + . . .+ 1 (p− 1)2 = p−1∑ i=1 (i −1 )2 = p−1∑ i=1 i 2 . Với mọi số tự nhiên n ≥ 1, bằng quy nạp theo n ta có 12 + 22 + . . .+ n2 = n(n+ 1)(2n+ 1) 6 . Vì p > 3 là số nguyên tố nên p không là bội của 3 và cũng không là bội của 2. Do đó 12 + 22 + . . .+ (p− 1)2 = (p− 1)p(2p− 1) 6 là số nguyên chia hết cho p, tức là p−1∑ i=1 i 2 = 0 ∈ Zp. Do đó p là −ớc của a. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn 17 (ii) T−ơng tự ta có 1 13 + 1 23 + . . .+ 1 (p− 1)3 = p−1∑ i=1 (i −1 )3 = p−1∑ i=1 i 3 . Với mọi số tự nhiên n ≥ 1, bằng quy nạp theo n ta có 13 + 23 + . . .+ n3 = n2(n+ 1)2 4 . Vì p > 2 là số nguyên tố nên (p− 1)2 chia hết cho 4. Do đó 13 + 23 + . . .+ (p− 1)3 = (p− 1)2p2 4 là số nguyên chia hết cho p, tức là p−1∑ i=1 i 3 = 0 ∈ Zp. Vì thế p là −ớc của a′. Nhận xét trên có thể sử dụng để chứng minh kết quả sau đây. 2.1.3. Mệnh đề. (Định lí Wilson). Số tự nhiên p là số nguyên tố n