Tài liệu 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 ...
43 trang |
Chia sẻ: hunglv | Lượt xem: 1879 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu 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, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
ĐẠ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ếu và
chỉ nếu (p− 1)! ≡ −1 (mod p).
Chứng minh. Cho p nguyên tố. Nếu p = 2 thì (2 − 1)! ≡ −1 (mod 2).
Cho p > 2. Khi đó p lẻ. Trong nhóm nhân Z∗p = {1, . . . , p− 1}, nghịch
đảo của 1 là 1, nghịch đảo của p− 1 là p− 1. Hơn nữa, nghịch đảo của a
khác a với 1 < a < p− 1. Thật vậy, nếu ng−ợc lại ta có a2 ≡ 1 (mod p),
do đó p là −ớc của a2− 1 = (a− 1)(a+1), điều này là vô lí. Nh− vậy ta
có thể nhóm p − 3 phần tử {2, . . . , p− 2} của Z∗p thành (p − 3)/2 cặp,
mỗi cặp là nghịch đảo của nhau. Suy ra 2 . . . (p− 2) = 1 ∈ Z∗p. Do đó
(p− 1)! = 2 . . . (p− 2)(p− 1) ≡ 1.(p− 1) ≡ −1 (mod p).
Ng−ợc lại, giả sử (p − 1)! ≡ −1 (mod p). Giả sử p không nguyên tố.
Gọi a là một −ớc thực sự của p. Khi đó 1 < a < p. Do đó a là −ớc của
(p − 1)!. Vì (p − 1)! + 1 là bội của p nên nó là bội của a. Lại do a là
−ớc của (p− 1)! nên a là −ớc của 1, điều này là vô lí.
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
18
Chú ý rằng nhóm con của một nhóm xyclic là xyclic. Từ nhận xét
này ta có thể chứng minh kết quả sau đây.
2.1.4. Bổ đề. Cho a1, . . . , an là các số tự nhiên không đồng thời bằng
0. Giả sử d = gcd(a1, . . . , an). Khi đó tồn tại các số nguyên x1, . . . , xn
sao cho d = a1x1 + . . .+ anxn.
Chứng minh. Đặt H = {a1x1+ a2x2+ . . .+ anxn | xi ∈ Z, ∀i}. Khi đó
H là nhóm con của nhóm cộng Z. Vì Z xylic nên H là xyclic, tức là
H = tZ với t ∈ N. Ta khẳng định t = gcd(a1, . . . , an). Vì
ai = 0a1 + . . .+ 0ai−1 + 1ai + 0ai+1 + . . .+ 0an
nên ai ∈ H = tZ, suy ra ai chia hết cho t với mọi i = 1, . . . , n. Giả sử
r là một −ớc chung của a1, . . . , an. Vì t ∈ H nên t biểu diễn đ−ợc d−ới
dạng t = a1x1 + . . . + anxn, trong đó x1, . . . , xn ∈ Z. Do xi chia hết
cho t với mọi i = 1, . . . , n nên t chia hết cho r. Vậy t là −ớc chung lớn
nhất của các ai. Suy ra d = t. Do đó ta có kết quả.
2.1.5. Mệnh đề. (Định lí Bezout). Các số nguyên a1, . . . , an là nguyên
tố cùng nhau nếu và chỉ nếu tồn tại các số nguyên x1, . . . , xn sao cho
1 = a1x1 + . . .+ anxn.
Chứng minh. Đặt H = {a1x1+a2x2+ . . .+anxn | xi ∈ Z, ∀i}. Theo bổ
đề trên, H = dZ với d = gcd(a1, . . . , an). Nếu d = 1 thì H = Z. Do đó
1 ∈ H, vì thế 1 có biểu diễn 1 = a1x1 + . . .+ anxn với x1, . . . , xn ∈ Z.
Ng−ợc lại, nếu có biểu diễn 1 = a1x1 + . . .+ anxn thì 1 ∈ H = dZ. Suy
ra d = 1.
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
19
2.2 Một số ứng dụng của Định lí Lagrange
Trong tiết này, chúng ta sử dụng Định lí Lagrange phát biểu ở Ch−ơng I
để chứng minh một số kết quả trong số học.
2.2.1. Mệnh đề. (Định lí Fermat bé). Cho p là một số nguyên tố và a
là một số nguyên. Khi đó ap ≡ a (mod p).
Chứng minh. Xét nhóm nhân Z∗p các lớp thặng d− theo môđun p nguyên
tố cùng nhau với p. Nhóm này có cấp p − 1. Nếu a là bội của p thì ap
cũng là bội của p và do đó ap ≡ a (mod p). Tr−ờng hợp ng−ợc lại thì
gcd(a, p) = 1. Do đó a ∈ Z∗p. Trong nhóm Z
∗
p, áp dụng Định lí Lagrange
ta có ap−1 = 1, tức là ap−1 ≡ 1 (mod p). Suy ra ap ≡ a (mod p).
2.2.2. Mệnh đề. (Định lí Euler). Cho m > 1 là một số tự nhiên và a
là một số nguyên nguyên tố cùng nhau với m. Kí hiệu ϕ là hàm Euler.
Khi đó aϕ(m) ≡ 1 (modm).
Chứng minh. Xét nhóm nhân Z∗m các lớp thặng d− theo môđun m nguyên
tố cùng nhau với m. Nhóm này có cấp ϕ(m). Vì gcd(a,m) = 1 nên
a ∈ Z∗m. Trong nhóm Z
∗
m, áp dụng Định lí Lagrange ta có a
ϕ(m) = 1, tức
là aϕ(m) ≡ 1 (modm).
Cho G = (a) là nhóm xyclic cấp n. Khi đó phần tử ak là phần tử
sinh của G nếu và chỉ nếu gcd(n, k) = 1. Vì thế G có đúng ϕ(n) phần
tử sinh, trong đó ϕ là hàm Euler. Hơn nữa, nếu d là một −ớc của n thì G
có duy nhất một nhóm con cấp d, đó là nhóm con sinh bởi phần tử an/d.
A´p dụng Định lí Lagrange kết hợp với nhận xét này, ta có “đồng nhất
Euler” sau đây.
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
20
2.2.3. Mệnh đề. Gọi ϕ là hàm Euler. Nếu n > 0 là một số nguyên thì
n =
∑
d|n
ϕ(d).
Chứng minh. Chọn G là một nhóm xyclic cấp n, chẳng hạn G là nhóm
Zn với phép cộng các lớp thặng d− theo môđun n. Xét quan hệ trên G
cho bởi x ∼ y nếu và chỉ nếu các nhóm con xylic sinh bởi x và y là nh−
nhau. Dễ thấy ∼ là quan hệ t−ơng đ−ơng trên G. Kí hiệu cl(x) là lớp
t−ơng đ−ơng của phần tử x ∈ G. Khi đó
cl(x) = {y ∈ G : (y) = (x)}
= {y ∈ G : y là phần tử sinh của (x)}.
Giả sử cấp của x là d. Theo Định lí Lagrange, d là −ớc của n. Từ nhận
xét trên, mỗi phần tử y = xk là phần tử sinh của nhóm con (x) nếu và
chỉ nếu (k, d) = 1. Vì thế cl(x) gồm đúng ϕ(d) phần tử. Gọi x1, . . . , xk
là các đại diện của các lớp t−ơng đ−ơng rời nhau. Khi đó G là hợp của
k tập rời nhau
G = cl(x1) ∪ cl(x2) ∪ . . . ∪ cl(xk).
Do G là nhóm xyclic nên theo nhận xét trên, mỗi −ớc d của n có duy
nhất một nhóm con xyclic cấp d của G. Suy ra n có đúng k −ớc, mỗi −ớc
là cấp của một và chỉ một nhóm (xi) nào đó. Vì thế n =
∑
d|n
ϕ(d).
2.3 Ư´ng dụng của Công thức các lớp và Định lí Burnside
Định lí 2.3.1 và Định lí 2.3.2 đ−ợc trình bày dựa vào bài báo năm 2005
của Tyler J. Evans và Benjamin V. Holt [EH].
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
21
Kí hiệu à là hàm M
..
obius, tức là à(1) = 1 và với n = pα11 . . . p
αk
k
là sự phân tích tiêu chuẩn của số tự nhiên n thì à(n) = (−1)k nếu
α1 = . . . = αk = 1 và à(n) = 0 nếu tồn tại i sao cho αi > 1. Chú ý
rằng nếu f(n) và g(n) là các hàm số học sao cho g(n) =
∑
d|n
f(d) thì
f(n) =
∑
d/n
à(n/d) g(d).
Định lí sau đây là một kết quả cổ điển của lí thuyết số, đ−ợc viết
trong cuốn sách “History of the Theory Numbers” năm 1919 của L. E.
Dickson. Trong luận văn này, chúng ta đ−a ra một chứng minh khác bằng
ph−ơng pháp sử dụng tác động nhóm lên tập hợp và Công thức các lớp.
2.3.1. Định lý. Với mọi số nguyên d−ơng n và k ta có∑
d|n
à(n/d) kd ≡ 0 (modn).
Chứng minh. Hiển nhiên định lí đúng với n = 1. Cho n > 1. Xét hàm
số phức h : C −→ C cho bởi h(z) = zk. Với mỗi n > 1, đặt
Pn = {z ∈ C | n là số nguyên d−ơng bé nhất để h
n(z) = z}.
Cho thuận tiện, với mỗi tập hợp hữu hạn A, kí hiệu | A | là số phần tử
của A. Tr−ớc hết ta khẳng định rằng n là −ớc của | Pn |. Thật vậy, cho
k = 1. Khi đó với mỗi z ∈ C, số nguyên d−ơng t bé nhất để ht(z) = z
là số nguyên d−ơng t bé nhất để z1
t
= z, và số này chính là 1. Vì n > 1
nên với mỗi z ∈ C cho tr−ớc, n không thể là số nguyên d−ơng bé nhất
thoả mGn tính chất hn(z) = z. Vì thế tập
Pn = {z ∈ C | n là số nguyên d−ơng bé nhất để h
n(z) = z}
là tập rỗng, tức là | Pn |= 0, khẳng định là đúng trong tr−ờng hợp k = 1.
Cho k > 1. Giả sử z ∈ Pn. Khi đó n là số nguyên d−ơng bé nhất để
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
22
hn(z) = zk
n
= z. Từ đó, ta có thể chỉ ra rằng n là số nguyên d−ơng bé
nhất để
hn(zk
a
) = (zk
a
)k
n
= (zk
n
)k
a
= zk
a
,
tức là zk
a
∈ Pn với mọi số tự nhiên a với 0 a < n. Vì thế ta có tác
động của nhóm cộng Zn vào tập Pn cho bởi a • z = zk
a
với mọi a ∈ Zn
và mọi z ∈ Pn. Với z ∈ Pn bất kì, n là số nguyên d−ơng bé nhất để
zk
n
= z. Vì thế nhóm con đẳng h−ớng của z là
{a ∈ Zn | a • z = z} = {a ∈ Zn | 0 a < n, z
ka = z}
= {0}.
Do đó chỉ số của nhóm con đẳng h−ớng của z là n. Theo Công thức các
lớp, số phần tử của quỹ đạo của z là n. Vì Pn là hợp của các quỹ đạo
rời nhau, mỗi quỹ đạo đều có n phần tử nên n là −ớc của | Pn |, trong
đó | Pn | là số phần tử của Pn. Khẳng định đ−ợc chứng minh.
Tiếp theo ta tính | Pn | theo k và n. Với mỗi số nguyên d−ơng n, đặt
Xn = {z ∈ C | h
n(z) = z} = {z ∈ C | zk
n
= z}.
Rõ ràng Xn gồm đúng kn phần tử. Hơn nữa, Xn =
⋃
d|n
Pd và nếu d1 = d2
là các −ớc nguyên d−ơng của n thì Pd1∩Pd2 = ∅. Vì thế k
n =
∑
d|n
| Pd | .
Đặt f(n) =| Pn | và g(n) = kn. Khi đó g(n) =
∑
d|n
f(n). Suy ra
| Pn |= f(n) =
∑
d|n
à(n/d) g(d) =
∑
d|n
à(n/d) kd.
Theo khẳng định trên, n là −ớc của
∑
d|n
à(n/d) kd.
Định lí sau đây là một kết quả cổ điển hơn của lí thuyết số, đ−ợc
viết trong bài báo của P. A. MacMahon “Applications of the theory of
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
23
permutations in circular procession to the theory of numbers”, đăng trên
tạp chí Proc. London Math. Soc., năm 1891. Trong luận văn này, chúng
ta đ−a ra một chứng minh khác bằng việc sử dụng Định lí Burnside.
2.3.2. Định lý. Với mọi số nguyên d−ơng n và k ta có∑
d|n
ϕ(n/d) kd ≡ 0 (modn).
Chứng minh. Với mỗi số nguyên d−ơng n, đặt
Xn = {z ∈ C | h
n(z) = z} = {z ∈ C | zk
n
= z}.
Dễ thấy rằng quy tắc Zn ì Xn −→ Xn cho bởi a • z = zk
a
là một tác
động của nhóm cộng Zn lên tập Xn. Ta sẽ sử dụng Định lí Burnside đối
với tác động này để chứng minh định lí. Cho z ∈ Xn và a là số tự nhiên
với 0 a < n. Ta dễ kiểm tra đ−ợc zk
a
= z nếu và chỉ nếu zk
gcd(a,n)
= z,
trong đó gcd(a, n) là −ớc chung lớn nhất của a và n. Với a, b ∈ Zn, tập
các điểm cố định qua tác động của a là
{z ∈ Xn | a • z = z} = {z ∈ Xn | z
ka = z}
= {z ∈ Xn | z
kgcd(a,n) = z}.
Do đó số phần tử cố định qua tác động của a ∈ Zn là kd với d = gcd(a, n).
T−ơng tự, tập các điểm cố định qua tác động của b là
{z ∈ Xn | b • z = z} = {z ∈ Xn | z
kgcd(b,n) = z}.
Vì thế nếu gcd(a, n) = gcd(b, n) thì tập các điểm cố định qua tác động
của a và của b là nh− nhau. Hơn nữa, với d là một −ớc nguyên d−ơng
của n thì có đúng ϕ(n/d) số tự nhiên j ∈ {1, . . . , n} với gcd(j, n) = d.
Vì thế, với mỗi −ớc tự nhiên d của n, có đúng ϕ(n/d) phần tử của Zn
có −ớc chung lớn nhất với n bằng d và có cùng tập điểm cố định qua tác
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
24
động của mỗi phần tử trong chúng. Mặt khác, ta thấy rằng nhóm Zn là
hợp rời nhau của các tập Yd, trong đó
Yd = {a ∈ Zn | (a, n) = d},
và hợp đ−ợc lấy theo các chỉ số d là −ớc nguyên d−ơng của n. Bây giờ
áp dụng Định lí Burnside. Gọi r là số quỹ đạo rời nhau của tác động.
Kí hiệu Xan là tập các điểm cố định qua tác động của phần tử a. Khi đó
r =
1
| Zn |
∑
a∈Zn
| Xan |=
1
n
(∑
d|n
ϕ(n/d) kd
)
.
Vì r là số quỹ đạo của tác động nên r ∈ N. Do đó n là −ớc của∑
d|n
ϕ(n/d) kd, định lí đ−ợc chứng minh.
2.3.3. Chú ý. A´p dụng Định lí 2.3.2 cho tr−ờng hợp n = p là một số
nguyên tố thì ta nhận lại Định lí Fermat bé (xem Mệnh đề 2.2.1). Thật
vậy, theo Định lí 2.3.2, p là −ớc của ϕ(p) k1 + ϕ(1) kp = (p− 1)k+ kp.
Do đó kp ≡ k (mod p). A´p dụng chứng minh Định lí 2.3.2 cho tr−ờng
hợp k = 1 ta nhận lại đ−ợc “Đồng nhất Euler” trong Mệnh đề 2.2.3. Thật
vậy, khi k = 1 thì số quỹ đạo là 1. Vì thế ta có 1 =
1
n
(∑
d|n
ϕ(d) 1n/d
)
.
Suy ra n =
∑
d|n
ϕ(d).
Còn rất nhiều những ứng dụng khác của Lí thuyết nhóm trong việc
chứng minh lại những kết quả cổ điển của lí thuyết số (không đ−ợc trình
bày trong bản luận văn với khuôn khổ nhỏ bé này). Ng−ời ta cũng dùng
những kiến thức về Lí thuyết nhóm để đ−a ra những kết quả mới về số
học. Chẳng hạn, trong cuốn sách về lí thuyết nhóm của D. Surowski
[Sur], ông đG trình bày những kết quả đẹp của lí thuyết số (thể hiện trong
2 mệnh đề d−ới đây) mà chứng minh của chúng chỉ cần dùng đến Định
lí Burnside.
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
25
2.3.4. Mệnh đề. Cho x, n là các số nguyên với x ≥ 0 và n > 0. Khi đó
n−1∑
a=0
x(a,n) ≡ 0 (modn).
2.3.5. Mệnh đề. Cho n > 0 là một số nguyên. Kí hiệu d(n) là số các
−ớc của n. Kí hiệu ϕ là hàm Euler. Khi đó
n−1∑
a=0
(a,n)=1
(a− 1, n) = ϕ(n)d(n).
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
Ch−ơng 3
Ư´ng dụng vào tổ hợp
3.1 Nhóm đối xứng
Giả sử X có n phần tử. Khi đó nhóm đối xứng của X đ−ợc kí hiệu bởi
Sn. Chú ý rằng cấp của Sn là n!, và mỗi phần tử của Sn có thể đồng nhất
với một song ánh từ tập {1, 2, . . . , n} đến chính nó. Ta biểu diễn phần
tử s ∈ Sn d−ới dạng s =
(
1 2 . . . n
a1 a2 . . . an
)
, trong đó s(i) = ai với mọi
i = 1, . . . , n.
Sau đây là một số tính chất cơ sở của nhóm đối xứng Sn.
3.1.1. Bổ đề. Nhóm đối xứng Sn không giao hoán khi n ≥ 3.
Chứng minh. Cho n ≥ 3. Chọn s, r ∈ Sn là các ánh xạ cho bởi s(1) = 2,
s(2) = 1, s(a) = a với mọi a ≥ 3; r(1) = 1, r(2) = 3, r(3) = 2,
r(a) = a với mọi a ≥ 4. Khi đó rs(1) = 3 và sr(1) = 2. Điều này chứng
tỏ rs = sr. Do đó Sn không giao hoán.
3.1.2. Định nghĩa. Phép thế s ∈ Sn đ−ợc gọi là xích độ dài k nếu có
các số a1, . . . , ak ∈ {1, 2, . . . , n} sao cho s(a1) = a2, . . . , s(ak−1) =
ak, s(ak) = a1, và s(a) = a với mọi a /∈ {a1, . . . , ak}. Khi đó ta viết
s = (a1, a2, . . . , ak). Tập {a1, . . . , ak} đ−ợc gọi là tập nền của xích s.
Hai xích s, s′ ∈ Sn đ−ợc gọi là độc lập nếu các tập nền của chúng rời
26
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
27
nhau. Ta quy −ớc ánh xạ đồng nhất e là xích có độ dài 1 với tập nền
gồm một phần tử tuỳ ý.
3.1.3. Mệnh đề. Mỗi phép thế s ∈ Sn đều viết đ−ợc thành tích những
xích độc lập.
3.1.4. Chú ý. Cho s ∈ Sn. Giả sử s = s1 . . . st là sự phân tích của s
thành tích những xích độc lập. Nếu ta yêu cầu sự phân tích này có tính
chất a1 < a2 < . . . < at, trong đó ai là phần tử bé nhất trong tập nền
của si với mọi i = 1, . . . , t, thì rõ ràng sự phân tích nh− thế của s là duy
nhất nếu không kể đến các nhân tử là các xích có độ dài 1.
• Một số ví dụ.
- Các phần tử của nhóm đối xứng S3 đ−ợc biểu diễn nh− sau
S3 = {e, (1, 2, 3), (1, 3, 2), (1, 2), (1, 3), (2, 3)}.
- Trong nhóm đối xứng S8, ta có(
12345678
87231456
)
= (18643275);
(
12345678
25671348
)
= (125)(36)(47).
3.2 Ư´ng dụng vào tổ hợp
Tr−ớc khi trình bày một ứng dụng vào tổ hợp, chúng ta nghiên cứu
nhóm nhị diện của một đa giác đều.
Xét một đa giác đều n cạnh, tâm O và các đỉnh 1, 2, . . . , n sắp thứ
tự ng−ợc chiều kim đồng hồ. Kí hiệu Sn là nhóm các phép thế của tập
đỉnh {1, 2, . . . , n}. Nhóm nhị diện D2n là nhóm con của Sn sinh bởi hai
phần tử R và T, trong đó R là phép quay tâm O ng−ợc chiều kim đồng
hồ với góc quay
3600
n
, và T là phép đối xứng qua đ−ờng thẳng nối tâm
O với một đỉnh (chẳng hạn đỉnh 1). Nếu kí hiệu I là ánh xạ đồng nhất
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
28
thì nhóm nhị diện D2n gồm đúng 2n phép đẳng cự của đa giác, trong
đó có n phép quay I , R, R2, . . . , Rn−1 và n phép đối xứng T,RT, . . . ,
Rn−1T. Nếu n lẻ thì mỗi phép đối xứng đ−ợc xác định bởi đ−ờng thẳng
nối tâm O với một đỉnh (đi qua trung điểm của cạnh đối diện với đỉnh
đó). Nếu n chẵn thì n/2 phép đối xứng đ−ợc xác định bởi n/2 đ−ờng
thẳng, mỗi đ−ờng nối hai đỉnh đối diện nhau (đ−ờng thẳng này đi qua
tâm O); và n/2 phép đối xứng đ−ợc xác định bởi n/2 đ−ờng thẳng, mỗi
đ−ờng nối hai trung điểm của hai cạnh đối diện nhau (đ−ờng thẳng này
cũng qua tâm O).
3.2.1. Ví dụ. Để giảm bớt sự trừu t−ợng, ta làm việc với hình ngũ giác
đều có các đỉnh là 1, 2, 3, 4, 5 sắp thứ tự ng−ợc chiều kim đồng hồ. Nhóm
nhị diện D10 sinh bởi hai phần tử R,T trong đó R là phép quay tâm O
ng−ợc chiều kim đồng hồ với góc quay 720, và T là phép đối xứng qua
đ−ờng thẳng nối tâm O với đỉnh 1. Ta có thể viết T = (2, 5)(3, 4) và
R = (1, 2, 3, 4, 5), vì thế RT = (1, 2)(3, 5) là phép đối xứng qua đ−ờng
thẳng nối tâm O với đỉnh 4.
3.2.2. Ví dụ. Xét một lục giác đều với các đỉnh là 1, 2, 3, 4, 5, 6 sắp
thứ tự ng−ợc chiều kim đồng hồ. Nếu R là phép quay 600 và T là
phép đối xứng qua đ−ờng thẳng nối hai đỉnh 1, 4 thì nhóm nhị diện D12
gồm 12 phần tử sau: I , R = (1, 2, 3, 4, 5, 6), R2 = (1, 3, 5)(2, 4, 6),
R3 = (1, 4)(2, 5)(3, 6), R4 = (1, 5, 3)(2, 6, 4), R5 = (1, 6, 5, 4, 3, 2),
T = (2, 6)(3, 5), RT = (1, 2)(3, 6)(4, 5), R2T = (1, 3)(4, 6), R3T =
(1, 4)(2, 3)(5, 6), R4T = (1, 5)(2, 4), R5T = (1, 6)(2, 5)(3, 4).
3.2.3. Chú ý. Giả sử rằng, với k mầu cho sẵn, chúng ta tô màu các đỉnh
của hình lục giác trong Ví dụ 3.2.2 (không yêu cầu phải dùng tất cả các
mầu). Thế thì có bao nhiêu cách tô màu? Vì mỗi đỉnh đều có k cách
chọn mầu, nên câu trả lời theo logic là k6 cách tô. Tuy nhiên, câu trả
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
29
lời này không mô tả chính xác thực tế. Thật vậy, giả sử chúng ta có hai
mầu, mầu vàng (Y) và mầu xanh da trời (B). Khi đó qua phép đẳng cự
RT trong Ví dụ 3.2.2, cách tô mầu
C1 =
(
1 2 3 4 5 6
B B Y Y Y B
)
biến thành cách tô màu
C2 =
(
1 2 3 4 5 6
B B B Y Y Y
)
,
(vì qua RT = (1, 2)(3, 6)(4, 5), đỉnh 3 chuyển đến chỗ mà tr−ớc đó là
đỉnh 6 nên truyền mầu (Y) sang đỉnh 6, đỉnh 6 chuyển đến chỗ mà tr−ớc
đó là đỉnh 3 nên truyền mầu (B) sang đỉnh 3, còn các đỉnh 1, 2 cùng
có màu (B); các đỉnh 4, 5 cùng có mầu (Y) nên qua RT chúng vẫn giữ
nguyên màu). Theo tính toán logic thì C1 và C2 là 2 cách tô màu khác
nhau. Tuy nhiên, thử hình dung chúng ta có 2 cái vòng cứng hình lục
giác đều, một cái đ−ợc tạo mầu nh− C1 và cái kia đ−ợc tạo mầu nh− C2.
Nếu hai cái vòng cùng đặt trên một chiếc bàn thì sẽ khó lập luận đ−ợc
chúng có màu khác nhau, bởi vì cái vòng này sẽ có màu giống đúc cái
vòng kia khi ta lật úp nó rồi quay nó. Vì thế, trong thực tế, hai cách tô
màu (trang trí) C1 và C2 nên đ−ợc xem là nh− nhau.
Tr−ớc khi thiết kế một mô hình toán học phù hợp với thực tế, ta cần
bổ đề sau đây.
3.2.4. Bổ đề. Cho X là một tập hợp. Giả sử G là một nhóm con của
nhóm các phép thế S(X) của X . Khi đó G tác động tự nhiên lên X nh−
sau: g • x = g(x) với mọi x ∈ X, g ∈ G.
Chứng minh. Cho g, h ∈ G, x ∈ X. Ta có 1X • x = 1X(x) = x và
g • (h • x) = g • h(x) = g(h(x)) = (gh)(x) = (gh) • x.
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
30
Bây giờ ta xét một mô hình toán học. Giả sử ta có k mầu cho sẵn
để tô màu các đỉnh của lục giác đều nh− trong Ví dụ 3.2.2. Chú ý rằng
nhóm nhị diện D12 là nhóm con của nhóm các phép thế S(X), trong đó
X là tập các đỉnh của lục giác. Vì thế D12 tác động tự nhiên lên tập các
đỉnh của lục giác đều (xem Bổ đề 3.2.4), và vì thế nó tác động lên tập
các cách tô mầu của các đỉnh. Với mỗi g ∈ D12, t−ơng tự nh− các lập
luận trong Chú ý 3.2.3, nếu C là một cách tô màu các đỉnh của lục giác
và C ′ = g • C là tác động của g lên C thì trong nhiều tr−ờng hợp ta có
thể coi các cách tô màu C và C ′ là nh− nhau. Vì thế các cách tô màu
trong cùng quỹ đạo {g • C : g ∈ D12} của C nên đ−ợc xem là t−ơng
đ−ơng. Trong tr−ờng hợp này, số cách tô màu phân biệt (không t−ơng
đ−ơng) chính là số các quỹ đạo.
Định lí Burnside 1.4.5 giúp ta tính đ−ợc số quỹ đạo của một tác động
nếu ta biết số cách tô màu cố định qua tác động của một hoán vị cho
tr−ớc. Vì thế ta cần mệnh đề sau đây.
3.2.5. Mệnh đề. Gọi G là nhóm con của nhóm các phép thế S(X) với
X là tập các đỉnh của một đa giác đều n cạnh. Cho g ∈ G. Giả sử g là
tích của c vòng xích độc lập, tính cả các xích có độ dài 1. Nếu ta có k
màu thì số cách tô màu các đỉnh của đa giác cố định qua tác động của
g là kc.
Chứng minh. Cho C là một cách tô màu các đỉnh của đa giác. Giả sử C
cố định qua tác động của g (tức là C = g •C), khi đó với mỗi vòng xích
(a1, . . . , ap) của g, vì g(a1) = a2, g(a2) = a3, . . . , g(an) = a1 nên các
đỉnh a1, . . . , ap phải có cùng màu. Ng−ợc lại, giả sử với mỗi vòng xích
(a1, . . . , ap) của g, các đỉnh a1, . . . , ap có cùng màu. Khi đó rõ ràng C
là cố định qua tác động của g. Vì thế số cách tô màu cố định qua tác
động của g là số cách chọn màu cho các xích của g, kể cả các xích có
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
31
độ dài 1, mỗi xích chọn một màu. Vì vậy có đúng kc cách tô màu cố
định qua tác động của g.
3.2.6. Ví dụ. Giả sử ta có k mầu để tô màu các đỉnh của một lục giác
đều. Trong nhóm nhị diện D12, xét hai phép thế T = (2, 6)(3, 5) và
R2 = (1, 3, 5)(2, 4, 6) (xem Ví dụ 3.2.2). Ta cần tính số cách tô màu cố
định qua T và số cách tô màu cố định qua R2. Vì T có 4 vòng xích (2
vòng xích cấp 2 và 2 vòng xích cấp 1), nên áp dụng Mệnh đề 3.2.5, số
cách tô màu cố định qua tác động của T là k4. Vì R2 có 2 vòng xích
nên số cách tô màu cố định qua tác động của R2 là k2.
3.2.7. Ví dụ. Giả sử ta có k mầu để tô màu các đỉnh của một lục giác
đều. Ta cần tính xem có bao nhiêu cách tô màu phân biệt, trong đó hai
cách tô màu đ−ợc xem là nh− nhau nếu cách này là tác động của cách
kia qua một phần tử nào đó của nhóm nhị diện D12. Trong nhóm nhị diện
D12, có 1 hoán vị gồm 6 vòng xích (đó là hoán vị đồng nhất); có 3 hoán
vị gồm 4 vòng xích; có 4 hoán vị gồm 3 vòng xích; có 2 hoán vị gồm
2 vòng xích; và 2 hoán vị gồm 1 vòng xích (xem Ví dụ 3.2.2). Với mỗi
g ∈ D12, áp dụng Mệnh đề 3.2.5, ta tính đ−ợc số cách tô màu cố định
qua tác động của g. Từ đó, áp dụng công thức trong Định lí 1.4.5, ta tính
đ−ợc số quỹ đạo phân biệt là :
1
12
(k6 + 3k4 + 4k3 + 2k2 + 2k).
Đây cũng chính là số cách tô mầu phân biệt.
3.3 Một số ví dụ minh họa
3.3.1. Ví dụ. Giả thiết rằng 2 cách tô màu các đỉnh của một hình vuông
là t−ơng đ−ơng nếu cách tô mầu này là tác động của một hoán vị trong
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
32
nhóm D8 lên cách tô màu kia. Khi đó với k màu cho tr−ớc, có
1
8
(k4 + 2k3 + 3k2 + 2k).
cách tô màu phân biệt.
Chứng minh. Xét một hình vuông tâm O với các đỉnh là 1, 2, 3, 4 sắp
thứ tự ng−ợc chiều kim đồng hồ. Nếu kí hiệu I là phép thế đồng nhất, R
là phép quay tâm O với góc quay 900 và T là phép đối xứng qua đ−ờng
thẳng nối hai đỉnh 1 và 3 thì nhóm nhị diện D8 gồm 8 phần tử sau:
I;R = (1, 2, 3, 4);R2 = (1, 3)(2, 4);R3 = (1, 4, 3, 2);T = (2, 4);
RT = (1, 2)(3, 4);R2T = (1, 3);R3T = (1, 4)(2, 3)
Nh− vậy nhóm D8 gồm có:
1 hoán vị 4 vòng xích, đó là I
2 hoán vị 3 vòng xích, đó là T và R2T
3 hoán vị 2 vòng xích, đó là R2, RT và R3T
2 hoán vị 1 vòng xích, đó là R và R3.
Từ đó áp dụng công thức Burnside và Mệnh đề 3.2.5, ta có số cách tô
màu phân biệt các đỉnh hình vuông nói trên là:
1
8
(k4 + 2k3 + 3k2 + 2k).
Nhận xét rằng, nếu thay việc tô màu các đỉnh bằng việc tô màu các
cạnh của hình vuông trong Ví dụ 3.3.1, với giả thiết 2 cách tô màu là
nh− nhau nếu cách này là tác động của cách kia qua một phép thế trong
nhóm D8 thì ta cũng có kết quả t−ơng tự. Thật vậy, gọi a1, a2, a3, a4 làn
l−ợt là các cạnh nối hai đỉnh 1− 4, 1− 2, 2− 3 và 3− 4. Khi đó nhóm
D8 gồm 8 phần tử sau: I , R = (a1, a2, a3, a4), R2 = (a1, a3)(a2, a4),
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
33
R3 = (a1, a4, a3, a2), T = (a1, a2)(a3, a4), RT = (a1, a3), R2T =
(a1, a4)(a2, a3), R3T = (a2, a4). Nh− vậy, D8 bao gồm 1 hoán vị 4 vòng
xích, 2 hoán vị 3 vòng xích, 3 hoán vị 2 vòng xích, 2 hoán vị 1 vòng
xích. Do đó số cách tô màu phân biệt vẫn là
1
8
(k4 + 2k3 + 3k2 + 2k).
3.3.2. Ví dụ. Ng−ời ta cần tô màu các đỉnh hình của một hình vuông
với 2 màu trắng và xanh. Khi đó số cách tô màu các đỉnh là 16. Gọi X
là tập các cách tô màu. Trên X, xét quan hệ t−ơng đ−ơng ∼ nh− sau:
∀C1, C2 ∈ X : C1 ∼ C2 ⇔ ∃g ∈ D8 sao cho C2 = gC1.
Khi đó sẽ có 6 lớp t−ơng đ−ơng. HGy xác định các lớp t−ơng đ−ơng đó.
Chứng minh. Ta có k = 2. Theo Ví dụ 3.3.1, số cách tô màu phân biệt là
1
8
(24 + 2.23 + 3.22 + 2.2) = 6.
Vì thế quan hệ t−ơng đ−ơng trên có 6 lớp t−ơng đ−ơng, mỗi lớp t−ơng
đ−ơng là một quỹ đạo của tác động của nhóm D8 lên tập các đỉnh của
hình vuông. Để tìm 6 lớp t−ơng đ−ơng đó, ta chú ý rằng X gồm 16 phần
tử, mỗi phần tử là một bộ gồm 4 toạ độ t−ơng ứng với 4 đỉnh 1, 2, 3, 4
mà mỗi toạ độ (mỗi đỉnh) là t (trắng) hoặc x (xanh). Chẳng hạn, phần
tử (txxt) ∈ X là cách tô màu trắng ở đỉnh 1 và đỉnh 4, màu xanh ở đỉnh
2 và đỉnh 3.
Lớp t−ơng đ−ơng của (tttt) là
C1 = {g(tttt)} | g ∈ D8} = {(tttt)}.
T−ơng tự, lớp t−ơng đ−ơng của (xxxx) là
C2 = {g(xxxx)} | g ∈ D8} = {(xxxx)}.
Lớp t−ơng đ−ơng của (txxx) là
C3 = {g(txxx) | g ∈ D8} = {(txxx), (xtxx), (xxtx), (xxxt)}.
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
34
Lớp t−ơng đ−ơng của (ttxx) là
C4 = {g(ttxx)} | g ∈ D8} = {(ttxx), (xttx), (xxtt), (txxt)}
Lớp t−ơng đ−ơng của (tttx) là
C5 = {g(tttx)} | g ∈ D8} = {(tttx), (xttt), (txtt), (ttxt)}
Lớp t−ơng đ−ơng của (txtx) là
C6 = {g(txtx)} | g ∈ D8} = {(txtx), (xtxt)}.
3.3.3. Ví dụ. Giả sử một cái cây gậy đ−ợc đặt trên trục hoành từ x = −1
đến x = 1 với 3 hạt đ−ợc đính trên gậy. Các hạt này đ−ợc đính tại các
điểm cuối (tức là đ−ợc đính tại điểm (−1, 0) và (1, 0)) và tại trung điểm
(0, 0) của gậy. Ng−ời ta muốn tô 3 hạt đó bằng n màu, và hai cách tô
màu đ−ợc coi là nh− nhau nếu cách tô mầu này là tác động lên cách tô
màu kia qua phép hoán vị trong nhóm {I, δ}, trong đó I là phép thế đồng
nhất và δ là phép quay quanh trục tung một góc 1800. Khi đó số cách tô
màu phân biệt là
1
2
(n2 + n3).
Chứng minh. Ta giả sử các vị trí đính hạt là 1, 2, 3. Xét nhóm {I, δ}.
Chú ý rằng I là hoán vị 3 vòng xích và
δ =
(
1 2 3
1 2 3
)
= (1, 3)
là hoán vị gồm 2 vòng xích. Từ đó áp dụng công thức Burnside và Mệnh
đề 3.2.5, số cách tô màu phân biệt cho 3 hạt đó với n màu là
1
2
(n2 + n3).
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
35
Chú ý rằng với các giả thiết nh− Ví dụ 3.3.3 và giả thiết thêm rằng
trong n màu đó có mầu đen. Khi đó số cách tô màu phân biệt sao cho
hạt ở giữa gậy luôn có màu đen là
1
2
(n+n2). Thật vậy, mỗi cách tô màu
là một cách chọn mầu chỉ cho 2 hạt ở 2 đầu. Gọi 2 vị trí đó là 1, 3. Khi
đó trong nhóm {I, δ}, phép thế đồng nhất I có 2 vòng xích (1) và (3),
còn δ có 1 vòng xích là (1, 3). Vì thế theo Định lí Burnside và Mệnh đề
3.2.5, số cách tô màu phân biệt là
1
2
(n+ n2).
3.3.4. Ví dụ. Với 2 màu đỏ và xanh ta cần tô màu các đỉnh của một lục
giác đều. Giả thiết rằng 2 cách tô màu là t−ơng đ−ơng nếu cách tô mầu
này là tác động lên cách tô màu kia qua một hoán vị trong nhóm nhị
diên D12 . Khi đó có 3 cách tô màu phân biệt sao cho 3 đỉnh của lục
giác có màu đỏ và 3 đỉnh còn lại có màu xanh.
Chứng minh. Với 2 màu đỏ và xanh, theo logic sẽ có 26 cách tô màu cho
6 đỉnh của một lục giác đều. Trong số này, ta tìm số cách tô mầu màu
có 3 đỉnh màu đỏ và 3 đỉnh màu xanh. Số cách tô này cũng chính là
số cách chọn 3 đỉnh từ 6 đỉnh của lục giác, vì khi 3 đỉnh đ−ợc chọn đG
tô màu đỏ thì những đỉnh còn lại buộc phải tô màu xanh. Nh− vạy, có
20 cách tô sao cho có 3 đỉnh màu đỏ và 3 đỉnh màu xanh (chính là số
tổ hợp chập 3 của 6 phần tử). Gọi L là tập 20 cách tô này. Ta phải tìm
xem trong L có bao nhiêu cách tô màu phân biệt (ở đây, 2 cách tô màu
trong L đ−ợc xem là nh− nhau nếu cách này là tác động của cách kia bởi
một phép thế của D12). Nh− vậy, để tính số cách tô màu phân biệt trong
L, với mỗi g ∈ D12, ta cần tính số phần tử của L cố định qua g là bao
nhiêu.
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
36
Nhắc lại rằng nhóm nhị diên D12 gồm 12 phần tử nh− sau
I;R = (1, 2, 3, 4, 5, 6);R2 = (1, 3, 5)(2, 4, 6);R3 = (1, 4)(2, 5)(3, 6);
R4 = (1, 5, 3)(2, 6, 4);R5 = (1, 6, 5, 4, 3, 2);T = (2, 6)(3, 5);
RT = (1, 2)(3, 6)(4, 5);R2T = (1, 3)(4, 6);R3T = (1, 4)(2, 3)(5, 6);
R4T = (1, 5)(2, 4);R5T = (1, 6)(2, 5)(3, 4),
trong đó I là phép thế đồng nhất, R là phép quay 600 và T là phép đối
xứng qua đ−ờng thẳng nối 2 đỉnh 1,4. Cho g ∈ D12. Kí hiệu f(g) là
số phần tử của L cố định qua tác động của g. Giả sử f(g) > 0. Khi đó
tồn tại z ∈ L sao cho nó cố định qua tác động của g. Theo chứng minh
Mệnh đề 3.2.5, nếu (a1, . . . , at) là một vòng xích của g thì trong cách
tô màu z, các đỉnh a1, . . . , at phải có cùng màu. Vì z có 3 đỉnh màu
đỏ và 3 đỉnh màu xanh nên g chỉ có thể là một trong các phép thế sau
đây: I , R2 = (1, 3, 5)(2, 4, 6), R4 = (1, 5, 3)(2, 6, 4), T = (2, 6)(3, 5),
R2T = (1, 3)(4, 6), R4T = (1, 5)(2, 4). Trong tr−ờng hợp này, ta dễ thấy
số vòng xích của g phải chẵn. Nh− vậy, nếu g ∈ D12 có số vòng xích
lẻ thì sẽ không có phần tử nào của L cố định qua tác động của g, tức là
f(g) = 0.
Chú ý rằng tất cả các phần tử của L đều cố định qua I . Do đó
f(I) = 20. Đối với phép thế R2, có 2 cách tô màu trong L cố định qua
R2, cách thứ nhất là tô các đỉnh 1,3,5 màu đỏ và các đỉnh 2,4,6 màu
xanh. Cách thứ hai là tô các đỉnh 1,3,5 màu xanh và 2,4,6 màu đỏ. Vì
thế f(R2) = 2. T−ơng tự f(R4) = 2. Phép thế T có 4 vòng xích. Có 4
cách tô màu trong L cố định qua T , cách thứ nhất là tô các đỉnh 1,2,6
màu đỏ và các đỉnh 4,3,5 màu xanh; cách thứ hai là tô các đỉnh 1,3,5 màu
đỏ và 4,2,6 màu xanh, cách thứ ba là tô 1,2,6 màu xanh và 4,3,5 màu đỏ,
cách thứ t− là tô 1,3,5 màu xanh và 4,2,6 màu đỏ. Nh− vậy f(T ) = 4.
T−ơng tự ta có f(R2T ) = f(R4T ) = 4. Theo công thức Burnside và
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
37
Mệnh đề 3.2.5, số cách tô màu phân biệt trong L là
1
12
(2.2 + 3.4 + 20) = 3.
3.3.5. Ví dụ. Gọi G là nhóm gồm 12 phép quay một khối tứ diện đều
bao gồm: hoán vị đồng nhất I và 08 phép quay ng−ợc chiều kim đồng hồ
quanh trục nối 1 đỉnh với trọng tâm của mặt đối diện với góc quay1200
và 2400, đó là:
(1)(2, 3, 4), (1, 3, 4)(2), (1, 2, 4)(3), (1, 2, 3)(4),
(1)(2, 4, 3), (1, 4, 3)(2), (1, 4, 2)(3), (1, 3, 2)(4)
và 03 phép quay quanh 03 trục nối các trung điểm của 2 cạnh chéo nhau
với góc quay 1800. Giả thiết rằng 2 cách tô màu là t−ơng đ−ơng nếu cách
này là tác động lên cách kia qua một hoán vị nào đó trong nhóm G. Khi
đó với k màu cho tr−ớc để tô màu các đỉnh của khối tứ diện nói trên, có
1
12
(n4 + 11n2)
cách tô màu phân biệt.
Chứng minh. Ta thấy với khối tứ diện đều với các đỉnh 1,2,3,4 thì 3 phép
quay quanh 3 trục nối các trung điểm của 2 cạnh chéo nhau với góc quay
180o sẽ là:
(1, 4)(2, 3), (1, 3)(2, 4), (1, 2)(3, 4).
Nh− vậy ta thấy trong nhóm G gồm:
01 hoán vị 4 vòng xích, đó là hoán vị đồng nhất I .
11 hoán vị 2 vòng xích, đó là 11 hoán vị trong G khác I .
Từ đó áp dung công thức Burnside và Mệnh đề 3.2.5, số cách tô màu
phân biệt các đỉnh của khối tứ diện đó là
1
12
(n4 + 11n2)
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
38
3.3.6. Ví dụ. Giả sử ta có 4 màu, trong đó có màu xanh để tô màu các
đỉnh của khối tứ diện đều. Gọi G là nhóm phép thế gồm 12 phần tử xác
định nh− trong Ví dụ 3.3.5. Giả thiết rằng 2 cách tô màu đ−ợc xem là
nh− nhau nếu cách tô này là tác động của cách kia qua một phép thế
trong G. Khi đó có 6 cách tô màu phân biệt sao cho có đúng 2 đỉnh
đ−ợc tô màu xanh.
Chứng minh. Theo tính toán logic, có 44 cách tô màu các đỉnh của khối
đa diện đều bằng 4 màu cho tr−ớc. Trong số đó, số cách tô màu mà có
đúng 2 đỉnh màu xanh chính là số cách chọn ra 2 đỉnh trong 4 đỉnh để tô
màu xanh và tô 2 đỉnh còn lại bằng 3 màu còn lại. Kí hiệu Ckn là số tổ
hợp chập k của n phần tử. Khi đó số cách tô màu có đúng 2 đỉnh màu
xanh là
C24 .3
2 =
4!
2!2!
32 = 54.
Gọi L là tập 54 cách tô màu sao cho có đúng 2 đỉnh màu xanh. Khi
đó số cách tô màu phân biệt trong L chính là số quỹ đạo của tác động
của nhóm G lên tập L. Để tính số quỹ đạo này, ta cần tìm số phần tử cố
định qua tác động của mỗi phần tử của G. Cho g ∈ G. Kí hiệu f(g) là
số phần tử của L cố định qua tác động của g. Giả sử f(g) > 0. Khi đó
tồn tại z ∈ L sao cho z cố định qua tác động của g. Theo chứng minh
Mệnh đề 3.2.5, nếu (a1, . . . , at) là một vòng xích của g thì trong cách
tô màu z, các đỉnh a1, . . . , at phải có cùng màu. Vì z đúng 2 đỉnh màu
xanh nên nhất thiết g phải có ít nhất 1 vòng xích cấp 2 (để 2 đỉnh ứng
với vòng xích đó đều đ−ợc tô màu xanh) hoặc g có ít nhất 2 vòng xích
cấp 1 (để 2 đỉnh ứng với 2 vòng xích đó đều đ−ợc tô màu xanh). Do đó
g chỉ có thể là một trong 4 phép thế sau đây: I , (1, 4)(2, 3), (1, 3)(2, 4),
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
39
(1, 2)(3, 4). Nh− vậy, nếu g không là một trong 4 phép thế trên thì sẽ
không có phần tử nào của L cố định qua tác động của g, tức là f(g) = 0.
Chú ý rằng tất cả các phần tử của L đều cố định qua I . Do đó
f(I) = 54. Đối với phép thế g = (1, 4)(2, 3), nếu z là cách tô màu cố
định qua tác động của g thì các đỉnh 1,4 của z phải có cùng màu và các
đỉnh 2,3 của z cũng cùng màu. Do đó có 6 cách tô màu trong L cố định
qua (1, 4)(2, 3). Trong 6 cách đó, có 3 cách tô hai đỉnh 1,4 màu xanh và
tô hai đỉnh 2,3 cùng 1 màu trong số 3 màu còn lại, và có 3 cách tô hai
đỉnh 2,3 màu xanh và tô hai đỉnh 1,4 cùng 1 màu trong số 3 màu còn lại.
Vì thế f(g) = 6. T−ơng tự, số cách tô màu trong L cố định qua tác động
của (1, 3)(2, 4) hoặc của (1, 2)(3, 4) đều là 6. Theo công thức Burnside
và Mệnh đề 3.2.5, số cách tô màu phân biệt trong L là
1
12
(54 + 3.6) = 6.
3.3.7. Ví dụ. Cho p là số nguyên tố. Xét một đa giác đều p cạnh với
tâm O. Gọi I là phép đồng nhất và R là phép quay tâm O ng−ợc chiều
kim đồng hồ với góc quay 3600/p. Kí hiệu
G = {I,R,R2, . . . , Rp−1}.
là nhóm các phép quay của đa giác. Giả thiết rằng hai cách tô màu là
t−ơng đ−ơng nếu cách tô này là tác động lên cách kia qua một phép quay
trong G. Khi đó với n màu cho tr−ớc, để tô màu các đỉnh của đa giác,
số cách tô màu phân biệt là
1
p
(np + (p− 1)n).
Chứng minh. Tr−ớc hết ta nhận thấy vì p là nguyên tố nên p lẻ. Nếu
ta kí hiệu các đỉnh của đa giác p cạnh này là 1, 2, 3, . . . , p − 1, p thì
R = (1, 2, 3, . . . , p − 1, p). Do đó R2 = (1, 3, . . . , p, 2, 4, . . . , p − 1).
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
40
T−ơng tự, vì p lẻ nên R3, R4, . . . , Rp−1 đều là các phép thế 1 vòng xích.
Nh− vậy trong nhóm G có
1 phép thế p vòng xích, đó là hoán vị đồng nhất I .
p− 1 phép thế 1 vòng xích, đó là R,R2, . . . , Rp−1.
Theo công thức Burnside và Mệnh đề 3.2.5, số cách tô màu phân biệt các
đỉnh của đa giác đó là
1
p
(np + (p− 1)n).
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
Tài liệu tham khảo
[ABR] P. Anderson, A. Benjamin, J. Rouse, Combinatorial proofs of
Fermat’s, Lucas’s and Wilson’s theorems, American Math. Monthly,
112(3) (2005), 266-268.
[Ash] R. Ash, Abstract Algebra - The Basic Graduate Year, Dover, New
York 2002.
[EH] T. Evans, B. Holt, Deriving divisibility theorems with Burnside’s
theorem, Electronic J. Combinatorial number theory, 5 (2005), 1-5.
[Hum] J. F. Humphreys, A Course in group theory, Oxford University
Press, Oxford 1996.
[Lev] Lionel Levine, Fermat’s little theorem: a proof by function inter-
ation, Mathematics Magazine, 72(4) (1999), 308-309.
[Rot] J. Rotman, An introduction to the Theory of Groups, (Third Edition)
Springer - Verlag, New York 1999.
[Sur] D. Surowski, Workbook in higher Algebra, Springer - Verlag, New
York 1992.
41
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
Các file đính kèm theo tài liệu này:
- 10LV_09_DHKH_PPTOAN_NGUYEN TUYET NGA.pdf