17 Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Cha

Transcription

1 Solutions Manual for Gallian s Contemporary Abstract Algebra 8/e 張世杰 bfhaha@gmail.com January 12, 2017 Contents 0 Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter

2 17 Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter Chapter For n = 5, 8, 12, 20, and 25, find all positive integers less than n and relatively prime to n. 補充. relatively prime 就是 互質 的意思, 所以題目是要找小於 n 且與 n 互質的所有正整數 例如 n = 12 時, 我們可以先算出 12 = 2 2 3, 我們要找跟 12 互質且小於 12 的正整數時, 我們只要找 不含有 因數 2 跟因數 3 的正整數就好 0.2 Determine and gcd ( , ) lcm( , ). 0.3 Determine 51 mod 13, 342 mod 85, 62 mod 15, 10 mod 15, (82 73) mod 7, ( ) mod 7, (35 24) mod 11, and (47 68) mod 11. 補充. a mod n 的意思就是 a 被 n 除之後的餘數, 例如 17 被 5 除餘 2, 所以 17 mod 5 = 2 你可能對這個 mod 運算感到彆扭, 但事實上, 你平常就已經在使用它了, 例如我們的時鐘就是 mod 12, 所以 14 點也可以說是下午 14 mod 12 = 2 點 ; 又或者是星期就是 mod 7 2

3 0.4 Find integers s and t such that 1 = 7 s + 11 t. Show that s and t are not unique. 補充. 我作一題更複雜的給你看 : Find integers s and t such that 1 = 69 s + 31 t. 69 = , (1) 31 = , (2) 7 = (3) (18) 1 = (17) = 7 (31 7 4) 2 = = (16) = ( ) = = s = 9, t = 20. 注意到 gcd (7, 11) 及 gcd (69, 31) 都是 1 一般來說, 我們有 gcd (a, b) = 1 s, t Z such that as + bt = 1. (4) 這超級重要的, 你以後看到 a, b 互質 (relatively prime) 或是 gcd (a, b) = 1, 你就要馬上想到他, 這不是很好證, 你不妨就先把他記下來 另外, 我們其實還有 gcd (a, b) = d s, t Z such that as + bt = d. (5) 0.6 Suppose a and b are integers that divide the integer c. If a and b are relatively prime, show that ab divides c. Show, by example, that if a and b are not relatively prime, then ab need not divide c. 補充. Since a c and b c, suppose that c = aq 1, c = bq 2, q 1, q 2 Z. (6) Since gcd (a, b) = 1 (4) s, t Z such that as + bt = 1 multiplying c asc + = c (6) as(bq 2 ) + = c ab(sq 2 ) + = c ab(sq 2 + ) = c ab c. 如果 gcd (a, b) 1 時的反例自己想想 3

4 0.7 If a and b are integers and n is a positive integer, prove that a mod n = b mod n if and only if n divides a b. 補充. 關於 a mod n 這東西, 如果你沒有學過基礎數論, 請務必花一些時間把它弄熟, 我實在無法過分強調它在數論及代數中的重要性 先複習一下高中學的 整除 (divide), a 整除 b 的意思就是 a 是 b 的因數, 或是說 b 是 a 的倍數, 也就是存在整數 q, 使得 b = aq, 我們記作 a b, 其中 a 0 我們剛剛講過, a mod n 代表一個數字, 這個數字就是 a 被 n 除之後的餘數, 所以 a mod n = b mod n 的意思就是 a 跟 b 被 n 除之後的餘數會是一樣的, 我們稱 a 跟 b 對模 n 同餘, 用符號來記的話, 就是 a b (mod n) 所以 Exercise 0.7 的意思就是 我們證明如下 a b (mod n) n (a b) (7) a b (mod n) 慣用的符號 a mod n = b mod n 課本用的符號 a n = q 1...r, b n = q 2...r 國小用的符號, 好懷念啊 a = nq 1 + r, b = nq 2 + r, q 1, q 2 Z 高中用的符號 (a b) = (nq 1 + r) (nq 2 + r) = nq 1 nq 2 = n(q 1 q 2 ) (a b) = n(q 1 q 2 ) n a b. 另外, 這個 其實就是一個 equivalence relation 這個我們之後會談 0.8 Let d = gcd (a, b). If a = da and b = db, show that gcd (a, b ) = 1. 補充. 用反證法 這題的另一種表示就是 Suppose gcd (a, b ) = k > 1 (8) k a, k b a = kq 1, b = kq 2, q 1, q 2 Z a = da = dkq 1, b = = 第 10 題 dk a and dk gcd (a, b) = d dk d dk d, contrary to (8). a gcd ( gcd (a, b), b ) = 1. (9) gcd (a, b) 你可以試試看證明 a bc a gcd (a, b) b gcd (a, b) c. 4

5 由此再配合 Exercise 0.19 及 (9), 可以得到 a bc a gcd (a, b) c. 這幾個結果我們在後面學 cyclic group 的時候會用到 0.9 Let n be a fixed positive integer greater than 1. If a mod n = a and b mod n = b, prove that (a + b) mod n = (a + b ) mod n and (ab) mod n = (a b ) mod n. (This exercise is referred to in Chapter 6, 8, 10, and 15.) 補充. a mod n = a, b mod n = b (7) n (a a ), n (b b ) a a = nq 1, b b = nq 2, q 1, q 2 Z a = a + nq 1, b = a + b = (a + nq 1 ) + ( ) = (a + b ) + (nq 1 + ) = (a + b ) + n(q 1 + ) (a + b) (a + b ) = n(q 1 + ) n (a + b) (a + b ) (a + b) (a + b ) (mod n) (a b) (a b ) (mod n) 也是類似的方法 利用這題的結果, 你應該想想 Exercise 0.3 有沒有更快的算法 0.10 Let a and b be positive integers and let d = gcd (a, b) and m = lcm(a, b). If t divides both a and b, prove that t divides d. If s is a multiple of both a and b, prove that s is a multiple of m. 補充. 前半部比較重要, 後半部不妨先跳過 我們先來證一個 Lemma: If t a and t b, then t as + bu for any s, u Z. 事實上, 這是非常基本的技巧, 來證原題目 : If t a and t b a = tq 1, b =, q 1, q 2 Z as = t(q 1 s), bu = t(q 2 u), q 1, q 2, s, u Z as + bu = t(q 1 s) + t(q 2 u) = t( ) t as + bu. (10) gcd (a, b) = d (5) s, u Z such that as + bu = d. (11) If t a and t b (10) t as + bu (11) = d. 5

6 你要想一想這題背後的意義, 這題說明了, 任何公因數都是最大公因數的因數, 聽起來真繞口 0.11 Let n and a be positive integers and let d = gcd (a, n). Show that the equation ax (mod n) = 1 has a solution if and only if d = 1. 補充. 想一想這題跟 U(n) 的定義有何關係? Theory 中學的 Z n U(n) 就是你們在 Elmentary Number Proof. We need a lemma: gcd (a, b) = 1 s, t Z such that as + bt = 1. ( ) It follows immediately from p.4, thm.0.2. () If there exists s, t Z such that as + bt = 1, then since gcd (a, b) a and gcd (a, b) b, we have gcd (a, b) (as + bt) = 1. Which implies that gcd (a, b) = 1. gcd (a, n) = 1 Lemma s, t Z, such that as + nt = 1 as 1 = n( t) n (as 1) as 1 (mod n) ax 1 (mod n) has a solution a has a multiplicative inverse modulo n a U(n) 類似 0.11 Solve the congruence equation 69x 1 (mod 31). 補充. 由 Exercise 0.4 的提示, ( 20) = = (mod 31) (12) 利用 (12) 及 Exercise 0.9 的結果, 將 69x 1 (mod 31) 左右同乘以 9, 得到 9 69x 9 1 (mod 31) (12) 1 x x 9 (mod 31) 這個我們在後面求一些 group 中的元素的 inverse 時會用到 0.13 Suppose that m and n are relatively prime and r is any integer. Show that there are integers x and y such that mx + ny = r. 6

