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

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

pdf43 trang | Chia sẻ: maiphuongdc | Lượt xem: 1732 | Lượt tải: 6download
Bạn đang xem trước 20 trang 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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

Các file đính kèm theo tài liệu này:

  • pdf10LV_09_DHKH_PPTOAN_NGUYEN TUYET NGA.pdf
Tài liệu liên quan