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

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