7 補充. 這題就是 (4), 證明有點難度, 你可以先跳過, 但如果你想要挑戰看看的話, 下面是提示 你學期末學完 ring 之後, 你會發現如果用 ring 的觀點來看, 這個定理就會變得很簡單 ˆ Consider the set S = {ms + nt s, t Z}. ˆ Consider the subset S + = {a S a > 0} of S. ˆ Prove that S +. ˆ Apply the Well-Ordering Principle on S +, there is a smallest positive integer d in S +. ˆ Suppose that d = mp + nq. ˆ If c m and c n, by (10), c mp + nq = d. ˆ That is, d = gcd (m, n). ˆ If gcd (m, n) = 1, then there exist p, q Z such that mp + nq = 1. r = m(pr) + n(qr). Let x = pr and y = qr Determine mod 6 and mod 7. 補充. 注意到 7 1 (mod 6) and 6 1 (mod 7), 利用 Exercise 0.9 的結果 例如 ( 1) (mod 7). Thus, 0.17 Let a, b, s, and t be integers. If a (mod st) = b (mod st), show that a (mod s) = b (mod s) and a (mod t) = b (mod t). What condition on s and t is needed to make the converse true? 0.18 Determine mod 5. 補充. 注意到 (mod 5), 利用第 9 題的結果 例如 (8 2 ) ( 1) 201 (mod 5) Show that gcd (a, bc) = 1 if and only if gcd (a, b) = 1 and gcd (a, c) = 1. Proof. gcd (a, c) divides gcd (a, bc) is obviously. We show that gcd (a, bc) divides gcd (a, c). Since gcd (a, b) = 1, by p.4, thm.0.2, there exists s, t Z such that as + bt = 1. Let d = gcd (a, bc) d a and d bc d [a(cs) + (bc)t] = (as + bt)c = c d gcd (a, c). 類似 0.19 If gcd (a, b) = 1 and a bc, then a c. 7

8 補充. Since a bc, suppose that bc = aq, q Z. (13) Since gcd (a, b) = 1 (4) s, t Z such that as + bt = 1 multiplying c + (bt)c = c + (bc)t = c (13) asc + (aq)t = c a( ) = c a c Express ( 7 3i) 1 in standard form. 補充 Express 5+2i 4 5i in standard form i = ( 7+3i) ( 7 3i)( 7+3i) For every positive integer n, prove that a set with exactly n elements has exactly 2 n subsets (counting the empty set and the entire set). 補充. 這是高中的排列組合問題 0.30 (Generalized Euclid s Lemma) If p is a prime and p divides a 1 a 2 a n, prove that p divides a i for some i Use the Generalized Euclid s Lemma (see Exercise 0.30) to establish the uniqueness portion of the Fundamental Theorem of Arithmetic. 提示. Use mathematical induction on n Prove that the First Principle of Mathematical Induction isa consequence of the Well Ordering Principle In the cut As from Songs in the Key of Life. Stevie Wonder mentions the equation = 4. Find all integers n for which this statement is true, modulo n. 補充. 其實就是找 n 使得 (mod n). 關於 Stevie Wonder, 我想我必須要多講一點, 你可能不認識他, 但你一定聽過他的 I Just Called To Say I Love You. ( 他可以算是美國的蕭煌奇, ( 恩... 應該說蕭煌奇是台灣的 Stevie Wonder,) 布魯斯威利在終極警探裡說過一句玩笑話 : Who s driving this car, Stevie Wonder? Stevie Wonder 膾炙人口的當然不只這首歌, 還有 ˆ You Are The Sunshine Of My Life. 8

9 ˆ Part Time Lover. ˆ Sir Duke. ˆ Superstition. ˆ Master Blaster (Jammin ). ˆ Uptight (Everything s Alright) If it is 2 00 A.M. now, what time will it be 3736 hours from now? 補充. mod The 10-digit International Standard Book Number (ISBN-10) a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 has the property (a 1, a 2,..., a 10 ) (10, 9, 8, 7, 6, 5, 4, 3, 2, 1) mod 11 = 0. The digit a 10 is the check digit. When a 10 is required to be 10 to make the dot product 0, the character X is used as the check digit. Suppose that an ISBN-10 has a smudged entry where the question mark appears in the number 0-716? Determine the missing digit. 補充. (a 1, a 2,..., a 10 ) (10, 9, 8, 7, 6, 5, 4, 3, 2, 1) 是內積的意思, 就是 10 a a a a a 10. 這題就是 mod 的一個經典應用, 就在你手上拿的這本書背面 英國大數學家 Hardy 在 1940 寫的 一個數學家的辯白 裡面, 提到數論是個沒什麼應用的科目, 他萬萬想不到今天數論在密碼學上的重要性 在解這題的過程中, 你可能需要解 6x 9 (mod 11), 你可以將兩邊同乘以 2, 為什麼知道要乘以 2, 做完 Exercise 0.11 你就知道了 0.58 Let S be the set of real numbers. If a, b S, define a b if a b is an integer. Show that is an equivalence relation on S. Describe the equivalence classes of S. Proof. For all a S, a a = 0 Z, so a a, or says (a, a). If a b, then a b Z and b a = (a b) Z. Thus, b a. If a b and b c, then a b Z and b c Z and a c = (a b) + (b c) Z. Therefore, a c. 補充. 我們先任意選定一個數字, 例如 3.4 好了, 我們知道 , , ,... 我們可以考慮這個集合 [3.4] = {a R a 3.4}, 所以 3.4 [3.4], 4.4 [3.4], 5.4 [3.4],... 這個集合 [3.4] 就叫做一個 equivalence class equivalence relation 是比較抽象的內容, 其實你在學同餘 及 Z n 的時候就遇過了, 未來我們在學 coset 及代數拓樸時都還會再遇到他 雖然你不知道 equvalence relation 的話也可以往後學, 但是如果你瞭解它的話, 你會看到一番截然不同的數學面貌 這是比較進階的內容, 你不知道的話也可以往後學, 但是如果你瞭解它的話, 你會看到一番截然不同的數學面貌, 我覺得這也是你讀數學系真正該學的東西 我們先來講講 relation, 助教我高中的時候, 數學課本的第一章就是 邏輯 集合 函數, 這說明了這三個觀念是數學中最根本的東西, 我猜你早就聽過這句話了, 但你應該對這句話不是很有感覺, 我現在要展現這句話的深刻意涵給你看 9

10 先講一下 direct product, 兩個集合 A 跟 B 的 direct product 就是一個新的集合, 記作 A B, 這個集合收集由 A 跟 B 分別取元素出來構成的有序對 (ordered pair), 簡單來說就是 A B def. = {(a, b) a A, b B}. 當然, 我們也可以由一個集合 S 自己跟自己做 direct product, 你以前學的 R 2 = R R = {(x, y) x, y R} 就是一個典型的例子 你回想一下國小學的小於關係, 例如 13 < 25, 現在我們要用抽象 嚴謹的語言來描述這個 < 3 2 < 2, < 1, 21 /< 10, π /< 2,... 4 < 在本質上是一個集合, 它是一個 R R 的子集合 (subset), 這個 subset < 包含了下面這些元素 (13, 25), ( 2, 2), ( 3, 1),... 4 但是不包含 也就是 (21, 10), (π, 2),... <= {(13, 25), ( 2, 2), ( 3, 1),...} R R. 4 但是 (21, 10), (π, 2) <. 很抽象吧, 所以你看這個跟集合看似一點關係都沒有的觀念, 竟然可以用集合來定義它 我們現在來定義什麼是 relation, a relation on a set S def. = a subset of S S. 這實在太抽象了, 所以通常如果 (a, b), 我們就記作 a b, 所以剛剛的 (13, 25) <, 我們就記作 13 < 25 數學家們真是無聊嗎? 其實如果你瞭解這個 relation 的本質, 你在看數學上的很多事情時都會變得很清楚 有了 relation, 我們要定義 equivalence relation, 或是也可以記作 a relation on a set S is called an equivalence relation if and only if the following statements hold: (i) s S, (s, s). (ii) If (s, t), then (t, s). (iii) If (s, t) and (t, u), then (s, u). (i) s S, s s. (ii) If s t, then t s. (iii) If s t and t u, then s u. 關於 equivalence relation 的基本練習就是驗證一個 relation 是不是 equivalence relation, 假設 S = {a, b, c, d}, 請問下面哪一個 relation on S 是 equivalence relation? 10

11 ˆ 1 = {(a, b), (b, c), (c, d), (a, c), (b, d), (a, d)} ˆ 2 = {(a, b), (b, c), (a, c)} ˆ 3 = {(a, b), (b, c), (a, c), (a, a), (b, b), (c, c)} ˆ 4 = {(a, b), (b, c), (a, c), (a, a), (b, b), (c, c), (d, d)} ˆ 5 = {(a, b), (b, c), (a, c), (a, a), (b, b), (c, c), (d, d), (b, a), (c, b), (c, a)} 驗證一下 the relation < on R 不是一個 equivalence relation 驗證一下 the relation on Z 是一個 equivalence relation 這個 equivalence relation 尤其重要, 我們後面會花很長的篇幅來討論它 equivalence relation 跟 partition 是有密切關係的, 應該說他們算是同一件事 你應該想想, equivalence relation 感覺上就是一種弱化的相等, 例如 13 跟 9 本來是不相等的, 可是在 mod 4 之下, 它們就是相等的, 也就是 13 9 (mod 4) 如果你覺得類似這種探討數學本質的活動很有趣, 想要知道更多的話, 你可以想想你以前國小學的整數乘法, 其實就是一個從 Z Z 打到 Z 的函數, 也就是 Z Z Z, 例如 (3, 7) = Let S be the set of integers. If a, b S, define arb if ab 0. Is R an equivalence relation on S? 補充 Let S be the set of integers. If a, b S, define arb if a + b is even. Prove that R is an equivalence relation and determine the equivalence classes of S What is the last digit of 3 100? What is the last digit of 2 100? 補充. 一個數字 a 的個位數其實就是 a mod 10, 這在高中就學過了 (?) 助教我離高中很遠很遠了 (Cancellation Property) Suppose α, β, and γ are functions. If αγ = βγ and γ is one-to-one and onto, prove that α = β. Proof. α(x) = (α(γγ 1 ))(x) = ((αγ)γ 1 )(x) = ((βγ)γ 1 )(x) = (β(γγ 1 ))(x) = β(x) 11

12 1 Chapter With pictures and words, describe each symmetry in D 3 (the set of symmetries of an equilateral triangle). 1.2 Write out a complete Cayley table for D 3. Is D 3 Abelian? 補充. 你先想想, abelian 在 Cayley table 上如何表現? 這裡提供你一個記下 dihedral group D n 的 Cayley Table 的好方法, 其中 D n = {1, a, a 2,..., a n 1, b, ba, ba 2,..., ba n 1 a = n, b = 2, ab = ba 1 }. 在這裡以 D 3 為例, 但這個規律對於一般的 D n 都是成立的 ˆ 按照 1, a, a 2, b, ba, ba 2 的順序, 將表頭填上 ˆ 先寫出第一列 ˆ 將表格對半分成四等份, 然後畫交叉線, 把第一列的內容交叉填下來 ˆ 接著分別利用四個部分的第一列來填滿四個部分, 左半邊依序往左輪轉一格 ; 右半邊依序往右輪轉一格 如下圖所示 D 3 1 a a 2 b ba ba a a 2 b ba ba 2 a a 2 b b ba ba 2 1 a a 2 ba ba 2 得到 1.3 In D 4, find all elements X such that a. X 3 = V ; b. X 3 = R 90 ; c. X 3 = R 0 ; d. X 3 = R 0 ; e. X 3 = H. D 3 1 a a 2 b ba ba a a 2 b ba ba 2 a a a 2 1 ba 2 b ba a 2 a 2 1 a ba ba 2 b b b ba ba 2 1 a a 2 ba ba ba 2 b a 2 1 a ba 2 ba 2 b ba a a Describe in pictures or words the elements of D 5 (symmetries of a regular pentagon). 12

13 1.5 For n 3, describe the elements of D n. (Hint: You will need to consider two cases n even and n odd.) How many elements does D n have? 補充. 1.6 In D n, explain geometrically why a reflection followed by a reflection must be a rotation. 提示. 將正 n 邊形的頂點按順時針依序標號, 觀察 rotation 或是 reflection 如何影響頂點標號的順逆 例如 或是 In D n, explain geometrically why a rotation followed by a rotation must be a rotation. 補充. 1.8 In D n, explain geometrically why a rotation and a reflection taken together in either order must be a reflection. 補充 If r 1, r 2, and r 3 represent rotations from D n and f 1, f 2, and f 3 represent reflections from D n, determine whether r 1 r 2 f 1 r 3 f 2 f 3 r 3 is a rotation or a reflection Find elements A, B, and C in D 4 such that AB = BC but A C. (Thus, cross cancellation is not valid.) 1.12 Explain what the following diagram proves about the group D n. 補充. 13

14 1.13 Describe the symmetries of a nonsquare rectangle. Construct the corresponding Cayley table Describe the symmetries of a parallelogram that is neither a rectangle nor a rhombus. Describe the symmetries of a rhombus that is not a rectangle Describe the symmetries of a noncircular ellipse. Do the same for a hyperbola For each of the snowflakes in the figure, find the symmetry group and locate the axes of reflective symmetry (disregard imperfections). 補充. 關於雪花的美我就不多說了, 仔細看這些美麗的結構, 你很難不相信神的存在 ˆ 你可以參考這個網站 ˆ 助教上課給你們看的書在這裡, 博客來有賣, 700 元而已, ˆ 台灣很可惜看不到雪, 如果你企圖在家裡製造雪的話, 這個網站有教學, goo.gl/h7pw3, 不過我想買這些製作器材的錢可以出國好幾趟了 1.19 Does a fan blade have a cyclic symmetry group or a dihedral symmetry group? 補充 Bottle caps that are pried off typically have 22 ridges around the rim. Find the symmetry group of such a cap. 補充. 2 Chapter 2 常用結果 Gallian Burton Theorem exe.0.13 p.21, thm.2.3 gcd (a, b) = d s, t such that as + bt = d p.23, thm.2.4 gcd (a, b) = 1 s, t such that as + bt = 1 exe.0.6 p.23, cor.2 gcd (a, b) = 1, a c, b c ab c p.24, thm.2.5 gcd (a, b) = 1, a bc a c p.79, cor.2 a = n, a s = e n s exe.3.4 x = x 1 p.80, thm.4.2 a r n = gcd (r,n) 2.1 Which of the following binary operations are closed? (a) subtraction of positive integers (b) division of nonzero integers (c) function composition of polynomials with real coefficients (d) multiplication of 2 2 matrices with integer entries 2.2 Which of the following binary operations are associative? 14

15 (a) multiplication mod n (b) division of nonzero rationals (c) function composition of polynomials with real coefficients (d) multiplication of 2 2 matrices with integer entries 2.3 Which of the following binary operations are commutative? (a) subtraction of integers (b) division of nonzero real numbers (c) function composition of polynomials with real coefficients (d) multiplication of 2 2 matrices with integer entries 2.4 Which of the following sets are closed under the given operation? (a) {0, 4, 8, 12} addition mod 16 (b) {0, 4, 8, 12} addition mod 15 (c) {1, 4, 7, 13} multiplication mod 15 (d) {1, 4, 5, 7} multiplication mod In each case, find the inverse of the element under the given operation. (a) 13 in Z 20 (b) 13 in U(14) (c) n 1 in U(n) (n > 2) (d) 3 2i in C, the group of nonzero complex numbers under multiplication 2.6 In each case, perform the indicated operation. (a) In C, (7 + 5i)( 3 + 2i) (b) In GL(2, Z 13 ), det [ ] (c) In GL(2, R), [ ] 1 (d) In GL(2, Z 13 ), [ ] Referring to Example 13, verify the assertion that subtraction is not associative. 2.9 Show that {1, 2, 3} under multiplication modulo 4 is not a group but that {1, 2, 3, 4} under multiplication modulo 5 is a group Show that the group GL(2, R) of Example 9 is non-abelian by exhibiting a pair of matrices A and B in GL(2, R) such that AB BA Given an example of group elements a and b with the property that a 1 ba b Let G be a group and let H = {x 1 x G}. Show that G = H as sets. 15

16 2.20 For any integer n > 2, show that there are at least two elements in U(n) that satisfy x 2 = 1. 提示. 這裡教各位一個解題技巧, 我相信, 這也是數學家們發現新結果的常用手段 : 就是列出大量的例子, 然後再從中觀察並且大膽假設 小心求證 我們列出 U(3) U(9), 然後把滿足 x 2 = 1 的元素圈起來, 你發現了什麼事情嗎? 你發現了什麼事情嗎? U(3) = { 1O, 2O} U(4) = { 1O, 3O} U(5) = { 1O, 2, 3, 4O} 剩下的自己圈 U(6) = {1, 5} U(7) = {1, 2, 3, 4, 5, 6} U(8) = {1, 3, 5, 7} U(9) = {1, 2, 4, 5, 7, 8} Proof. When n > 2, n 1 1 U(n) and 1 2 = (n 1) 2 = 1. 補充. 這題跟 Exercise 3.59 有什麼關係? 2.22 Let G be a group with the property that for any x, y, z in the group, xy = zx implies y = z. Prove that G is Abelian. ( Left-right cancellation implies commutativity.) Proof. ab y = ba z b x (ab y ) = (ba z )b x 2.23 (Law of Exponents for Abelian Groups) Let a and b be elements of an Abelian group and let n be any integer. Show that (ab) n = a n b n. Is this also true for non-abelian groups? 2.24 (Socks-Shoes Property) Draw an analogy between the statement (ab) 1 = b 1 a 1 and the act of putting on and taking off your socks and shoes. Find distinct nonidentity elements a and b from a non-abelian group such that (ab) 1 = a 1 b 1. Find an example that shows that in a group, it is possible to have (ab) 2 b 2 a 2. What would be an appropriate name for the group property (abc) 1 = c 1 b 1 a 1? 補充. 我解釋一下為什麼 (sw) 1 = w 1 s 1 叫做 Socks-Shoes Property, ˆ 假設 s 表示穿鞋子,w 表示穿襪子 ˆ 那 sw 表示先穿襪子再穿鞋子, ( 注意, 我們看 sw ˆ 則 (sw) 1 表示要全部脫掉, 光腳丫 ˆ 脫掉時當然要先脫鞋子 s 1 再拖襪子 w 1, 也就是 w 1 s 1 ˆ 所以 (sw) 1 = w 1 s 1 16 時是從右到左, 跟函數一樣 )

17 2.25 Prove that a group G is Abelian if and only if (ab) 1 = a 1 b 1 for all a and b in G. Proof. () For any a, b G, ( ) For any a, b G, abelian (ab) 1 = b 1 a 1 = a 1 b 1. hypothesis ab = (a 1 ) 1 (b 1 ) 1 = (a 1 b 1 ) 1 = (b 1 ) 1 (a 1 ) 1 = ba For any elements a and b from a group and any integer n, prove that (a 1 ba) n = a 1 b n a. 補充. 這其實我們以前在 linear algebra 中, 講矩陣對角化的應用時就遇過了 例如 A = P 1 DP,A 100 = P 1 D 100 P Proof. If n = 0, then (a 1 ba) 0 = e = a 1 a = aea 1 = ab 0 a 1. If n > 0, then If n < 0, then (a 1 ba) n = (a 1 b a)( a 1 b a) ( a 1 ba) = a 1 b n a. n times (a 1 ba) n = ((a 1 ba) 1 ) n = (a 1 b 1 a) n = (a 1 b 1 a)( a 1 b 1 a) ( a 1 b 1 a) n times = a 1 (b 1 ) n a = a 1 b n a Give an example of a group with 105 elements. Give two examples of groups with 44 elements. 補充. Consider cyclic groups and dihedral groups Prove that every group table is a Latin square; that is, each element of the group appears exactly once in each row and each column. 補充. 這題隱含了一個很重要的訊息, 就是 group table 的每一行, 恰好都是這個 group 的元素的一個重新排列, 這我們在 Section 5 還會再詳細討論 這個發現引出了一個重要的定理 : Cayley Theorem. 17

18 2.34 Prove that if (ab) 2 = a 2 b 2 in a group G, then ab = ba. Proof. left multiplying a 1 right multiplying b 1 (ab) 2 = a 2 b 2 abab = aabb bab = abb ba = ab Let a and b belong to a group G. Find an x in G such that xabx 1 = ba Let G be a finite group. Show that the number of elements x of G such that x 3 = e is odd. Show that the number of elements x of G such that x 2 e is even. Proof. Note that x e, x 3 = e x 2 e x x 1. Let S = {x G x 3 = e}. Pick x 1 e S. Then x 1 x 1 1 and x 1 1 S. Remove these two elements x 1 and x 1 1 from S. Pick x 2 from the remaining elements, do the same process as above. We can always remove two elements because x 1 i x 1 j S if i j. Since G is finite, we can t do the process infinitely. Finally, there is only one element remain in S. That is, the identity element e. Thus, S = {e, x 1, x 1 1, x 2, x 1 2,,,,, x n, x 1 n } and #S is odd. Note that x 2 e x x 1. Let S = {x G x 2 e}. Pick x 1 e S. Then x 1 x 1 1 and x 1 1 S (why?). Remove these two elements x 1 and x 1 1 from S. Pick x 2 from the remaining elements, do the same process as above. We can always remove two elements because x 1 i x 1 j S if i j. Since G is finite, we can t do the process infinitely. Finally, there is no element remain in S. Thus, S = {x 1, x 1 1, x 2, x 1 2,,,,, x n, x 1 補充. c.f. Exercise n } and #S is even Given an example of a group with elements a, b, c, d and x such that axb = cxd but ab cd. (Hence middle cancellation is not valid in groups.) 2.39 Suppose that G is a group with the property that for every choice of elements in G, axb = cxd implies ab = cd. Prove that G is Abelian. ( Middle cancellation implies commutativity.) 補充. 1 ab = ba Find an element X in D 4 such that R 90 V XH = D. 補充. 想一想, 有沒有一眼就可以看出答案的方法 18

19 2.41 Suppose F 1 and F 2 are distinct reflections in a dihedral group D n. Prove that F 1 F 2 R 0. 補充. Since F1 2 = F 2 2 = R 0 and by Theorem 2.3, F1 1 = F 1 F2 1 = F 2. If F 1 F 2 = R 0, then F 2 = F Suppose F 1 and F 2 are distinct reflections in a dihedral group D n such that F 1 F 2 = F 2 F 1. Prove that F 1 F 2 = R 180. 補充. See Section 1 Exercise 6 (p.37). Note that (F 1 F 2 ) 2 = (F 1 F 2 )(F 1 F 2 ) = F 1 (F 2 F 1 )F 2 = F 1 (F 1 F 2 )F 2 = F 2 1 F 2 2 = R Let R be any fixed rotation and F any fixed reflection in a dihedral group. Prove that R k F R k = F. 補充. It is sufficient to show that R 360/n F R 360/n = F. Note that R = R m for some 360/n m Let R be any fixed rotation and F any fixed reflection in a dihedral group. Prove that F R k F = R k. Why does this imply that D n is non-abelian? 補充. It immediately follows by Exercise In the dihedral group D n, let R = R 360/n and let F be any reflection. Write each of the following products in the form R i or R i F, where 0 i < n. a. In D 4, F R 2 F R 5 b. In D 5, R 3 F R 4 F R 2 c. In D 6, F R 5 F R 2 F 補充 Prove that the set of all rational numbers of the form 3 m 6 n, where m and n are integers, is a group under multiplication. 提示. 記住 group test 的口訣 : 閉結單反 Proof. Let S = {3 m 6 n Q m, n Z}. We show that S is a group under multiplication. ˆ Closed: For any 3 m 1 6 n 1, 3 m 26 n 2 S, where m1, m 2, n 1, n 2 Z, since m 1 + m 2, n 1 + n 2 Z, we have 3 m 1 6 n 1 3 m 2 6 n 2 = 3 m 1+m 2 6 n 1+n 2 S. ˆ Associative: For any 3 m 1 6 n 1, 3 m 26 n 2, 3 m 36 n 3 S, where m1, m 2, m 3, n 1, n 2, n 3 Z, (3 m 1 6 n 1 3 m 2 6 n 2 ) 3 m 3 6 n 3 = 3 m 1+m 2 6 n 1+n 2 3 m 3 6 n 3 19 = 3 (m 1+m 2 )+m 3 6 (n 1+n 2 )+n 3 = 3 m 1+(m 2 +m 3 ) 6 n 1+(n 2 +n 3 ) = 3 m 1 6 n 1 3 m 2+m 3 6 n 2+n 3 = 3 m 1 6 n 1 (3 m 2 6 n 2 3 m 3 6 n 3 )

20 ˆ Identity: Since 0 Z, we have 1 = S and 1 is the multiplicative identity in S. ˆ Inverse: For any 3 m 6 n S, where m, n Z, since m, n Z, we have 3 m 6 n S and 3 m 6 n 3 m 6 n = 1 S. That is, 3 m 6 n has a multiplicative inverse in S. 補充. 其實也可以視為 S Q {0}, 用 subgroup test 就好, 這樣可以少證一個 associative 2.47* Prove that if G is a group with the property that the square of every element is the identity, then G is abelian. Proof. For any a, b G, since a 2 = b 2 = e, we have a = a 1 and b = b 1. (14) left multiplying a 1 left multiplying b 1 (14) e = (ab) 2 = abab a 1 = bab b 1 a 1 = ab ba = ab 2.49 Prove the assertion made in Example 20 that the set {1, 2,..., n 1} is a group under multiplication modulo n if and only if n is prime. 補充. 這我們之前講過了, 或是說, gcd (a, n) = 1 ax 1 (mod n) has a solution a has an inverse in Z n. gcd (a, n) = 1 x, y Z, such that ax + ny = 1 1 = ax + ny = ax U(n) a has an inverse in Z n In a finite group, show that the number of nonidentity elements that satisfy the equation x 5 = e is a multiple of 5. If the stipulation that the group be finite is omitted, what can you say about the number of nonidentity elements that satisfy the equation x 5 = e? 補充. Note that if x 0 is a solutaion of the equation x 5 = e, then x 0, x 2 0, x3 0, x4 0, x5 0 all are and x i 0 xj 0 for any i j {1, 2, 3, 4, 5}. 20

21 2.52 Let G = {[ a a a a ] a R, a 0}. Show that G is a group under matrix multiplication. Explain why each element of G has an inverse even though the matrices have 0 determinants. (Compare with Example 10.) 2.53 Suppose that in the definition of a group G, the condition that there exists an element e with the property ae = ea = a for all a in G is replaced by ae = a for all a in G. Show that ea = a for all a in G. (Thus, a one-sided identity is a two-sided identity.) 2.54 Suppose that in the definition of a group G, the condition that for each element a in G there exists an element b in G with the property ab = ba = e is replaced by the condition ab = e. Show that ba = e. (Thus, a one-sided inverse is a two-sided inverse.) 補充 2.A Let G be a set with an operation such that: 1. G is closed under. 2. is associative. 3. There exists an element e G such that e x = x for all x G. 4. Given x G, there exists a y G such that y x = e. Prove that G is a group. (Thus you must show that x e = x and x y = e for e, y as above.) (Abstract Algebra, Herstein, Section 2.2, Exercise 28) 補充. 這題比上面兩題更強, 所以你可以發現 group axiom 中的某些條件是多餘的, 也就是說可以由其他條件得到 這是比較進階的題目, 有興趣再做就好 3 Chapter For each group in the following list, find the order of the group and the order of each element in the group. What relation do you see between the orders of the elements of a group and the order of the group? 補充. C.f. p.148, Corollary 2. Z 12, U(10), U(12), U(20), D Prove that in any group, an element and its inverse have the same order. 提示. x n = e x n = e. Proof. Note that x n = e (x 1 ) n = x n = (x n ) 1 = e. If x < x 1, since x x = e, then (x 1 ) x = e, a contradiction. 補充. 簡單來說, 這題就是 x = x 1, 這個定理很重要, 直觀來看, 如果 x 2, 那麼 x 跟 x 1 就是成雙成對的 這題的應用包括 Exercise 2.20, 2.37, 3.5, Without actually computing the orders, explain why the two elements in each of the following pairs of elements from Z 30 must have the same order: {2, 28}, {8, 22}. Do the same for the following pairs of elements from U(15): {2, 8}, {7, 13}. 21

22 3.6 In the group Z 12, find a, b, and a + b for each case. a. a = 6, b = 2 b. a = 3, b = 8 c. a = 5, b = 4 Do you see any relationship between a, b, and a + b? 3.8 What can you say about a subgroup of D 3 that contains R 240 and a reflection F? What can you say about a subgroup of D 3 that contains two reflections? 3.9 What can you say about a subgroup of D 4 that contains R 270 and a reflection? What can you say about a subgroup of D 4 that contains H and D? What can you say about a subgroup of D 4 that contains H and V? 3.10 How many subgroups of order 4 does D 4 have? 提示. 如果一個 group G 的 order 是 4, 那麼他必定是由一個 order 是 4 的 element 所生成, 例如 Z 4 ; 或是由 3 個 order 2 的元素及一個 order 1 的元素 (identity) 構成, 其中任兩個 order 為 2 的元素相乘 ( 或相加 ) 會等於第三個 order 為 2 的元素, 例如 Z 2 Z Determine all elements of finite order in R, the group of nonzero real numbers under multiplication. Proof. ± If a and b are group elements and ab ba, prove that aba e. 補充. aba = e ba left right = a 1 = ab 3.13 Suppose that H is a nonempty subset of a group G that is closed under the group operation and has the property that if a is not in H then a 1 is not in H. Is H a subgroup? 3.14 Let G be the group of polynomials under addition with coefficients from Z 10. Find the orders of f(x) = 7x 5 +5x+4, g(x) = 4x 2 +8x+6, and f(x)+g(x) = x 2 +3x. If h(x) = a n x n +a n 1 x n 1 + +a 0 belongs to G, determine h(x) given that gcd (a 1, a 2,..., a n ) = 1; gcd (a 1, a 2,..., a n ) = 2; gcd (a 1, a 2,..., a n ) = 5; and gcd (a 1, a 2,..., a n ) = 10. Proof. f(x) = 10, g(x) = 5, f(x) + g(x) = 10. h(x) = 5 if gcd (a 1, a 2,..., a n ) = 2, 2 if gcd (a 1, a 2,..., a n ) = 5, 1 if gcd (a 1, a 2,..., a n ) = If a is an element of a group G and a = 7, show that a is the cube of some element of G. 22

23 補充. a 7 = 1, b 3 = a, consider in a. a = 7, b = a r, a 7 = 1, (a 7 ) r = a 7r = 1 a 7r+1 = a 3 (7r + 1) r = Suppose that H is a nonempty subset of a group G with the property that if a and b belongs to H then a 1 b 1 belongs to H. Prove or disprove that this is enough to guarantee that H is a subgroup of G Prove that if an Abelian group has more than three elements of order 2, then it has at least 7 elements of order 2. Find an example that shows this is not true for non-abelian groups. 3.18* Suppose that a is a group element and a 6 = e. What are the possibilities for a? Provide reasons for your answer. 提示. Division Algorithm. Proof. By division algorithm, If r 0, then 0 < r < a and 6 = a q + r for some q, r Z, where 0 r < a. e = a 6 = a a q+r = (a a ) q a r = a r, a contradiction. Thus, r = 0 and a divide 6. That is, a {1, 2, 3, 6} If a is a group element and a has infinite order, prove that a m a n when m n Let x belong to a group. If x 2 e and x 6 = e, prove that x 4 e and x 5 e. What can we say about the order of x? Proof. It immediately follows by Problem 3, x = 3 or Show that if a is an element of a group G, then a G Show that U(20) k for any k in U(20). [Hence, U(20) is not cyclic.] 3.24 Suppose n is an even positive integer and H is a subgroup of Z n. Prove that either every member of H is even or exactly half of the members of H are even. 補充. 2 H, 2 H 3.25 Prove that for every subgroup of D n, either every member of the subgroup is a rotation or exactly half of the members are rotations Prove that a group with two elements of order 2 that commute must have a subgroup of order For every even integer n, show that D n has a subgroup of order 4. 補充. {1, a n/2, b, ba n/2 }. 23

24 3.28 Suppose that H is a proper subgroup of Z under addition and H contains 18, 30, and 40. Determine H. Proof. gcd (18, 30, 40) = Suppose that H is a proper subgroup of Z under addition and that H contains 12, 30, and 54. What are the possibilities for H? 補充. 線性代數中的 span 3.30 Prove that the dihedral group of order 6 does not have a subgroup of order 4. 補充. There is no element in D 3 which is of order 4. Hence if there is a subgroup H of D 3 which is of order 4, then H must be a Klein four group. The elements in D 3 which is of order 2 are b, ba, ba 2. But {1, b, ba, ba 2 } is not a subgroup of D 3. C.f. p.148, Corollary 2. 補充. 學完 Lagrange s Theorem, 這題就很簡單了 3.31 For each divisor k > 1 of n, let U k (n) = {x U(n) x mod k = 1}. [For example, U 3 (21) = {1, 4, 10, 13, 16, 19} and U 7 (21) = {1, 8}.] List the elements of U 4 (20), U 5 (29), U 5 (30), and U 10 (30). Prove that U k (n) is a subgroup of U(n). Let H = {x U(10) x mod 3 = 1}. Is H a subgroup of U(10)? (This exercise is referred to in Chapter 8.) Proof. U 4 (20) = {1, 9, 13, 17}, U 5 (20) = {1, 11}, U 5 (30) = {1, 11}, U 10 (30) = {1, 11}. We show that U k (n) is a subgoup of U(n). ˆ Closed: a, b U k (n) a 1 (mod k), b 1 (mod k) ab 1 1 = 1 (mod k) ab U k (n). ˆ Identity: 1 mod k = 1 1 U(n) U k (n). ˆ Inverse*: a U k (n) U(n) a 1 U(n) gcd (a 1, n) = 1 k n gcd (a 1, k) = 1 a 1 U k (n). H is not a subgroup of U(10) because H = {1, 7} and 7 7 = 49 = 9 H. 24

25 3.32 If H and K are subgroups of G, show that H K is a subgroup of G. (Can you see that the same proof shows that the intersection of any number of subgroup of G, finite or infinite, is again a subgroup of G?) 提示. 記住 subgroup test 的口訣 : 閉單反 Proof. ˆ Closed: x, y H K x, y H, x, y K H,K G xy H, xy K xy H K. ˆ Identity: H, K G e G H, e G K e G H K. ˆ Inverse: x H K x H, x K H,K G x 1 H, x 1 K x 1 H K Show that Z(G) = a G C G (a). [This means the intersection of all subgroups of the form C G (a).] Proof. g Z(G) ga = ag for all a G g a G C G (a) Let G be a group, and let a G. Prove that C(a) = C(a 1 ). Proof. b C G (a) ba = ab a 1 (ba) = a 1 (ab) a 1 (ba) = b a 1 (ba)a 1 = ba 1 a 1 b = ba 1 b C G (a 1 ). g 1 C(a) 補充. If g C(a), then ga 1 = (ag 1 ) 1 = (g 1 a) 1 = a 1 g and g C(a 1 ) 25

26 3.36 Complete the partial Cayley group table given below. 補充. 6 = 5 2, 5 6 = Suppose G is the group defined by the following Cayley table a. Find the centralizer of each member of G. b. Find Z(G). c. Find the order of each element of G. How are these orders arithmetically related to the order of the group? 補充. C(a), Z(G) 在 Cayley Table 上如何表現? 3.38 If a and b are distinct group elements, prove that either a 2 b 2 or a 3 b 3. 補充. 這裡教各位一個很常用的證明技巧, 當你要證明 A (B or C) 時, 可以證明 在這題就是證明 A and ( B) C. a b, a 2 = b 2 a 3 b In the group Z, find a. 8, 14 ; b. 8, 13 ; c. 6, 15 ; d. m, n ; e. 12, 18, 45 ; In each part, find an integer k such that the subgroup is k. 26

27 3.41 For each a in a group G, the centralizer of a is a subgroup of G. Proof. Since ea = a = ae, we get e C G (a). If b, c C G (a), then Hecnce, bc C G (a). If b C G (a), then (bc)a = b(ca) c C G (a) c C G (a) = b(ac) = (ba)c = (ab)c = a(bc). right multiplying b 1 left multiplying b 1 ab = ba (ab)b 1 = (ba)b 1 ae = a = bab 1 b 1 a = ab 1 b 1 C G (a) If H is a subgroup of G, then by the centralizer C(H) of H we mean the set {x G xh = hx for all h H}. Prove that C(H) is a subgroup of G. Proof. ˆ Closed: x, y C(H) ˆ Identity: h H, (xy)h = x(yh) xy C(H). y C(H) x C(H) = x(hy) = (xh)y = (hx)y = h(xy) h H, e G h = h = he G e G C(H). ˆ Inverse*: x C(H) H G, h H,h 1 H x C(H) x 1 h = (h 1 x) 1 = (xh 1 ) 1 = hx 1 x 1 C(H) Must the centralizer of an element of a group be Abelian? 3.44 Must the center of a group be Abelian? 3.45 Let G be an abelian group with identity e and let n be some fixed integer. Prove that the set of all elements of G that satisfy the equation x n = e is a subgroup of G. Give an example of a group G in which the set of all elements of G that satisfy the equation x 2 = e does not form a subgroup of G. 27

28 Proof. Let S = {x G x n = e}. We claim that S is a subgroup of G. ˆ Closed: G abelian a, b S a n = e = b n (ab) n = a n b n = ee = e ab S. ˆ Identity: ˆ Inverse*: e n G = e e G S. a S (a 1 ) n = (a n ) 1 = e 1 = e a 1 S. In the case G = D 3 = { a, b a = 3, b = 2, ab = ba 1 }, S = {x G x 2 = e} = {e, b, ba, ba 2 }. S is not a subgroup of G because b ba = a S Suppose a belongs to a group and a = 5. Prove that C(a) = C(a 3 ). Find an element a from some group such that a = 6 and C(a) C(a 3 ). 補充. See p.67, Example Let G be the set of all polynomials with coefficients from the set {0, 1, 2, 3}. We can make G a group under addition by adding the polynomials in the usual way, except that we use modulo 4 to combine the coefficients. With this group operation, determine the orders of the elements of G. Determine a necessary and sufficient condition for an element of G to have order In each case, find elements a and b from a group such that a = b = 2. a. ab = 3 b. ab = 4 c. ab = Suppose a group contains elements a and b such that a = 4, b = 2, and a 3 b = ba. Find ab. 3.50* Suppose a and b are group elements such that a = 2, b e, and aba = b 2. Determine b. Proof. We show that b 2 e. left multiplying a right multiplying a aa=e If b 2 = e aba = b 2 = e aaba = a aabaa = aa b = e, a contradiction. 28

29 蔡 諭, 沈 慧的解法 : Therefore, b 4 = b and b 3 = e and b = 3. 袁 隆的解法 : aba = b 2 left multiplying a aaba = ab 2 right multiplying a aa=e left multiplying a right multiplying a b 4 = (b 2 )(b 2 ) aabaa = ab 2 a b = ab 2 a = (aba)(aba) = ab(aa)ba aa=e = ab 2 a aba=b 2 = a(aba)a = (aa)b(aa) aa=e = b. b 2 = (ab 2 a) 2 = (ab 2 a)(ab 2 a) = ab 2 (aa)b 2 a aba = b 2 = ab 4 a aaba = aab 4 a aa=e b = b 4. aabaa = aab 4 aa aa=e = ab 4 a Therefore, b 4 = b and b 3 = e and b = Let a be a group element of order n, and suppose that d is a positive divisor of n. Prove that a d = n/d. 補充. 建議你直接背 p.80, thm.4.2 的公式 : If a = n, then a r n = gcd (r,d), 這是更強的版本, 不用要求 r n 證明也很簡單, 類似國小的兩個人跑操場, 不同起點, 同時抵達終點的問題 下面是助教我以前大學時記下這個公式的方法, 注意到 r 跟 n 分別都有一個在上一個在下 g r r = gcd (r, n) 3.52 Consider the elements A = [ ] and B = [ A, B, and AB. Does your answer surprise you? ] from SL(2, R). Find 29

30 Proof. A = 4, B = 3, AB = Consider the element A = [ ] in SL(2, R). What is the order of A? If we view A = [ ] as a member of SL(2, Z p) (p is a prime), what is the order of A? Proof. A = { if A SL(2, R), p if A SL(2, Z p ) For any positive integer n and any angle θ, show that in the group SL(2, R), n cos θ sin θ [ sin θ cos θ ] cos nθ sin nθ = [ sin nθ cos nθ ]. Use this formula to find the order of [ cos 60 sin 60 2 sin 2 sin 60 cos 60 ] and [cos sin 2 cos 2 ]. (Geometricall, [ cos θ sin θ sin θ ] represents a rotation of the plane θ degree.) cos θ 3.56 Let x belong to a group and x = 6. Find x 2, x 3, x 4, and x 5. Let y belong to a group and y = 9. Find y i for i = 2, 3,..., 8. Do these examples suggest and relationship between the order of the power of an element and the order of the element? 補充. 事實上, 我們有 a r = 這蠻難證的, 有興趣的同學可以挑戰看看 3.57 D 4 has seven cyclic subgroups. List them U(15) has six cyclic subgroups. List them. Proof. 1 = {1}, n gcd (n, r). 2 = {1, 2, 4, 8}, 4 = {1, 4}, 7 = {1, 7, 7 2 = 4, 7 3 = 13}, 11 = {1, 11}, 14 = {1, 14}. 30

31 3.59* Prove that a group of even order must have an element of order 2. Proof. Consider the set S = {x G x 2 = e}. Since x = x 1, if x 3, then x and x 1 are two distinct elements that they have the same order. Thus, there are even number of elements in G/S and the number of elements in S are even. Since e S, there is an element x 0 S such that x 0 e and x 2 0 = e. 胡 瑋的解法 : Define a relation on the group G of even order by a b a = b or a = b 1. Then show that is an equivalence relation. In addition, show that the number of elements in each equivalence class is either 1 or 2 and the equivalence class which contains the identity is {e}. 其他 idea( 未證明 ): Let G = {g 1, g 2,..., g n } be a group, where n is an even number. Let Perm G be the set of all permutation on the set G. Show that the mapping σ G G defined by σ(g) = g 1 is a permutation. That is, σ Perm G. Define a mapping θ Perm G S n. If τ Perm G and τ(g i ) = g j, then θ(τ)(i) = j. Show that θ is well-define and θ(σ) is a product of disjoint tranpositions. If g 1 = e, then θ(σ)(1) = 1. Since n is even and θ(σ) is a product of disjoint tranpositions, there must exists j 1 such that θ(σ)(j) = j. That is, σ(g j ) = g j and gj 1 = g j and g j = 2. Proof. Note that x 2 e x x 1. Let S = {x G x 2 e}. Pick x 1 e S. Then x 1 x 1 1 and x 1 1 S (why? 1 ). Remove these two elements x 1 and x 1 1 from S. Pick x 2 from the remaining elements, do the same process as above. We can always remove two elements because x 1 i x 1 j S if i j. Since G is finite, we can t do the process infinitely. Finally, there is no element remain in S. Thus, S = {x 1, x 1 1, x 2, x 1 2,,,,, x n, x 1 n } and #S is even. Since G is even, we get #(G S) is even and there exists g e G S and g = 2. 補充. ˆ 這題跟 2.20 有什麼關係? ˆ 之後學到 group action 會知道這題只是 Cauchy s Theorem 的一個特例 3.60 Suppose G is a group that has exactly eight elements of order 3. How many subgroups of order 3 does G have? 1 可以直接證也可以用 x = x 1 31

32 Proof. Suppose that a 1 is an element of order 3 in G. Then a 2 1 = 3 and a2 1 a 1. By a similar argument, {a 1, a 2 1, a 2, a 2 2, a 3, a 2 3, a 4, a 2 4 } are all the eight elements of order 3. There are 4 subgroups of order 3. They are H 1 = {e, a 1, a 2 1}, H 2 = {e, a 2, a 2 2}, H 3 = {e, a 3, a 2 3}, H 4 = {e, a 4, a 2 4} Let H be a subgroup of a finite group G. Suppose that g belongs to G and n is the smallest positive integer such that g n H. Prove that n divides g. 補充. By Division Algorithm, suppose that g = n q + r for some integer q and 0 r < n. If r 0, then e = g g = g n q+r = (g n ) q g r and g r = (g n ) q H. Contrary to the minimality of n. Therefore, r = 0 and n divides g Compute the orders of the following groups. a. U(3), U(4), U(12) b. U(5), U(7), U(35) c. U(4), U(5), U(20) d. U(3), U(5), U(15) On the basis of your answers, make a conjecture about the relationship among U(r), U(s), and U(rs). 補充. 這個以後再講, 在這裡先算就好, 要證明的話要用到一些進階的工具 3.63 Let R be the group of nonzero real numbers under multiplication and let H = {x R x 2 is rational}. Prove that H is a subgroup of R. Can the exponent of 2 be replaced by any positive integer and still have H be a subgroup? 3.64 Compute U(4), U(10), and U(40). Do these groups provide a counterexample to your answer to Exercise 62? If so, revise your conjecture Find a cyclic subgroup of order 4 in U(40) Find a noncyclic subgroup of order 4 in U(40). 補充. {1, 9, 11, 19} Let G be a group of functions from R to R, where the operation of G is multiplication of functions. Let H = {f G f(2) = 1}. Prove that H is a subgroup of G. Can 2 be replaced by any real number? Proof. ˆ Closed: x, y H (xy)(2) = x(2) y(2) x,y H = 1 1 = 1 xy H. 32

33 ˆ Identity: ˆ Inverse: x H x 1 (2) 1 G (2) = 1 1 G H. x(2)>0 = [x(2)] 1 = 1 1 = 1 x 1 H Let G = GL(2, R) and H = {[ a 0 ] a and b are nonzero integers} under the operation of matrix multiplication. Prove or disprove that H is a subgroup of GL(2, 0 b R). Proof. ˆ Closed: [ a 0 0 b ], [c 0 ] H a, b, c, d all are not 0 0 d ac 0, bd 0 [ a 0 0 b ] [c 0 0 d ] = [ac 0 0 bd ] H. ˆ Identity: 1 0 [ ] = e G H. ˆ Inverse: [ a ] H a 0, b 0 [a 0 b 0 b ] = [ a b 1] H Let H = {a + bi a, b R, a 2 + b 2 = 1}. Prove or disprove that H is a subgroup of C under multiplication. Describe the elements of H geometrically. Proof. ˆ Closed: a + bi, c + di H a 2 + b 2 = 1 = c 2 + d 2 (a 2 + b 2 )(c 2 + d 2 ) = a 2 c 2 + b 2 c 2 + a 2 d 2 + b 2 d 2 = 1 1 = 1 (ac bd) 2 + (bc + ad) 2 = 1 (a + bi)(c + di) = (ac bd) + (bc + ad)i H. ˆ Identity: 1 = 1 + 0i, = 1 1 H. 33

34 ˆ Inverse: a + bi H a 2 + b 2 = 1 2 a ( a 2 + b ) 2 (a + bi) 1 = + ( b a 2 + b 2 ) 2 = 1 a a 2 + b 2 + b a 2 + b 2 H. The geometric interpretation of H is the unit circle in the complex plane. 類似 3.73 Let H = {a + bi a, b R, a 2 + b 2 = 1}. Prove or disprove that H is a subgroup of C under multiplication. Describe the elements of H geometrically. Proof. Since 1 = 1 + 0i and = 1, we get 1 H. If a + bi, c + di H, then a 2 + b 2 = 1 = c 2 + d 2 and (a 2 + b 2 )(c 2 + d 2 ) = a 2 c 2 + b 2 c 2 + a 2 d 2 + b 2 d 2 = 1 1 = 1. Therefore, (ac bd) 2 + (bc + ad) 2 = 1 and (a + bi)(c + di) = (ac bd) + (bc + ad)i H Let G be a finite Abelian group and let a and b belong to G. Prove that the set a, b = {a i b j i, j Z} is a subgroup of G. What can you say about a, b in terms of a and b? 3.77 Let a belong to a group and a = m. If n is relatively prime to m, show that a can be written as the nth power of some element in the group. 補充. a = a 1 = a gcd (m,n) = a mx+ny = (a m ) x + (a y ) n = (a y ) n. Compare to Section 4, Exercise Let F be a reflection in the dihedral group D n and R a rotation in D n. Determine C(F ) when n is odd. Determine C(F ) when n is even. Determine C(R) Let G = GL(2, R). a. Find C ([ ]). b. Find C ([ ]). c. Find Z(G). Proof. Let B = [ ]. 34

35 C G (B) = {[ a b b ] GL(2, R) [a c d c d ] [ ] = [ ] [a b ], ad bc 0} c d = {[ a b ] GL(2, R b = c, a = d, ad bc 0} c d = {[ a b b a ] GL(2, R) a2 b 2 0} Let By a similar argument, A = [ ]. C G (A) = {[ a b b a b ] GL(2, R) a2 ab b 2 0} Therefore, Z(G) C G (A) C G (B) = {[ a 0 0 a ] GL(2, R) a2 0} = S. It is easy to show that S Z(G). Hence, Z(G) = S. 補充. See Exercise 33. Z(G) C(a) C(b) Let G be a finite group with more than one element. Show that G has an element of prime order. 補充. Show that a <. Suppose a = p r 1 1 pr 2 2 prn n. Then consider a pr p r 2 2 p rn n. 補充 3.A Let G = {z C z n = 1 for some n Z + }. (a) Prove that G is a group under multiplication (called the group of roots of unity in C). Proof. For any z 1, z 2 G, suppose that z n 1 1 = z n 2 2 = 1 for some n 1, n 2 Z +. Then (z 1 z 2 ) n 1n 2 = (z n 1 1 )n 2 (z n 2 2 )n 1 = 1 1 = 1. That is, z1 z 2 G. Obviously, 1 1 = 1 so 1 G. In addition, ( 1 z 1 ) n 1 = 1 z n 1 = 1. Thus, z1 1 G. The associative of the 1 multiplication on G inherited from the multiplication on C. Therefore, G is a group under multiplcation. (b) Prove that G is not a gorup under addition. Proof. Note that 1 G but = 2 is not in G because 2 n 1 for any n Z +. Hence, G is not closed under addition. 35

36 4 Chapter List the elements of the subgroups 3 and 15 in Z 18. Let a be a group element of order 18. List the elements of the subgroups a 3 and a 15. Proof. By Exercise 4.11, 3 = 3 = 15 = {0, 3, 6, 9, 12, 15}. a 3 = a 3 = a 15 = {1, a 3, a 6, a 9, a 12, a 15 }. 4.5 List the elements of the subgroups 3 and 7 in U(20). Proof. 3 = 7 = {1, 3, 9, 7}. 4.9 How many subgroups does Z 20 have? List a generator for each of these subgroups. Suppose that G = a and a = 20. How many subgroups does G have? List a generator for each of these subgroups. Proof. Z 20 a 2 5 a 2 a a 4 a 10 0 a 0 = Let G = a and let a = 24. List all generators for the subgroup of order 8. Proof. By the formula of the order of the element in a finite cyclic group, we know that a m 24 = gcd (m,24). It is sufficient to find m such that gcd (m, 24) = 3. Then a m 24 = gcd (m,24) = 8. By some computation, m {3, 9, 15, 21}. That is, the generators for the subgroup of order 8 are a 3, a 9, a 15 and a Let G be a group and let a G. Prove that a 1 = a In Z 24 find a generator for Suppose that a = 24. Find a generator for a 21 a 10. In general, what is a generator for the subgroup a m a n? Proof. 你當然可以直接算 21 跟 10, 但這裡我教你一些技巧 36

37 Exercise 4.11 ˆ 21 = 3 = 3 = {0, 3, 6, 9, 12, 15, 18, 21}. p.80, thm ˆ Since 10 = 10 = gcd (10,24) Cyclic Groups, there is only one subgroup of order 12. Thus, = 12, by the Fundamental Theorem of 10 = 2 = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22}. ˆ Then = 3 2 = 6. Similarly, a 21 a 10 = a 3 a 2 = a 6. In general, a m a n = a r, where r = l.c.m.(gcd (m, 24), gcd (n, 24)). 補充. 解答有誤 4.14 Suppose that a cyclic group G has exactly three subgroups: G itself, {e}, and a subgroup of order 7. What is G? What can you say if 7 is replaced with p where p is a prime? 提示. Fundamental Theorem of Cyclic Groups. Proof. By the Fundamental Theorem of Cyclic Groups, G = Z 49. Z 49 has exactly three subgroup: Z 49, 7 and {0}. G = 49. If 7 is replaced with a prime p, then G = Z p 2. Proof. 這題如果要嚴謹證明的話, 要用到一些還沒教過的觀念 ˆ At first, we need to prove that G is finite. See Hungerford, p.37, exe.i.4.8. ˆ Recall that the Fundamental Theorem of Cyclic Groups states that: If G is a cyclic group of finite order, then the order of every subgroup of G divides G and for each divisor k of G, there is only one subgroup H of G such that H = k. ˆ If G has exactly three subgroups G, H and {0}, where H = 7, then by the Fundamental Theorem of Cyclic Groups, G = 49. ˆ If G is cyclic and G = 49, then G Z 49. ˆ If 7 is replaced with a prime p, then G = Z p Find a collection of distinct subgroups a 1, a 2,..., a n of Z 240 with the property that a 1 a 2 a n with n as large as possible. Proof List the cyclic subgroups of U(30). 37

38 Proof. 1 = {1}, 7 = {1, 7, 19, 13}, 17 = {1, 17, 19, 23}, 11 = {1, 11}, 19 = {1, 19}, 29 = {1, 29} Let G be a cyclic group with G = 24, and let a G. If a 8 e and a 12 e, show that a = G. (Hint: consider a and G.) Proof. By the Lagrangle s Theorem, a divide G = 24. Recall that if a divide n, then a n = e. Equivalently, if a n e, then a n. Hence, a 8 e and a 12 e implies that a {1, 2, 3, 4, 6, 8, 12}. Therefore, a = 24 and G is a cyclic group generated by a. That is, G = a For any element a in any group G, prove that a is a subgroup of C G (a). Proof. a is already a subgroup of G. It is sufficient to show that a C G (a). If a m a, then a m a = a m+1 = a a m. That is, a m C G (a) Find all generators of Z. Let a be a group element that has infinite order. Find all generators of a. Proof. ±1, a ± Prove that C, the group of nonzero complex numbers under multiplication, has a cyclic subgroup of order n for every positive integer n. 提示. 回想高中學的 z n = 1 Proof. ω n, where ω n = e 2π n i = cos 2π n + i sin 2π n Let a be a group element that has infinite order. Prove that a i = a j if and only if i = ±j. Proof. ( ) By Exercise

39 () a i = a j a i a j a i = (a j ) q 1 for some q 1 Z a i jq 1 = e a = i jq 1 = 0 i = jq 1 Similar j = iq 2 for some q 2 Z i = jq 1 = iq 1 q 2 i(q 1 q 2 1) = 0 If i = 0 j = 0 = i If q 1 q 2 1 = 0 q 1 q 2 = 1 q 1 = ±1 i = ±j 4.30* Suppose a and b belong to a group, a has odd order, and aba 1 = b 1. Show that b 2 = e. 提示. aba 1 = b 1 bab = a. Let x = ba = ab 1. Then x 2 = = a 2. Suppose a = 2n + 1. Then x 2n+1 = = b. Therefore, b 2 = x 4n+2 =. Proof. aba 1 = b 1 implies that ba = ab 1. Let x = ba = ab 1. Then x 2 = (ab 1 )(ba) = a 2. Suppose that a = 2n + 1. Then x 2n+1 = x (x 2 ) n = x (a 2 ) n = (ba) (a 2 ) n = b a 2n+1 = b. Therefore, b 2 = (x 2n+1 ) 2 = (x 2 ) 2n+1 = (a 2 ) 2n+1 = (a 2n+1 ) 2 = e Let G be a finite group. Show that there exists a fixed positive integer n such that a n = e for all a in G. (Note that n is independent of a.) 提示. Consider a = {a, a 2, a 3,...}. 補充. 學過 Lagrange s Theorem 之後, 這題會變得很簡單 Proof. Let G = {a 1, a 2,..., a s }. Since G is finite, for i = 1, 2,..., s, a i = {a i, a 2 i, a3 i,...} is finite. Hence, a j i = a k i for some ji > k i and a j i k i = e. Let n = l.c.m.(j1 k 1, j 2 k 2,..., j s k s ). 39