### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Calif Government & Politics POLI 103A

GPA 3.81

### View Full Document

## 49

## 0

## Popular in Course

## Popular in Political Science

This 68 page Class Notes was uploaded by Boris Kuhn on Thursday October 22, 2015. The Class Notes belongs to POLI 103A at University of California - San Diego taught by Staff in Fall. Since its upload, it has received 49 views. For similar materials see /class/226806/poli-103a-university-of-california-san-diego in Political Science at University of California - San Diego.

## Reviews for Calif Government & Politics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15

Part II Math 103A Lecture Notes 1 Lecture 1 152009 Notation 11 Introduce N 2 012 Z Q R and C Also let Z I N 0 Set notations o Recalled basic notions of a function being one to one onto and invertible Think of functions in terms of a bunch of arrows from the domain set to the range set To nd the inverse function you should reverse the arrows 0 Some example of groups without the de nition of a group llGL2lR g2 detgad7bc7 0l a c d 2 Vector space with group operation being addition 3 The permutation group of invertible functions on a set S like S l2ln 11 A Little Number Theory Axiom 12 Well Ordering Principle Every nonempty subset S of N contains a smallest element We say that a subset S C Z is bounded below if S C hoo for some h E Z and bounded above if S C 700 h for some h E Z Remark 13 Well ordering variations The well ordering principle may also be stated equivalently as 1 any subset S C Z which is bounded from below contains a smallest element or 2 any subset S C Z which is bounded from above contains a largest elementl To see this suppose that S C hoo and then apply the well ordering principle to S 7 h to nd a smallest element n E S 7 hi That is n E S 7 h and n S 37h for all s E S Thus it follows that nh E S and nh S s for all s E S so that n h is the desired smallest element in S For the second equivalence suppose that S C 700 h in which case 7S C 716 00 and therefore there exist a smallest element n E 7S iel n S 7s for all s E S From this we learn that 7n E S and 7n 2 s for all s E S so that 7n is the desired largest element of S Theorem 14 Division Algorithm Let a E Z and b C Z1 then there exists unique integers q E Z and r E N with r lt I such that a 124 r For example 5E so that 12 2 5 2 7 Proof Let ShEZa7bh20 which is bounded from above Therefore we may de ne qz maxha7bh20l As 4 is the largest element of S we must have ra7bqZOandaibq1 lt0 The second inequality is equivalent to r 7 b lt 0 which is equivalent to r lt 12 This completes the existence proof To prove uniqueness suppose that a bq r in which case bq r bqr and hence bgtlT iillb474 lblq74 l 11 Since 47 qquot 2 1 if q f q the only way Eq 11 can hold is if q q and r r l l Axiom 15 Strong form of mathematical induction Suppose that S C Z is a nonempty set containing an element a with the property that if an ZC S thenn E Z then aoo ZC S Axiom 16 Weak form of mathematical induction Suppose that S C Z is a nonempty set containing an element a with the property that for ev erynES withnZanl S then aoo ZCSl Remark 17 In Axioms 15 and 16 it suf ces to assume that a 0 For if a f 0 we may replace 5 by S 7 a I s 7 a z s E S Then applying the axioms with a 0 to S 7 a shows that 000 N Z C S 7 a and therefore aoo Z0oo ZaCSi Theorem 18 Equivalence of Axioms Axioms 12 7 16 are equivalent Only partially covered in class Proof We will prove 12 ltgt 15 ltgt 1 6 gtli2i liZ liS Suppose 0 E S C Z satis es the assumption in Axiom 15 If No is not contained in S then N0 S is a non empty subset of N and therefore has a smallest element n It then follows by the de nition of n that 0 n Z C S and therefore by the assumed property on S n E S This is a contradiction since n can not be in both 5 and N0 5 15 gtli2 Suppose that S C N does not have a smallest element and let Q I NSi Then 0 E Q since otherwise 0 E 5 would be the minimal element of 5 Moreover if 1n N Z C Q then n E Q for otherwise n would be a minimal element of 5 Hence by the strong form of mathematical induction it follows that Q N and hence that S 0 15 gtli6 Any set S C Z satisfying the assumption in Axiom 16 will also satisfy the assumption in Axiom 1 5 and therefore by Axiom 15 we will have aoo N Z C 5 16 gtli5 Suppose that 0 E S C Z satis es the assumptions in Axiom 15 Let Q I n E N 0n C 5 By assumption 0 E Q since 0 E 5 Moreover if n E Q then 0n C S by de nition of Q and hence n 1 E Thus Q satis es the restrictions on the set S in Axiom 16 and therefore Q Ni So ifn E N then n16 N Q and thus n E 0nl C Swhich shows that N C 5 As 0 E S by assumption it follows that No C S as desired 2 Lecture 2 172009 De nition 21 Given ab E Z with a f 0 we say that a divides b or a is a divisor ofb write alb provided b ah for some h E Z De nition 22 Given ab E Z with lal lbl gt 07 we let god a7 12 max m mla and mlb be the greatest common divisor ofa and b We do not de ne god 00 and we have god 012 lbl for all I E Z 0 If god ab 1 we say that a and b are relatively prime Remark 23 Notioe that god ab god lal 2 0 and god a0 0 for all a f 0 Lemma 24 Suppose that ab E Z with I f 0 Then god a 161212 god ab for all h E Z Proof Let 5k denote the set of oommon divisors of a kl and 12 1f d E 5k then dlb and dl a lob and therefore dla so that d 6 50 Conversely if d 6 So then dlb and dla and therefore dlb and dl a lob ile d E 5k This shows that 5k 50 ie a kl and b and a and b have the same oommon divisors and henoe the same greatest oommon divisorsl I This lemma has a very useful oorollaryl Lemma 25 Euclidean Algorithm Suppose that ab are positive integers with a lt b and let I ha r with 0 S r lt a by the division algorithm Then god ab god ar and in particular ifr 07 we have god a7 12 god a7 0 al Example 26 Suppose that a 15 3 5 and b 28 22 7 In this oase it is easy to see that god 1528 1i Nevertheless7 lets use Lemma 25 repeatedly as follows 28 1 15 13 so god 157 28 god 137 15 21 15 1 132 so god 1315 god 213 22 13621 so Ggod213god127 23 2210 so god12god011l 24 Moreover making use of Eqs 21723 in reverse order we learn that7 1 13 7 6 2 13761571137137615 7287115761572871315l Thus we have also shown that 1s28t15wheres7andt713 The ohoioes for s and t used above are oertainly not unique For example we have7 0152872815 which added to 172871315 implies7 1 715287 1328 15 222874115 as well Example 27 Suppose that a 40 23 5 and b 52 2213 In this oase we have god 407 52 4 Working as above we nd7 5214012 403124 12340 so that we again see god 4052 4i Moreover7 440731240735271404407352 So again we have shown god a7 12 sa tb for some st E Z7 in this oase s 4 and t 3i 12 2 Lecture 2 172009 Example 28 Suppose that a 333 32 37 and b 459 33 17 so that god 333 459 32 9 Repeated use of Lemma 215 gives 459 1 333 126 so god 333 459 god 126333 215 333 2 126 81 so god 126 333 god 81 126 216 126 81 45 so god 81126 god 4581 27 81 45 36 so god 4581 god 3645 218 45 36 9 so god 3645 god 9 36 and 219 36 490 so god 936 god 09 91 2110 Thus we have shown that god 333 459 91 We oan even say more From Eq1 2110 we have 9 45 7 36 and then from Eq1 2110 945736457817452457811 Continuing up the ohain this way we learn 9212678178121267381 21267333372126812673333 845971333733338459711333 so that 984597113331 The methods of the previous two examples oan be used to prove Theorem 219 below1 However we will two different variants of the proof Theorem 29 lfab E Z 0 then there exists not unique numbers st E Z such that god ab satb1 2111 Moreover if m f 0 is any common divisor of both a and b then ml god a b 1 Proof If m is any oommon divisor of a and b then m is also a divisor of sa tb for any st E Z In partioular this proves the seoond assertion given the truth of Eq1 211 In partioular god a b is a divisor of sa tb for all st E Z Let S sa tb st E Z and then de ne d 2 min S N Z sa tb for some st E Z 2112 By what we have just said if follows that god a b ld and in partioular d 2 god a b 1 If we oan snow d is a oommon divisor of a and b we must then have d god a b 1 However using the division algorithm Page 12 job algebra ahdrwith0 rltd1 2113 As ra7hda7hsatb 17hsa7htb6 S N if r were greater than 0 then r 2 d from the de nition of d in 2112 whioh would oontradiot Eq1 21131 Henoe it follows that r 0 and dla1 Similarly one shows that dlb1 l Lemma 210 Euclid s Lemma If god c a 1 ie c and a are relatively prime and clab then c1121 Proof We know that there exists st E Z suoh that satc 11 Multiplying this equation by 12 implies sab tcb b1 Sinoe clab and clcb it follows from this equation that c1121 l Corollary 211 Suppose that ab E Z such that there exists st E Z with 1 sad tb1 Then a and b are relatively prime ie god a b 11 Proof If m gt 0 is a divisor of a and b then ml sa tb i1e1 ml1 whioh implies m 11 Thus the only positive oommon divisor of a and b is 1 and henoe I god a b 11 21 Ideals Not covered in class De nition 212 As nonempty subset S C Z is called an ideal if S is closed under addition ie S S C S and under multiplication by any element of Z ie Z S C S Example 213 For any n E Z let nZnnZhn hEZ1 l is easily oheoked that is an ideal The next theorem states that this is a listing of all the ideals of Z Theorem 214 Ideals of Z If S C Z is an ideal then S for some n E Z Moreover either S 0 in which case n 0 for S f 0 in which case n minS Z1 Proof If S 0 we may take it 01 So we may assume that S oontains a nonzero element a1 By assumption that Z S C S it follows that 7a E S as well and therefore S Z is not empty as either a or 7a is positive By the well ordering prinoiple we may de ne it as n 2 min S N Z1 macro svmonob cls datetime 13Mar20099 O4 Since Z n C Z S C 5 it follows that C 5 Conversely suppose that s E 5 Zl By the division algorithm 8 kn T where k E N and 0 S T lt n It now follows that T s 7 kn E S If T gt 0 we would have to have T 2 n minS Z and hence we see that T 0 This shows that s kn for some k E N and therefore 8 E lf 8 E S is negative we apply what we have just proved to is to learn that is E and therefore 8 E n l l RemaTk 215 Notice that all iff b ak for some k E Z which happens iff b E a Proof Second Proof of Theorem 29 Let S satb st E Z One easily checks that S C Z is an ideal and therefore 5 d where d I minS Zl Notice that d 3a tb for some st E Z as d E S We now claim that d gcd abl To prove this we must show that d is a divisor of a and b and that it is the maximal such divisorl Takings l andt Oors Oandt lwelearnthat bothab6 S d ilel dla and dlbl If m E Z and mla and mlb then i 82 t3 E Z m m m from which it follows that so that mldl This shows that d gcd ab and also proves the last assertion of the theoreml Alternate proof of last statement If mla and mlb there exists kl E Z such that a km and b lm and therefore dsatb sktlm which again shows that mldl l RemaTk 216 As a second proof of Corollary 211 if 1 E S where S is as in the second proof of Theorem 29 then gcd ab min 5 Z ll 3 Lecture 3 192009 31 Prime Numbers De nition 31 A number p E Z7 is prime i p 2 2 and p has no divisors other than 1 and p Alternatively put p 2 2 and god ap is either 1 or p for all a E Z Example 32 The rst few prime numbers are 27 37 57 7111317197 237 Lemma 33 Euclid s Lemma again Suppose that p is a prime number and plab for some a7 b E Z then pla or plb Proof We know that god ap 1 or god a7 p p In the latter oase pla and we are done In the former oase we may apply Euolidls Lemma 210 to oonolude that plb and so again we are done I Theorem 34 The fundamental theorem of arithmetic Every n E Z with n 2 2 is a prime or a product of primes The product is unique except for the order of the primes appearing the product Thus 2 2 and n p1 pn ql Han where the p s and q s are prime then m n and after renumbering the q s we have pi qil Proof Existence This olearly holds for n 2 Now suppose for every 2 S h S n may be written as a produot of primesl Then either n1 is prime in whioh oase we are done or n1 a b with 1 lt ab lt n1l By the induotion hypothesis7 we know that both a and b are a produot of primes and therefore so is n 1 This oompletes the induotive stepl Uniqueness You are asked to prove the uniqueness assertion in 025l Here is the solution Observe that pllq1 lqml 1f p1 does not divide ql then god pl7 ql 1 and therefore by Euolidls Lemma 2 107 pll qg gm It now follows by induotion that p1 must divide one of the qi by relabeling we may assume that ql p1 The result now follows by induotion on n V ml l De nition 35 The least common multiple of two nonzero integers a7 b7 is the smallest positive number which is both a multiple of a and b and this number will be denoted by lom a7 b Notice that m min a N b N Z Example 36 Suppose that a 12 223 and b 15 35l Then god 127 15 ile lom1215 223 52235 2235 60 Observe that god1215lom1215 3 2235 223 35 1215 This is a speoial oase of Chapter 012 on p 23 whioh oan be proved by similar Considerations In general if pp pk andbprl mpg with 71W 6N then goat palm 3le and 1cmltabgt 201 va WW Therefore7 godab lomab Pilmm mvml 39 39 39 39 39pZMWTnkWLk p1m1pzkmk a b 32 Modular Arithmetic De nition 37 Let n be apositive integer and let a ganra with 0 S ra lt n Then we de ne amodn I ral Sometimes we might write a ra modn 7 but I will try to stick with the rst usage Lemma 38 Let n E Z1 and ab7 h E Z Then 1 a kn modn amodnl 2 ab modn amodnbmodnmodn 5 a b modn a modn b modn modnl Proof Let ra amod n7 rb bmodn and 4145 6 Z suoh that a qanra and b mm rbl 16 3 Lecture 3 192009 11 Then a kn 4a k n Ta and therefore a kn modn Ta amodnr 21 a b qa 41 n Ta T5 and hence by item 1 with k qa 45 we find a b modn Ta Tb mod n a modn 12 mod n mod n1 3 For the last assertion a b Lian M mm Tb qaqbn ram qua n Ta Tb and so again by item 11 with k qaqbn Taqb qua we have a b modn Ta Tb modn amodn bmodn modnr I Example 39 Take n 4 a 18 and b 71 Then 18 mod4 2 and 7mod4 31 On one hand 18 7 mod4 25 mod4 1 while on the other 2 3 mod4 11 Similarly 187 126 4 31 2 so that 18 7 mod4 2 while 2 3 mod4 6mod4 21 Remark 310 Error Detection Companies often add extra digits to identi fication numbers for the purpose of detecting forgery or errors For example the United Parcel Service uses a mod 7 check digitr Hence if the identi cation number were n 354691332 one would append nmod7 354691332 mod7 2 to the number to get 3546913322 say See the book for more on this method and other more elaborate check digit schemesr Note 354691332 50670190 7 21 Remark 311 Suppose that a n E Z and b E Z then it is easy to show you prove ab mod an a 12 mod n Page 16 job algebra Example 312 Computing mod10 We have 123456 mod 10 6 123456 mod 100 56 123456 mod 1000 456 123456 mod 10000 3456 123456 mod 100000 23456 123456 mod 1000000 123456 so that an rag almod10k ak rag al for all k S n Solution to Exercise 052 As an example here is a solution to Problem HR 052 of the book which states that 111 r r r 1 is not the square of an integer except whenk1r As 11 is prime we may assume that k 2 31 By Example 312 111rrr1mod10 1 and 111rrr1mod100 111 Hence 11111111 n for some integer n we must have n2 mod10 1 and n2 1mod100 10 The first condition implies that nmod10 1 or 9 as 12 1 and 92 mod 10 81 mod10 1 1n the first case we have n k 10 1 and therefore we must require 10 n2 1mod100 k 1012 71 mod100 k2 100 2k10mod100 2k 10 mod100 10 2kmod10 which implies 1 2k mod 10 which is impossible since 210 mod 10 is even For the second case we must have 10 n2 1mod100mod100 10 10 92 1 mod100 k2 100 18k 10 81 1 mod100 108k 108 10 mod100 8 k 1 10 mod100 10 8k mod 10 which implies which 1 8k mod 10 which again is impossible since 810 mod 10 is even macro svmonob cls datetime 13Mar20099O4 Solution to Exercise 052 Second and better solution Notice that 111Hl11111 l00 11 and therefore 111 l11mod4 11mod4 3 On the other hand if111 11 n2 we must have nmod42 mod4 3 There are only four possibilities for r I nmod 4 namely r 0 1 2 3 and these are not allowed since 02 mod4 0 f 3 12 mod4 1 322 mod4 0 f 3 and 32 mod4 1 f 3 3 3 Equivalence Relations De nition 313 A equivalence relation on a set S is a subset R C S X S with the following properties 1 R is re exive aa E R for all a E S 2 R is symmetric If a b E R then b a E R 5 R is transitive If a b E R and bc E R then ac E R We will usually write a N b to mean that ab E R and pronounce this as a is equivalent to 12 With this notation we are assuming a N a a N b gt b N a and a N b and b N c gt a N c Note well the book write aRb rather than a N 12 Example 3141fS 12345 then 1 R 1232 U 452 is an equivalence relation 2 R 1 1 22 3 3 44 55 1 2 21 2 3 32 is not an equivalence relation For example 1 N 2 and 2 N 3 but 1 is not equivalent to 3 so R is not transitive Example 315 Let n E Z S Z and say a N 1 iff amodn bmodnl This is an equivalence relation For example when 8 2 we have a N 1 iff both a and b are odd or event So in this case R odd2 U even Example 316 Let S R and say a N 1 iff a 2 12 Again not symmetric so is not an equivalence relation De nition 317 A partition of a set S is a decomposition 503061 by disjoint sets so SD is a nonempty subset of S such that S UaeISD and Sa Sg0 ifay l Example 318 If S0a61 is a partition of S then R UaeIS is an equivalence relation The next theorem states this is the general type of equivalence relation 4 Lecture 4 1122009 Theorem 41 Let R or N be an equivalence relation on S and for each a E S axESaNx be the equivalence class ofa Then S is partitioned by its distinct equivalence classes Proof Because N is re exive a E a for all a and therefore every element a E S is a member of its own equivalence class Thus to nish the proof we must show that distinct equivalence classes are disjoint To this end we will show that if a N b ll then in fact a b So suppose that c E a N b and x E a Then we know that a N c b N c and a N x By re exivity and transitivity of N we then have xNaNch andhencebNx which shows that x E Thus we have shown a C b Similarly it follows that b C a l Exercise 41 Suppose that S Z with a N b iff amodn bmod n Identify the equivalence classes of N Answer lolylllyawlnill where iinZinszs Zi Exercise 42 Suppose that S R2 with a ahag N b b1b2 iff lal lbl where lal I a a Show that N is an equivalence relation and identify the equivalence classes of N Answer the equivalence classes consists of concentric circles centered about the origin 00 6 S 41 Binary Operations and Groups 7 a rst look De nition 42 A binary operation on a set S is afunction 6 S X S A S We will typically write a 96 b rather than 96 ab Example 43 Here are a number of examples of binary operations 1iSZand9 77 2 S odd integers and 96 77 is not an example of a binary operator since35358 S 3 S Z and 6 4 S R 0 and 6 5 S R 0 with 6 77 73 6 Let S be the set of 2 X 2 real complex matrices with A 96 B I ABi De nition 44 Let 96 be a binary operation on a set S Then 1 6 is associative if a 6 b 6 c a 6 b 6 c for all ab c E S 2 e E S is an identity element ife 6 a a a e for all a E S 5 Suppose that e E S is an identity element and a E S We say that b E S is an inverse toa ifbaeab 4 6 is commutative if a 6 b b 6 a for all a b E S De nition 45 Group A group is a triple G e where 6 is an associa tive binary operation on a set C e E G is an identity element and each 9 E G has an inverse in Ci Typically we will simply denote g 96 h by ghi De nition 46 Commutative Group A group Ge is commutative if gh hg for all hg 6 Ci Example 47 Z One easily checks that Z is a commutative group with e 0 and the inverse to a E Z is 7a Observe that e a ea a for all a iff e 0 Example 48 S Z and is an associative commutative binary oper ation with e 1 being the identity lndeed e a a for all a E Z implies e e 1 1 This is not a group since there are no inverses for any a E Z with lal 2 2 Example 49 G R 0 1 Rquot and is a commutative group e 1 an inverse to a is 1 a Example 410 S R 0 with 96 77 In this case 96 is not associative since a 12 c a 120 While abc abc It is also not commutative since ab ba in general There is no identity element e 6 S1 lncleecl7 e 96 a a a 96 e7 we would imply e a2 for all a f 0 Which is impossible7 iiei e l and e 4 at the same time Example 411 Let S be the set of 2 X 2 real complex matrices With A 96 B I ABi This is a noncommutative binary operation Which is associative and has an iclentity7 namely 397 1 0 e A 0 11 1 It is however not a group only those A E S With detA 0 admit an inverse Example 412 GL2 Let G I GL2 R be the set of 2 X 2 real complex matrices such that clet A f 0 With A 96 B 2 AB is a group With e I 1 1 and the inverse to A being A li This group is nonabeliean for example let 01 11 A2 710 andB01 then 0 1 11 0 1 AB 710 01 7171 While 11 0 1 711 BAl01l 710l l710l AB Example 413 SL2 Let SL2 R A E GL2 R detA 1 This is a group since det AB detA clet B 1 if A7 B E SL2 R 1 5 Lecture 5 1142009 51 Elementary Properties of Groups Let G be a group Lemma 51 The identity element in G is unique Proof Suppose that e and e both satisfy ea ae a and e a ae a forallaEG7theneeee l Lemma 52 Left and right cancellation holds Namely ab ac then b c and ba ca then b c Proof Let d be an inverse to a If ab ac then dab dac On the other hand by associativity7 d ab da b eb b and similarly7 d ac c Thus it follows that b c The right cancellation is proved similarly l Example 53 No cross cancellation in general Let G GL2 R 7 0 l l l l 0 A7710B701 andC7711 Then 0 AB 71 yet E f C In general7 all we can say if AB CA is that C ABA l 1 71 CA Lemma 54 Inverses in G are unique Proof Suppose that b and b are both inverses to a7 then ba e b a Hence by cancellation7 it follows that b b l Notation 55 fg E G let g 1 denote the unique inverse to g If we are in an abelian group and using the symbol quot for the binary operation we denote g 1 by 7g instead Example 56 Let G be a group Because of the associativity law it makes sense to write alagag and a1a2a3a4 where ai E G In eed7 we may either interpret alagag as a1a2a3 or as a1a2a3 which are equal by the associativity law While we might interpret a1a2a3a4 as one of the following expressions 01 1 a1a2 WW4 c2 2 a1a2a3 a4 03 1 a1a2a3a4 c4 2 a1a2a3a4 05 I a1a2a3a4 Using the associativity law repeatedly these are all seen to be equal For exam p16 61 a1a2 asa4 a1a2as a4 C2 03 a1a2a3a4 a1a2a3a4 C4 a1a2asa4 a1a2 asa4 61 and c5 2 a1a2aga4 a1a2a3a4 c1 More generally we have the following proposition Proposition 57 Suppose that G is a group and g17g27gn E G then it makes sense to write glgg gn E G which is interpreted to mean do the pair wise multiplications in any of the possible allowed orders without rearranging the orders of the g s Proof Sketch The proof is by induction Let us begin by de ning Mn G A G 2 inductively by M2 a7b ab7 M3 ab7 c ab c7 and Mng1gn I Mn1g1gn1 gn We wish to show that Mn g17 7gn may be expressed as one of the products described in the propo sition For the base case7 n 2 there is nothing to prove Now assume that the assertion holds for 2 S h S n Consider an expression for g1 gngn1 We now do another induction on the number of parentheses appearing on the right k A of this expression7 gn If h 07 we have braCketS inVOlVing 91 gn39gn1 Mn 917 797 9n1 Mn1lt917m79n17 wherein we used induction in the rst equality and the de nition of Mn1 in the second Now suppose the assertion holds for some k 2 0 and consider the case where there are k 1 parentheses appearing on the right of this expression k1 A ie i i i Using the associativity law for the last bracket on the right we can transform this expression into one with only k parentheses appearing k1 A on the right It then follows by the induction hypothesis that Mn1lt9179n1l l n times MES Notation 58 Form 6 Z andg E G let 9 2 gig andg I 9 1 i i 1971 g lyl 21andgoz ei Observe that with this notation that 9mg 9771 for all mn E Z For example 71 71 71 1 g3975999971g g g 97 7171 1 717171 7171 72 ggy ly g 9 99 g g g g 52 More Examples of Groups Example 59 Let G be the set of 2 X 2 real complex matrices with A 96 B I A Bi This is a group In fact any vector space under addition is an abelian group with e 0 and v Example 510 For any n 2 2 G 2 Zn 012Hin71 with a b ab modn is a commutative group with e 0 and the inverse to a 6 Zn being n 7 a Notice that n 7 a a modn nmodn 0 Example 51 Suppose that S 012Hin 71 with a 96 b abmodni In this case 96 is an associative binary operation which is commutative and e 1 is an identity for 5 In general it is not a group since not every element need have an inverse Indeed if ab E S then a 96 b 1 iff 1 ab modn which we have seen can happen iff gcd an 1 by Lemma 918 For example if n 4 S 0123 then 21122120 2100 and 2132 none of which are 1 Thus 2 is not invertible for this operation Of course 0 is not invertible as we r 6 Lecture 6 1162009 Theorem 61 The groups F07 n 2 2 let Un I a E 12n71 gcdan 1 and foT ab E U let a 97 12 ab modnl Then U 97 is a gToup Proof First off let a 97 12 ab modn for all ab E Z Then if abc E Z we have abc modn ab 0 modn ab modn cmod n modn a 97 b cmodn modn a b c modn a 97 b 97 5 Similarly one shows that abc modn a 97 b 97 c and hence is associative It should be clear also that 97 is commutative Claim an element a E 12ln71 is in Un iff there exists T E 12Hn7 1 such that Ta 1 gt a E U ltgt gcd an 1 ltgt there exists st E Z such that 3a 7 tn 1 Taking this equation modn then shows smodnamodn smodn amodn modn 3a modn 1modn 1 and therefore T I smodn 6 12 n 71 and T 97 a 1 lt If there exists T E 12ln71 such that 1 T 97 a Tamodn then nl Ta 7 1 ie there exists t such that Ta 7 1 kt or 1 Ta 7 kt from which it follows that gcd a n 1 ie a E U The claim shows that to each element a E U there is an inverse a U Finally if ab E U let k I 12 1 a 1 E Un then 16 kabb 1a 1ab1 and so by the claim a 97 b E U ie the binary operation is really a binary operation on U n l Example 62 U 10 U 10 13 7 9 with multiplication or Cayley table given by b1379 1 1379 3 3917 7 7193 9 9731 where the element of the ab row indexed by U 10 itself is given by a 97 b ab mod 10 Example 63 If p is prime then U p 12 pl For example U 5 1234 with Cayley table given by ab1234 1 1234 2 2413 3 3142 4 4321 Exercise 61 Compute 23 1 inside of U 50 Solution to Exercise We use the division algorithm see below to show 1 6 50 71323 Taking this equation mod 50 shows that 23 1 713 37 As a check we may show directly that 23 37 mod 50 1 Here is the division algorithm calculation 5022374 235473 4371 So working backwards we nd 14734737546472360722723 650771323 24 6 Lecture 6 1162009 61 02 7 re ections and rotations in R2 De nition 64 Subgroup Let G be a group A nonempty subset H C G is said to be a subgroup of G H is also a group under the multiplication law in G We use the notation H g G to summarize that H is a subgroup of G and H lt C to summarize that H is a proper subgroup of C In this section7 we are interested in describing the subgroup of GL2 R which corresponds to re ections and rotations in the plane We de ne these operations now As in Figure 61 let MLe39l I l S W1 9 9 C0029 Fig 61 The unit vector7 u 0 at angle 0 to the m 7 axis gt sin 9 W cos We also let Ra denote rotation by 04 degrees counter clockwise so that Rau t9 u 0 04 as in Figure 62 We may represent Ra as a matrix7 namely IQOLMLG 6d 0L ULLGl 6 Fig 62 Rotation by 04 degrees in the counter clockwise direction Ra RaellRaezl WWW WWW2N Ma Ma 7T2l cos04 cos 04 7172 cos04 7sin04 sin04 sin047r2 sin04 cos04 Page 24 job algebra We also de ne re ection7 Sm7 across the line determined by u 04 as in Figure 63 so that Suit 9 2 u 204 7 t9 We may compute the matrix representing SD Solute mowe Lum 9 M LG 7 Fig 63 Computing SW 857 SD SwellSaegl SDu 0 lSau 772 u 204 lu204 7 7r2 7 cos 204 cos 204 7 772 7 cos 204 sin 204 7 sin 204 sin 204 7772 7 sin 204 7cos 204 macro svmonob cls datetime 13Mar20099 O4 7 Lecture 7 1212009 De nition 71 Subgroup Let G be a group A nonempty subset H C G is said to be a subgroup of G is also a group under the multiplication law in Ci We use the notation H S G to summarize that H is a subgroup of G and H lt C to summarize that H is a proper subgroup of Cl Theorem 72 Twostep Subgroup Test Let G be a group and H be a nonempty subset Then H S G if 1 H is closed under ie his 6 H for all hh E H 2 H is closed under taking inverses ie h 1 E H ifh 6 Hi Proof First off notice that e h lh 6 Hi It also clear that H contains inverses and the multiplication law is associative thus H S Ci l Theorem 73 Onestep Subgroup Test Let G be a group and H be a nonempty subset Then H S G i ab 1 6 H whenever a b 6 Hi Proof If a E H then e a a 1 E H and hence so is a 1 ae 1 E H Thus it follows that for ab E H that ab a b 171 E H and hence H S G and the result follows from Theorem 72 l Example 74 Here are some examples of subgroups and not subgroups ll 2Z lt Z while SZ C Z but is not a subgroup 2 Zn 01 2 n 71 C Z is not a subgroup on since they have different group operations 3 e S G is the trivial subgroup and G S Ci Example 75 Let us nd the smallest subgroup H containing 7 E U15l Answer 72mod15 7 4 73mod15 13 74 mod15 1 so that H must contain 1 7413 One may easily check this is a subgroup and we have 7 4 Proposition 76 The elements 02 2 SmRa a E R form a subgroup GL2 R moreover we have the following multiplication rules RaR Ram 5045 R2a7 7 71 R350 0447327 and 50133 SWC g 72 for all 15 6 R Also observe that RD R3 ltgt a mod 360 73 while 50 5395 ltgt a modlSOl 74 Proof Equations 71 and 72 may be veri ed by direct computations using the matrix representations for R0 an 5 Per aps a more illuminating way is to notice that all linear transformations on R2 are determined by there actions on u9 for all 9 actually for two 9 is typically enough Using this remark we nd RaRgu 9 Rau 9 u 9 B a Ra u 9 SaSgu 9 Sau 2B 7 9 u2a 7 2B 7 9 u2 a 7 9 R2ltai u9 Bissau lt6 7 RM ea 7 0 7 u m 7 6 7 6 7 u lt2 a 2 7 0 7 Samw lt6 and SaRgu 9 Sau 95 u2a 7 9476 u 2 a 762 7 9 SQC gu 9 which veri es equations 71 and 72 From these it is clear that H is a closed under matrix multiplication and since R70 1 and 51 50 it follows H is closed under taking inverses To nish the proof we will now verify Eq 74 and leave the proof of Eq 73 to the reader The point is that 50 5 iff o u 2a 7 9 Sau 9 Sgu 9 u 25 7 9 for all 9 which happens iff 2a 7 9 mod 360 2B 7 9 mod 360 which is equivalent to a 6 mod 180 l 8 Lecture 8 1232009 Notation 81 The order of a group G is the number of elements in G which we denote by Cl Example 82 We have Zl 00 MA n for all n 2 2 and Dgl 6 and Dill 8 De nition 83 Euler Phi 7 function For n E Z1 let n I 1g h S ngcdhn1 This function so is called the Euler Phi 7 function Example 84 If p is prime then U p 1 2 p 71 and g0 p p 7 1 More generally U pn consists of 1 2 pn multiples of p in 1 2 p Therefore 9010 lUP l 0quot 7 multiples of in 127 v v 7107 Since multiples ofp in 12 p hp h 12p 1 it follows that multiples of p in 1 2 pn pn 1 and therefore so 10 0 7 10 7 10 0 71 valid for all primes and n 2 1 Example 85 g0 pmqn Let N pmq with mn 2 1 and p and 4 being distinct primes We wish to compute g0 N U To do this let let 0 2 12 N 71 N A be the multiples ofp in Q and B be the multiples of q in 2 Then A N B is the subset of common multiples of p and q or equivalently multiples of pq in 0 so that A NP Pm lq B Nq pmqn l and A m B N W pm lqn h Therefore MN9AUB97AUB 97lAB7A Bl 7 N N N P 4 P39q pm39qnip39m7139qnipm39qn714rpm7139qn7l which after a little algebra shows in n m m71 n n71 1 1 pqp 7 q 74 N 177 177 p q The next theorem generalizes this example Theorem 86 Euler Phi function Suppose that N plfl with hi 2 1 and p heing distinct primes Then n n 1 Nso pklmplfquot 7 p 7p 1 1 N 177 l 1 l l l 0 Proof Proof was not given in class Let Q 2 12 N and Ai I m E Q It then follows that U N Q ULIAi and therefore 90 N 9 0521140 N i 114139 To compute the later expression we will make use of the inclusion exclusion formula which states n it 21140 2PM Z Ail 39 39 39 AMA 8A1 l1 lgi1lti2ltmltiggn Here is a way to see this formula For A C 0 let 1A h 1 if h E A and 0 otherwise We now have the identity 28 8 Lecture 8 1232009 7 171W1A1H171A1 i1 n 17 Z 71l Z MUNMH l1 1 i1lti2ltmltii5n Summing this identity on k E Q then shows Ne U1AiN7i71l 2 Ai nnAgt l1 1 i1 lti2ltltii n which gives Eq 81 Since Ail Ail consists of those k E 0 which are common multiples of pi1pi2 pi or equivalently multiples of pi pig pi it follows that N Ail nnA pil 39piz quotquot39Pi Thus we arrive at the formula n N 11 NNZ71 l1 1 i1lti2ltmltiign 10 p p n N NZ 1l l1 1 i1lti2ltmltii n 10 3910 39 39 39 39 3910 Let us now break up the sum over those terms with i n and those with i lt n to nd n71 l N MN NZ1 l1 1 i1lti2ltmltiiltn 1 3910 39 39 39 39 3910 n N 71 l 3 gt Z l1 15i1lti2ltltii71ltiin We may factor out piquot in the rst term to nd n 1 1c kn l N MN pn so lt1011 guan Z1 l1 15i1lti2ltltii71ltiin Similarly the second term is equal to Page 28 job algebra viipi2pi macro k n l pkl pknil M71 k V 1 1 p 72011 Pn711 EH 12 lgi1lti2ltmltil71ltn p 0 pl n71 k1 knil knil k kw l P1 10 71 n follvvvpn71 Zlti1gt 11 15i1lti2ltltiiltn p p 0 164 k 1 ipn goltplliupn711gt Thus we have shown kn k kn 1671 k kw Npn90ltp11 pn711gt7pn solt1011mpnif 105quot 7 offl so lt101 a 4051 and so the result now follows by induction Corollary 87 If mn 2 1 and gcd m n 1 then go go go Notation 88 For 9 E G let lt9 2 9 z n E Z We call lt9 the cyclic subgroup generated by 9 as justi ed by the neat proposition Proposition 89 Cyclic subgroups For all 9 E G lt9 g G Proof For mn E Z we have 9 lt9 71 9n m 6 lt9 and therefore by the one step subgroup test lt9 S G l Notation 810 The order of an element 9 E G is 191 I minn 219 e with the convention that 191 00 n 2 1 9 e 0 Lemma 811 Let 9 E G Then lt91 00 i no two elements in the list 9 n6 Z9 297190 e91 992 are equal Theorem 812 Suppose that 9 is an element of a group G Then either 1f191 00 then all elements in the list 9 n6 Z de ning lt9 are distinct In particular 00 2fnz191lt 00 then 9m 9mm dn for all m E Z lt9 79927Awgn 1 8 2 with all elements in the list being distinct and n We also ave 9kgl 9klm dn for all hl 6 Zn 83 which shows that lt9 is equivalent to Zn svmonobcls datetime 13Mar20099O4 So in all cases lgl Proof 1 If gi gj for some i lt j7 then 6 9194 ng i 9H so that gm 7 6 with m j 7 i E Z from which we would conclude that lgl lt 00 Thus if lgl 00 it must be that all elements in the list7 gn n E Z 7 are distinct In particular lt9 gn n E Z has an in nite number of elements and therefore 00 2 Now suppose that n lgl lt 00 Since 9 67 it also follows that g 7 9 71 e er Therefore if m E Z and m sn 7 where 7 m mocln7 then gm 9 T gr7 iiel gm gm mm for all m E Z Hence it follows that lg 1l Moreover if gi gj for some 0 S i S j lt n7 then 6 with j 7 i lt n and hence j if Thus the list in 82 consists of distinct elements and therefore nl Lastly7 if 161 6 Zn then 9H 9kg 91H gklmodn 9 Lecture 9 1262009 Corollary 91 Let a E G Then ai aj i lal divides j 7 Here we use the convention that 00 divides m i m 0 In particular ak e i lal Us Corollary 92 For all g C G we have lgl S Proof This follows from the fact that lgl and ltggt C G l Theorem 93 Finite Subgroup Test Let H be a nonempty nite subset of a group G which is closed under the group law then H S G Proof To each h E H we have hk1 C H and since lt 00 it follows that hk hl for some h f l Thus by Theorem 812 lhl lt 00 for all h E H and lthgt ehh2hlhl 1 C H ln particular h 1 E h C H for all h E H Hence it follows by the two step subgroup test that H S G l De nition 94 Centralizer of a in G The centralizequot ofa C G denoted Ca is the set ofg E G which commute with a ie Cag ngaag More generally if S C G is any nonempty set we de ne CS 2 ye ngssgfor allsE S 565Cs Lemma 95 For all a C G a S Ca S G Proof If g E C a then ga ag Multiplying this equation on the right and left by g 1 then shows ay l y lgay l g layy l y la which shows g 1 E Ca Moreover if gh E Ca then gha gah agh which shows that gh E C a and therefore C a S G l Example 96 If G is abelian then C a G for all a E G Example 97 Let G GL2 R we will compute C A1 and C A2 where 01 10 A1 10 andAgz 071 ab cd ba 7 ab 017 01 ab 7 cd dc 7 cd 10 710 cd 7 ab which means thatbcandadieBmust be ofthe form ab M CA 7 ab 2 b2 0 0 ba 0397 d We have B e CAg i F aibiabloilo abiab cid 7 cd 0717 071 cd 7 iced which happens iff b c 0 Thus we have 0 CAg3dlzad o Lemma 98 If is a collection of subgroups ofG then H I iHi S G as well H WehaveB CA1iff and therefore to Proof If h h E H then h h 6 H1 for all i and therefore hh l 6 H1 for all i and hence hh l E H l Corollary 99 C S S G for any nonempty subset S C G De nition 910 Center of a group Center of a group denoted ZG is the centralizer of G ie ZGCGaEGazzaforallz G 32 9 Lecture 9 1262009 By Corollary 99 Z G C G is a group Alternatively if a e Z G then r raim iesa1r1 I la 1 w implies a1 7 1 forallr 6 Sand therefore ail e ZG v If ab 6 ZG then aha arh rah ah e ZG which again shows Z G is a Example 911 G is a ahelian iff ZG 0 thus ZZa Zn ZUrt U rt eta Example 912 Using Example 97 we may easily show ZGL2 112 AI A e 112 0 lndeed ZGL2 112 c 0A1 CA2 a2 at a 91 e 11mm As the latter matrices commute with every matrix we also have Z CL2 112 c M a e in 0 c Z CL2 112 Remarh 913 if s c a is a nonempty set we let 3 denote the smallest sub group in G which eontains s This suhgroup may he eonstrueted as nite prod 6 Lists of elements from S and 31 S It is not too hard to prove hat 03 CltSgtv Let us also note that if s c T c G then CT c 03 as there are more restrictions on a e G to he in CT than there are for a e G to he in 03 91 Dihedral group formalities and examples De nition 914 General Dihedral Groups FM n 2 3 the dihedral gmu Dm ts the symmet araap cf a regalar rt e gan Ta he erphttt thts may he reaheea as the subrgmups O 2 ae aea as Dn kaskg h 0l2rtel see the Ftaares helaw Nattte that pg 2a See the book and the demonstration in class for more intuition on these Oupst For Computational purposes We may present D7 in terms of generators and relations as follows and f 30 Theorem 915 A presentation of De Leta 2 3 and T R2 Then DegTk rkfk0l2 nil 9391 aha me hace the relatrars r7 1 f2 1 aha frf T l We say that r aha f are aerteratars far D Page 32 job algehra Figi 9i1i The 3 re ection symmetries axis of a regular 3 e gon ie a equilateral triangle Fig 92 The 47 re ection symmetries axis of a regular 4 e gon ie a square Figi 9i3i The he re ection symmety axis of a regular 6 e gon i e a heagon There are also a rotation symmetries macro sv39monobwls datetune 13Mar72009904 Proof We know that pk R162quot and that ka R162quot 50 516 from which Eq 91 follows It is also clear that T l f2l Moreover frf 501m 50 303 R2Oil r1 as desired Poetically a rotation viewed through a mirror is a rotation in the opposite direction I or computational purposes observe that 1W frf frf frf Hf H and therefore f39r gf f f39rgf f Tgl In general we have kaf T46 for all k e Z Example 916 If f 6 D7 is a re ection then f2 e and 2i lf 2 RQWn thenxk RQWkna eforlgkgniland39r lso l rl nand ltTgtR2kn0gkgn71chl Example 917 Suppose that G Dn and f Sol Recall that Dn Tk39rkf2gl We wish to compute We have pk E iff ka ka iff pk kaf T kl There are only two rotations R9 for which R9 R971 namely R0 e and R130 ill The latter is in Dn only if n is even Let us now check to see if ka E C This is the case iff pk f39rkf T k and so again this happens iff 7 R0 or ngol Thus we have shown 7 ltfgtef if nis odd 0 7 eT 2 f Tn2f if n is even Let us now nd C pk In this case we have ltTgt C C pk as this is a general factl Moreover Tlf E C pk iff Tlf pk pk Tlf which happens iff Tlik TlTik 01 ka T1947 ilel iff T211C el Thus we may conclude that C pk ltTgt unless k 0 or k g and when k 0 or k n2 we have C pk Dnl Of course the case k n2 only applies if n is even By the way this last result is not too hard to understand as 7 I and TnQ 71 where I is the 2 X 2 identity matrix which commutes with all matricesl Page 33 job algebra 91 Dihedral group formalities and examples 3 Example 918 For n 2 3 7 R0 I ifn is odd Z Dn 7 R0 R130 if n is even 92 To prove this recall that SaR9S1 R9 for all a and 9 So if SD 6 ZDn we would have R9 SOLR9 51 R9 for 9 kZTrn which is impossible Thus Z D7 contains no re ections Moreover this shows that R9 can only be in the center if R9 R79 ilel R9 can only be R0 or ngol This completes the proof since R130 6 Dn iff n is even Alternatively observe that Z Dn O f C 7 C fr since if g 6 D7 commutes with the generators of a group it must commute with all elements of the group Now according to Example 917 we again easily see that Eq 92 is correct For example when n is even we have 21 Cf n CT aw2 Jew216 n m mu2 R0R130 macro svmonob cls datetime 13Mar20099 O4 10 Lecture 10 1282009 Midterm I 11 Lecture 11 1302009 1 11 Cyclic Groups De nition 111 We say a group G is a cyclic group if there exists 9 C G such that G g We call such a g a generator of the cyclic group G Example 112 Recall that U 9 1245 7 8 and that lt2gt2 1 212 224 238 247 255 251 so that 2 2 6 and U9 and 2 is a generator Notice that 22 4 is not a generator since 22gt 147 y U9 Example 113 The group U 8 135 7 is not cyclic since 3 13 5 15 and 7 1 7 This group may be understood by observing that 3 5 15 mod8 7 so that U8 3151 ab E Z2 Moreover the multiplication on U 8 becomes two copies of the group operation on Z2 ie gash 3113 3aa5bb 3aamod25bb mod2 So in a sense to be made precise later U 8 is equivalent to Z3 Example 114 Here are some more examples of cyclic groups 1 Z is cyclic with generators being either 1 or 71 2 Zn is cyclic with 1 being a generator since 1 012113111n71 3 Let k G I e1527r h E Z then G is cyclic and g I ei27rn is a generator lndeed gk ei 27r is equal to 1 for the rst time when k n These last two examples are essentially the same and basically this is the list of all cyclic groups Later today we will list all of the generators of a cyclic group Lemma 115 IfH C Z is a subgroup and a I minH Z1 then H a haz h E Z Proof lt is clear that a C H lf 1 E H we may write it as b ha r where0 rlta Asrb7haEHand0 rltawemusthaver0 This shows that b E a and thus H C a l Example 116 If f E GL2 R then f is re ection about the line x ln particular f2 I and 1 and 2 So we can have elements of nite order inside an in nite group ln fact any element of a Dihedral subgroup of GL2 R gives such an example Notation 117 Let n E Z1 U We will write I E amodn i b 7 a modn 0 or equivalently n b 7 a here we use the convention that ifnoo thenbEamodn i ba andoohn i m0 Theorem 118 More properties of cyclic groups Let a C G andn a Then ai aj i i E j mod n If Mm then am C ak ltak ltagcdnkgt Lilgcd alykl D lt Zgt ajgt gcd gcd ltakgt W 23919 gcdkn 1 Proof 1 We have ai aj iff 1 2 3 4 5 o e al al7imodn which happens iff 7 j modn 0 by Theorem 812 2 lfm lh then amq alkq aklq and therefore am C ak 3 Let d I gcd n7 k 7 then dlk and therefore ltakgt C ltadgti For the opposite inclusion we must show ad 6 ltakgti To this end7 choose s7t E Z such that d 316 tni It then follows that ad askatn akgt5 E ltakgt as desired k 4 Again let d I gcd n7 k and set m I nd E N Then ad adk e for 1g k lt m and a m a er Hence we may conclude that ladl m ndi Combining this with item 3 show7 lakl lltakgtl lltadgtl ladl nd lalgcdk7 lull 5 By item 417 if gcd gcd j7n then ltaigt ltagcdingt ltagcdjngt ltajgt Conversely if ltaigt ltajgt then by item 417 L i j L gcdw llta gtl llta gtl gown from which it follows that gcd i7 n gcd j7 n i 6 This follows directly from item 3 or item 5 l Example 119 Let use Theorem 1118 to nd all generators of Z10 07172711179 Since 1 is a generator it follow by item 6 of the previ ous theorem that the generators of Z10 are precisely those k 2 1 such that gcdk710 1 Recall we use the additive notation here so that ak becomes kai In other words the generators of Z10 is precisely U10 1737 77 9 of which their are so 10 go 5 2 5 712 71 4 More generally the generators of Zn are the elements in U It is in fact easy to see that every a E U is a generator lndeed7 let I I a 1 6 U7 then we have Zn lt1gt ltbamodngt lt12 agt C a C Z771 Conversely if and a E 7 then gcd a7n d gt 1 and therefore gcd ad7n 1 and ad E Thus ad generates Zn and therefore lal nd and hence lltagtl nd and ltagt Z771 12 Lecture 12 222009 Theorem 121 Fundamental Theorem of Cyclic Groups Suppose that a is a cyclic group and H is a subgroup of C an mmHminh21zak6H 121 Then 1 H ltamgt so all subgroups of G are of the form ltamgt for some m 2 1 2 fn lal lt 00 thenmln andl ln m 5 To each divisor h 2 1 ofn there is precisely one subgroup ofG of order k namely H lta k In short ifG a with lal n then Positive divisors of n lt gt subgroups of C m A am is a one to one correspondence These subgroups may be indexed by their order k Ham Proof We prove each point in turn 1 Suppose that H C G is a subgroup and m is de ned as in Eq 121 Since am 6 H and H is closed under the group operations it follows that ltamgt C H So we must show H C ltamgt lf al 6 H with l E Z we write l jmr with r I lmodm Then al amjaT and hence aT al amfj E H As 0 S r lt m it follows from the de nition of m that r 0 and therefore al ajm am 6 lta Thus we have shown H C ltamgt and therefore that H ltamgt From Theorem 118 we know that H ltamgt ltangmgt gt and that n gcd m n Using the de nition ofm we must have m S gcd m n which can only happen if m gcd m This shows that mln and 3 From what we have just shown the subgroups H C G are precisely of the form ltamgt where m is a divisor of n Moreover we have shown that Ham nm h Thus for each divisor h of n there is exactly one subgroup of G of order k namely ltamgt where m n h E0 Example 122 Let G Z20 Since 20 22 5 it has divisors h 1 2 4 5 10 20 The subgroups having these orders are Order 1 0 H1 0 2 lil lt i iolio 4 lt5 1 051015 5 lt4 g1 048121620 10 pkg1 02468101214161820 20 lt1 E1 Z2o Corollary 123 Suppose G is a cyclic group of order n with generator g d is a divisor of n and a gnd Then elements of order d in G ak h E Ud and in particular G contains exactly go d elements of order d It should be noted that ak h E U is also the list of all the elements of G which generate the unique cyclic subgroup of order d Proof We know that a I gnd is the generator of the unique cyclic subgroup H S G of order d This subgroup must contain all of the elements of order d for if not there would be another distinct cyclic subgroup of order d in G The elements of H which have order d are precisely of the form ak with 1 S h lt d and gcd h d 1 ie with h E U As there are god such I elements the proof is complete Example 124 Let us nd all the elements of order 10 in Z20 Since 2 10 we know from Corollary 123 that 2hz h C U10 2h h 1379261418 are precisely the elements of order 10 in Z20 Corollary 125 The Euler Phi function satis es n EKG ng 4O 12 Lecture 12 222009 Proof Every element of Zn has a unique order d which divides n and therefore n E keanlkld Z Md 15010117 13010117 Example 126 Let us test this out for n 20 In this case we should have 7 20 so1so2so4so5so10so20 11244 2272 571 112448 20 Remark 127 In principle it is possible to use Corollary 125 to compute go For example using this corollary and the fact that go 1 1 we nd for distinct primes p and L that pso1sop 1sozo sozozo17 02 so1sozosop2 psop2 sozo 102710 pqso1sopso4som P41som which then implies sop4pqioiq110700171 Similarly p24 so 1 so P so 4 so 04 so 02 so 1024 1m p2 7 p so 1024 and hence sop2t1 102471047 10271 p247p27pq o pzoqipiq1 10o1q1s Theorem 128 Suppose that G is any nite group and d E Z then the num ber elements of order d in G is divisible by so d r Proof Let GdgEGzlgl dl lf Gd Z the statement of the theorem is true since so d divides 0 Gd r lfa 6 Cd then ltagt is a cyclic subgroup of order d with precisely g0 d element of order d If Gd ltagt Z we are done since there are precisely g0 d elements of order d in G If not choose I E Gd ltagt r Then the elements of order d in ltbgt Page 40 job algebra must be distinct from the elements of order d in ltagt for otherwise a 12gt but 12 ltagt r 1f Gd ltagt U Z we are again done since now Gd 2g d will be the number of elements of order d in Cr lf Gd ltagt U Z we choose a third element 5 E Gd ltagt U and argue as above that Gd 3g d if Gd ltagt U ltbgt U 0 Continuing on this way the process will eventually terminate since Gd lt 00 and we will have shown that Gd ngo d for some n E N l Example 129 Exercise 420 Suppose that G is an Abelian group 16quot 35 and every element of G satis es 135 er Prove that G is cyclic Since 135 e we have seen in Corollary 91 that must divide 35 5 7 Thus every element in G has order either 1 5 7 or 35 If there is an element of order 35 G is cyclic and we are done Since the only element of order 1 is e there are 34 elements of either order 5 or 7 As go 5 4 and go 7 6 do not divide 35 there must exists ab E G such that lal 5 and lbl 7 We now let I I a and claim that 35 which is a contradiction To see that 35 observe that gt1 15 a5b5 e125 e so f 5 and I7 a7b7 a2 f e so that lzl 7 Therefore 35 and we are done Alternatively for this last part Notice that I anbn e iff a If If a If f e then lanl 5 while lb 7 which is impossible Thus the only way that anbn e is if a e bnl Thus we must 5ln and 7ln and therefore 35ln and therefore 35 macro svmonob cls datetime 13Mar20099 O4 13 Lecture 13 242009 The least common multiple7 lcm a17 7 7 of h integers7 a17 7 E Z17 is the smallest integer n 2 l which is a multiple of each ai for i l7 7 h For example7 1011100714715 lcm2 5727735 235 7 210 Corollary 131 Let a17 7 ak E Z17 then a1 N am ltlcm a17 7akgt C Z Moreover7 m E Z is a common multiple of a177ak is a multiple of lcma177ak Proof First observe that common multiples of a17 7ak a1 N am which is a subgroup of Z and therefore by Lemma 1157 common multiples of a17 7ak where n min common multiples of a17 7 ak Z1 lcm a17 7 ck I Corollary 132 Let a17 7 ak E Z17 then lcm a17 7ak lcm a17lcm a17 7 am Proof This follows from the following sequence of identities7 ltlcma17 7akgt a1 N am a1 lta2gt N am a1 ltlcm a17 7akgt ltlcm a17lcm a17 7akgt I Proposition 133 Suppose that G is a group and a and b are two nite order commuting elements of a group G such that1 ltagt ltbgt e Then aw lcm M 7 Proof If e abm ambm for some m E Z then ltagt 3 am him 6 ltbgt from which it follows that am I m 6 ltagt ltbgt e 7 ie am e 127 This happens iff m is a common multiple of M and 12 and therefore the order of ab is the smallest such multiple7 ie aw lcm a 7 I It is not possible to drop the assumption that a N ltbgt e in the previous proposition For example consider a and 6 in Z37 so that M 47 6 8 gcd 678 47 and lcm 474 47 while a b 0 and 0 1 More generally if b a 1 then aw 1 while M 12 can be anything In this case7 ltagt n ltbgt ltagt 131 Cosets and Lagrange7s Theorem Chapter 7 of the book Let G be a group and H be a nonempty subset of G Soon we will assume that H is a subgroup of G De nition 134 Given a 6 G7 let 1 aH ah h E H 7 called the left coset ofH in G containing a when H g G7 2 Ha ha h E H 7 called the right coset of H in G containing a when H S G7 and 3aHa 1aha 1zh E De nition 135 IfH g G7 we let GH I aH a E G 1 You showed in Ebrercise 454 of homework 47 that if al and bl are relatively prime7 then 1 1 e holds automatically 42 13 Lecture 13 242009 be the set ofleft cosets ofH in G The index ofH in G is 1G H1 2 that is 1G H1 the number of distinct cosets ofH in G Example 136 Suppose that G CL ZR and H 2 SL ZR In this case for A E G we AHABBeHCdetCdetAl Each coset of H in G is determined by value of the determinant on that coset As GH may be indexed by R 0 it follows that GLaR SLlt2Rgt ltRogt oo Example 137 Let G U 20 U 22 5 13 7911131719 and take H lt3gt 1397 in which case 1H3H9H7HH 11H 11131917 13H 17H 19Hl WehaveleHl2and lGHlgtltlHl2gtlt48lGl Example 138 Let G Z9 and H lt3 0 36 In this case we use additive notation 0H3H6HH 1H1474H7H 2H2582H8H WehaveleHl3and lGHlgtltlHl3gtlt39lGl Example 139 Suppose that G D4 2 rkrkf0 with r4 1 f2 1 and frf r l If we take H 1f then TkH T a f rkfmkff kaH for k 0123 In this case we have 1G H1 4 and GHXH4gtlt28Gl Page 42 job algebra Recall that we have seen if G is a nite cyclic group and H S G then 1H1 divides G This along with the last three examples suggests the following theorem of Lagrange They also motivate Lemma 142 below Theorem 1310 Lagrange s Theorem Suppose that G is a nite group and H S G then divides 1G1 and 1G1 is the number of distinct cosets ofH in G ie leHlX Corollary 1311 If G is a group of prime order p then G is cyclic and every element in G e is a generator of G Proof Let g E G e and take H I Then gt 1 and l 1G1 p implies p Thus it follows that H G ie G ltg l Before proving Theorem 1310 we will pause for some basic facts about the cosets of H in C macro svmonob cls datetime 13Mar20099 O4 14 Lecture 14 262009 Suppose that f z X A Y is a bijection being one to one is actually enough here Then if AB are subsets of X we have AB ltgt fAfB7 where a z a E A C Y Indeed it is clear that A B gt A f For the opposite implication let g Y A X be the in verse function to f then f B gt gf gf But gfA agfa aeAAandgltfltBgtgt B Let us also observe that if f is one to one and A C X is a nite set with n elements then n Indeed if a1 an are the distinct elements of A then a1 f an are the distinct elements of f Lemma 141 For any a E G the maps La G A G and Ra G A G de ned by La am and Ra za are bijections Proof We only prove the assertions about La as the proofs for Ra are analogous Suppose that z y E G are such that La La ie az ay it then follows by cancellation that z y Therefore La is one to one It is onto since if z E G then La a lz 1 Alternatively Simply observe that Laa G A G is the inverse map to a I Lemma 142 Let G be a group H S G and ab E H Then a E aH aH H i a E H fa E G andb E aH then aH bH faH bH D then aH bH So either aH bH or aH bH 0 aH bH i ca lb E H G is the disjoint union of its distinct cosets aH Ha i caHa 1 H laHl lel where laHl denotes the number of element in aH aH is a subgroup of G i a E H FWRF F HFPSNEN Proof For the most part we refer the reader to p 138139 of the book for the details of the proof Let me just make a few comments 1 Since e E H we have a ae E aH 2 If aH H then a ae E aH H Conversely if a E H then aH C H since H is a group For the opposite inclusion if if h E H then h a a lh C aH ie H C aH Alternatively as above it follows that a lH C H and therefore H a a lH C aH 3 lfb E ah E aH then bH ahH aH 4 If ah bh E aH bH then b ah h 1 E aH and therefore bH aH 5 If a lb E H then a lb h E H and b ah and hence aH bH Conversely if aH bH then b be ah for some for some h E H Therefore a lb h e H 6 See item 1 shows G is the union of its cosets and item 4 shows the distinct cosets are disjoint 7 We have aH Ha ltgt H Ha a 1 aH a 1 aHa l 8 Since La and L5 are bijections it follows that laHl La Similarly lel 9 eEaHiffaEH Remark 143 Much of Lemma 142 may be understood with the aid of the following equivalence relation Namely write a N b iff a lb E H Observe that aNasincea laeEHaNb gt bNasincea leH gt b la a lb71 E H and a N b and b N 5 implies a N 5 since a lb E H and bile E H gt ailc ailbbilc E H The equivalence class a containing a is then abzaNbbha 1bEHahzhEHaH De nition 144 A subgroup H g G is said to be normal if aHa 1 H for all a E G or equivalently put aH Ha for all a E G We write H lt1 G to mean that H is a normal subgroup of G We will prove later the following theorem lf you want you can go ahead and try to prove this theorem yourself 44 14 Lecture 14 262009 Theorem 145 Quotient Groups If H lt1 G the set of left cosets GH7 becomes a group under the multiplication rule aH bH I abH for all ab 6 Hi In this group eH is the identity and aH 1 a lHl We are now ready to prove Lagrangels theorem which we restate herel Theorem 146 Lagrange s Theorem Suppose that G is a nite group and H S G then lGIHlX lHllGl7 where 1G Hl I is the number of distinct cosets of H in Cr In particular divides lGl and 16quot lG Hll Proof Let n 2 1G Hl and choose ai E G for i 12n such that aiHELI is the collection of distinct cosets of H in Cr Then by item 6 of Lemma 142 we know that G U1aiH with aiH ajH ll for all i a jl Thus we may conclude7 using item 8 of Lemma 142 that megaHm21H1nH1GH11H1 i1 i1 Remark 147 Becarefull Despite the next two results7 it is not true that all groups satisfy the converse to Lagrangels theoreml That is there exists groups G for which there is a divisor7 d of 16quot for which there is no subgroup7 H S G with d We will eventually see that G A4 is a group of order 12 with no subgroups of order 6 Here7 A4 is the so called alternating group on four letters Lemma 148 IfH and K satisfy the converse to Lagrange s theorem then so does H X Kl In particular every nite abelian group satis es the converse to Lagrange s theorem Proof Let m I and n 1f dlmn7 then we may write d dldg with dllm and dglnl We may now choose subgroups7 H S H and K S K such that lHl d1 and lKl dgl It then follows that H X K S H X K with lH gtlt K l dldg d The second assertion follows from the fact that all nite abelian groups are isomorphic to a product of cyclic groups and we already know the converse to Lagrangels theorem holds for these groups I Page 44 job algebra Example 149 Consider G Dn ltr f z r e f2 and frf r 1l The divisors of 2n are the divisors7 A of n and 21 1f d E A let H I ltrnd to construct a group of order d To construct a group of order 2d take7 H ltrndgt fU ltrndgtl Notice that this is subgroup of G since7 Tm01f Tmif TkndTlndff Tk7lnd Tm01f Tlnd Tk7lndf Tlndindf Tklndf This shows that Dn satis es the converse to Lagrangels theoreml Example 1410 Let G U30 U2 3 5 17111317192329 and H lt11 111 In this case we know 1G Hl 82 47 ie there are 4 distinct cosets which we now find 1H H 111 7H 717 13H 1313 11 mod30 23 19H 1919 11 mod30 29 Notice that 1911 7112 mod30 7121mod30 71mod30 29 Corollary 1411 fG is a nite group andg E G then lgl divides 1G1 ie Proof Let H I g then lgl and lG Hl lgl l Corollary 1412 fG is a nite group andg E G then glGl er Proof By the previous corollary7 we know that 16quot lgl n where n I n e er l 13 ltggt1 Therefore glGl glgln 9191 Corollary 1413 Fermat s Little Theorem Let p be a prime number and a 6 ap modp amodpl 141 Proof Let r I amodp E 012qui1 Since ap modp a modpp modp rp modp macro svmonob cls datetime 13Mar20099 O4 it suf ces to show TmeClp7 for all T E 0127lll7p71 As this latter equation is true when T 0 we may now assume that T E U p 127 l l l p 7 l The previous equation is then equivalent to T17 T in U p which is equivalent to T1 1 1 in U p l However this last assertion is true by Corollary 1412 and the fact that lU p 7 1 l 15 Lecture 15 292009 Example 15 Consider 32mod5 25 mod5 2mod5 2 Example 152 Let us now show that 35 is not prime by showing 235 mod35 y 2mod35 2 To do this we have 2 mod 35 2 22 mod 35 4 24 mod35 22 1110335 mod35 42 mod35 16 28 mod 35 24 mod 35 mod 35 162 mod 35 256 mod 35 11 215mod35 ll2mod35 l2lmod35 16 232mod35 162mod35 11 and therefore7 235mod35 23mod35 232mod35 mod35 88 mod35 18 y 2 Therefore 35 is not primel Example 153 Primality Test Suppose that n E Z is a large number we wish to see if it is prime or not Hard to do in general Here are some tests to perform on n Pick a few small primes7 p7 like 235 7 less than n 1 compute gcd p7 lf gcd p7 n p we know that pln and hence n is not rimel 2 If gcd p7 n l7 compute p modn as above If p modn p7 then n is again not prime 3 If we have p modn p gcd p7 n for p from our list7 the test has failed to show n is not primel We can test some more by adding some more primes to our list Remark This is not a fool proof test There are composite numbers n such that a modn amodn or al These numbers are called pseudoprimes and n 561 3 X 11 X 17 is one of theml See for example http enlwihipedialorgwihiFermatprimalitytest and http enwihipedialorgwihiPseudoprime Example 154 Exercise 716 The same proof shows that ifn E Z and a E Z is relatively prime to n7 t en awn modn ll lndeed7 we have aw modn r pm modn where r I amodn and we have seen that gcd r7 n gcd an 1 so that r E U Since go lU we may conclude that rwn l in U ile aw modn r pm modn 1 Theorem 155 Suppose G is a group of order p 2 3 which is prime Then G is isomorphic to Z217 or DP Before giving the proof let us rst prove a couple of lemmasl Lemma 156 IfG is a group such that a2 e for all a E G then G is abelian Proof Since a2 it follows that e we know that a a 1 for all a 6 Cl So for any a7 12 E G ab abf1 flail ba7 ie C must be abelianl l Lemma 157 If G is a group having two distinct commuting elements a and b with lal 2 lbl then H I eabab is a subgroup of order 4 Proof By cancellation ab is not equal to a or 12 Moreover if ab e7 then a 2 1 b which again is not allowed by assumption Therefore H has four elements It is easy to see that H S Cl 48 15 Lecture 15 292009 We are now ready for the proof of Theorem 155 Proof Proof of Theorem 155 Case 1 There is an element 9 E G of order 2p In this case G lt9 Z217 and we are done Case 2 lgl S p for all g E G In this case we must have at least one element a E G such that lal p Otherwise we would have by Lagrangels theorem lgl S 2 for all g E G However by Lemmas 156 and 157 this would imply that G contains a subgroup H of order 4 which is impossible because of Lagrangels theorem Let a E G with lal p and set Hz ltagt eaa2ap 1 As G H lGl Zpp 2 there are two distinct disjoint cosets of H in G So if b is any element in G H the two distinct cosets are H and bH bltagt bbaba2bap 1 We are now going to show that b2 e for all b E G H What we know is that b2H is either H or bH lf b2H bH then b b lb2 E H which contradicts the assumption that b H Therefore we must have b2H H ie b2 E H lf b2 e then b2 al for some 1 S l lt p and therefore lb2l lall p gcd lp p and therefore lbl 2p However we are in case 2 where it is assumed that lgl S p for all g E C so this can not happen Therefore we may conclude that b2 e for all b H Let us now x some b H ltagt Then ba H and therefore we know ba2 e which is to say ba bar1 a lb l ie bab 1 a l Therefore GHUbH akbak 0 S h lt n with ap e b2 e and bab ail But his is precisely our description of D1 lndeed recall that for n 2 3 Dn rkfrk 0 S h lt n with f2 e r7L e and frf r71 Thus we may map G A D217 via ak A rk and bak A brk This map is an isomorphism of groups 7 a notion we discuss next I 151 Homomorphisms and Isomorphisms De nition 158 Let G and G be two groups A function go G A G is a homomorphism if goab goago b for all ab E G We say that go is an isomorphism ifgo is also a bijection ie one to one and onto We say G and G are isomorphic there exists and isomorphism go G A G Page 48 job algebra Lemma 159 If go G A Gis an isomorphism the inverse map go l is also a homomorphism and go 1 G A G is also an isomorphism Proof Suppose that 113 6 G and a I go 1a and b I go 1 Then go ab go a go b a from which it follows that go 1 a1 ab go 1ago 1 b as desired l Notation 1510 Ifgo G A G is a homomorphism then the kernel of go is de ned by 16390 80 1 c I I 6 91801 ea C G and the range of go by Ranltso1so0 soy19 6 G C 5quot Example 1511 The trivial homomorphism go G A C is de ned by go 9 e for all g E G For this example ker go G and Ran G e Example 1512 Let G CL n R denote the set of n X n invertible matrices with the binary operation being matrix multiplication and let H R I R 0 equipped with multiplication as the binary operation Then det G A H is a homomorphism In this example ker det SL nlR I A 6 CL nlR detA 1 and Ran det R why Example 1513 Suppose that G R and H Rm both equipped with as their binary operation Then any m X n matrix A gives rise to a homomor phism1 from G A H via the map goA I Ax for all x E R In this case ker goA Nul A and Ran goA Ran A Moreover goA is an isomorphism iff m n and A is invertible 1 Fact any continuous homomorphism is of this form macro svmonob cls datetime 13Mar20099 O4 16 Lecture 16 2112009 Example 16 Suppose that G R and G 512 E Z 1 We use addition on G and multiplication of G as the group operations Then for each A E R go t 2 e0 is a homomorphism from G to G For this example if A f 0 then go t 1 iff At 6 27TZ and therefore ker goA 2Z and Ran goA 51 If A 0 go goo is the triVial homomorphismi Example 162 Suppose that G G 5391 I 2 E Z 1 Then for each n E Z gon I z is a homomorphism and when n i1 it is an isomorphismi If n 0 gon goo is the triVial homomorphism while if n f 0 gon 1 iff z 1 iffz 42ka for some h 012Hn71 so that ker gon 627 h 012n71gt while Ran gon 5391 Ci Theorem 163 Ifgo G A G is a homomorphism then 1 go e e E G 2 go a l go a71 for all a E G 5 go a go an for all n E Z 4 If lgl lt 00 then lgo divides lgl 5 so G S 0 6 ker go S G 7 go a go 12 i a lb E ker go aker go bker go and Go Ifgoa ae G then go 1a I z E G goz a akergoi Proof We prove each of these results in turn 1 By the homomorphism property soe soee soesoe and so by cancellation we learn that go e a E0 If a E G we have soesooo 1soosoa 1 and therefore go a l go a71i 3 W en n 0 item 3 follows from item 1 For n 2 1 we have so on so a on l so a so W from which the result then follows by induction For n S 1 we have so an so WW so a n fl so ltagt 1 ma 4 Let n lgl lt 00 then 909n 909 906 e Therefore lgogl divides n lgli 1f Ly E G goz and goy are two generic elements of goG Since so of1 so y so I ly 6 go G it follows that 0 a g as Ly are now in kergo iie goz e g0y7t en 5 533 lo soz 1soy e le e so 1 This shows I ly E ker go and therefore that ker go S Ci We have go a go 1 iff e go a71 go 12 go a lb iff a lb E ker We have I E go 1a iff go a go a which by 7 happens iff ailz E ker go iei iff z E aker go 007 Corollary 164 A homomorphism go G A G is an isomorphism i ker go e and go G Ci Proof According to item 7 of Theorem 163 go is one to one iff ker go ei Since go is onto iff by de nition go G G the proof is complete I Proposition 165 Classi cation of groups with all elments being or der 2 Suppose G is a nontrivial nite group such that 12 1 for all z 6 G Then G Z and lGl 2k for some h E Z1 Proof We know from Lemma 1516 that G is abeliani Choose a1 e and let H1ea1a 5 E Z2 S Ci 1f H1 G choose a E GH1 and then let H2 ai1a2 51 E Z2 S Ci Notice that ngl 11ng G choose a3 6 GH2 and let H3 a1a2a 3 51 E Z2 1f ailaggag ailagg then a3 6 H2 which is is not If ailaggag ailaggag then aila aila and therefore 5139 a for i 12 This shows that ngl 23 ie all elements in the list are distinct Continuing this way we eventually nd ai 1 C G such that Gai1 Mia 51 6Z2 with all elements being distinct in this list We may now de ne g0 Z A G by g051ui5k ailiuazki This map is clearly one to one and onto and is easily seen to be a homomorphism and hence an isomorphismi Indeed since G is abelian 6 6 6 6 51Hi5kg061ui6k a Hiazkaf Mia ailaf Hiazkakk E 5 d2 Ek a mod ai161 H akk l k 151 1m0 H alg k go51m5k61m6ki a Example 166 Essentially the same as a homework problem Recall that U 12 15 711 has all elements of order 2 Since lU 12M 22 we know that U 12 Z In this case we may take 5152 2 5517521 Notice that 5 7 35 mod 12 11 On the other hand U10 1379 lt3 1332 933 7 It will follows from Theorem 1711 below that U10 and U12 can not be isomorphici 17 Lecture 17 2132009 Theorem 171 If go G A G is a group isomorphism then go preserves all group related properties For example 139 ls09l lyl facallg 6 G 2 G is cyclic i G is cyclic Moreover g E G is a generator of G i go g is a generator of Cl 5 ab E G commute i go a go b commute in Cl In particular G is abelian i cG is abelian 4 For k E Z1 and b E G the equation 1k b in G and ik go b in C have the same number of equations In fact 1k b i go go b 5 K C G is a subgroup of G i go is a subgroup of G Proof 1 We have seen that lgo l lgl Similarly it follows that lsf1so9l l My i e yl l ls09l Thus Maul lol 2 If G g then G go G go showing G is cyclic The converse follows by considering go ll 3 If ab ba then go a go b go ab go ba go b go a The converse assertion again follows by considering go 1 4 We have 1k b implies go b go go Conversely if Ek go b then go 1 bl Thus taking 1 go 1 we have 1k b and E go 7 5 We know if K S G then goK S G and goK S G then K 9471 so 10 S G I Example 172 Let C C 0 and R I R 0 which are groups under multiplication We claim they are not isomorphic If they were the equations 24 1 in C and I4 1 in R would have to have the same number of solutions However the rst has four solutions 2 iLii while the second has only two i1 Proposition 173 Suppose that go G A G is a homomorphism and a E G then the values ofgo on a S G are uniquely determined by knowing a go a Let n I la and n lall 1 If n 00 then to every element a E G there is a unique homomorphism from G to G such that goa a If n 00 then ker go e while n lt 00 then ker go ail al il 2 Ifn lt 00 then to every element a E G such that nln there is a unique homomorphism go from G to G This homomorphism satis es a ker go ail al il and go a A a is an isomorphism i lal n n lall In particular two cyclic groups are isomorphic they have the same order Proof Since go ak go ak ak it follows that go is uniquely determined by knowing a go a 1 If n lal 00 we may de ne go ak k for all h E Z Then so algal so amt aml aka so 0416 at 7 showing go is a homomorphisml Moreover we have e go ak a iff n lal divides lh ile ker go al39 l E Z ail 2 Now suppose that n and n are nite and Then again we de ne go ak 2 If for all h E Z However in this case we must show go is well defined77 ie we must check the de nition makes sense The problem now is that ak h E Z contains repetitions and in fact we know that ak akm dnl Thus we must show go ak go ak mdn Write h sn r with r hmodn then wherein we have used a e since e now compute ker For this we have go ak 1k iff nlh and therefore ker go ak lls al39 l E Z ail Notice that ker go e iff n n and in this case go a a showing go is an isomorphisml If G and G are cyclic groups of different orders there is not bijective map from G to G let alone no bijective homomorphisml l Corollary 174 If G a and lal 00 then go G A Z de ned by go ak h is an isomorphism While if lal n lt 00 then go G A Zn de ned by go ak hmodn is an isomorphism 52 17 Lecture 17 2132009 Proof Each of the maps are well de ned by Proposition 173 homomor phisms onto Z and Zn respectively Moreover the same proposition shows that ker go e in each case and therefore they are isomorphism l Example 175 If go Z12 A Z30 is a homomorphism then golt1 h E Z30 where the order of lhl must divide 12 which is equivalent to h 12 0 in Z30 This condition is easy to remember since 12 0 in Z12 and therefore 0 go 0 go 12 k12 At any rate we know that Sol 16 12 or equivalently 5l 21 ie Slh Thus the homomorphisms are of the form gok hr where h E 0510152025 Furthermore we have go5 0 iff 51 0 mod 30 iff z 0 mod 6 iff z is a multiple of 6 ie z 6 lt6 1 We also have 05 Z12 lt5gt 1510152025 Z30 More generally one shows 30 Ran h ker k gcdk30 lkl gcdk30 lgcd lglzgo llkll wzu 0 30 1 lt0 lt30 Z12 lt1 5 5 6 lt5 lt6 10 10 3 lt10 lt3 15 15 2 lt15 lt2 20 10 3 lt20 lt10 lt3 25 5 6 lt25 lt5 lt6 as we will prove more generally in the next proposition Lemma 176 Suppose that mn h E Z1 then ml nh i gadg n lh Proof Let d I gcd ltmn m I md and n I nd Then gcd ltm n 1 Moreover we have ml nh iff Z 3 71 iff ml rth iff by Euclidls lemma mlh l Proposition 177 If go Zn A Zm is a homomorphisms then go gok for some h E Wgt where gok hr lt hr modm The list of distinct homomorphism from Zn A Zm is given by m m z 7 39 lt 7 y l k6ltgcdltmmgtgt thoikgcdmml Moreover Page 52 job algebra Ranwk so Zn W ltgcdm7kgt S Zm and kerltsogt ltlklzmgt Zn Proof Let d I gcd m n and m md By Proposition 173 the homo morphisms go Zn A Zm are of the form gok hr where h gok 1 must satisfy lhlZm ln ie geargm Alternatively this is equivalent to see the proof1 of item 4 of Theorem 163 requiring kn 0 in Zm ie that ml kn which by Lemma 176 is equivalent to m lh Thus the homomorphisms go n A Zm are of the form go gok where h E ltm lt swigW If is now easy to see that Ran gok US lt cd m 16 and from Proposi tion 173 we know that kerlt0k ltlklzm 391gt ltmgti Alternatively 0 gok iff hr 0 mod m ie iff ml hr which happens by Lemma 176 iff mlz ie z e M ltlklzmgt Zn Corollary 178 If mn E Z1 are relatively prime there is only one homomor phism go Zn A Zm namely the zero homomorphism Proof This follows from Proposition 177 We can also check it directly Indeed if go 1 h then 0 go 0 go kn modm which implies ml nh and hence by Euclidls lemma mlh Therefore go hr modm hmodm 1111061771 modm 0 1111061771 modm 0 for all z 6 Zn l 1 We can also see this using Lemma 176 By that lemma with the roles of n and k interchanged gcdlz m ln 111 ml macro svmonob cls datetime 13Mar20099 O4 18 Lecture 18 2162009 Notation 181 Given a group G let Aut G I go G A Glgo is an isomorphism We call Aut G the automorphism group of G Lemma 182 Aut G is a group using composition of homomorphisms as the binary operation Proof We will show Aut G is a subgroup of the invertible functions from G A Cl We have already seen that Aut G is closed under taking inverses in Lemma 159 So we must now only show that Aut G is closed under function composition But this is easy7 since if ab 6 G and go7 1 E Aut G then go o 1 is still a bijection with inverse function given by go o ibfl it 1 o go l7 and W 0 1b ab so W L110 so W a 1b 5 90W W80 W 1 W 0 1b a 39 W 0 1b b which shows that go o 1 E Aut G l Example 183 To each a E G let goa g I aga ll Then goa E Aut Indeed7 one has go1 goa71 and for z y E G 1 aza laya1 90a 80a 901119 azya Notice that goa idg iff a E Z G In particular if G is abelian7 then goa id for all a 6 Cl De nition 184 We say that god 9 aga l7 is conjugation by a and refer to goa as an inner automorphism The set of inner automorphism is then lnn G I goa E Aut G a E G Example 185 If go Z A Z is a homomorphism7 then go hr where h goll Conversely7 gok 2 hr gives a homomorphism from Z A Z for all h E Z Moreover we have ker gok lt0gt if h f 0 while ker goo Zl Since gokZ h S Zwe see that gokZ Ziffh ill So gok ZHZis an isomorphism iff h 6 i1 and we have shown see Proposition 1657 AutZgokhlorh71EZ2l To see that last statement directly simply check that 1 Z2 A Aut Z de ned by 1 0 gol and 1 l go1 is a homomorphisml The only case to check is as follows 901 WO 11 711 101121 907109071 soow 901 Theorem 186 Aut Zn 2 U All of the homomorphisms form Zn to itself are of the form gok hr modn for some h 6 Zn Moreover these gok is an isomorphism h E U Moreover the map U 3 h A gok E Aut Zn 181 is an isomorphism of groups Proof Since kn Omodn for all h 6 Zn it follows from Proposition 177 that all of the homomorphisms7 go Zn A Zn are of the form described More over7 by Proposition 177 Ran gok h ltgcd n7 hgt which is equal to Zn iff gcd n7 h 17 ie iff h E U For such a h we know that gok is also one to one since Zn is a nite set Thus Aut Zn gok h E U 18 Alternatively we have n k W ltng kngtgt which is trivial iff gcdzcm n7 iel gcd hn 17 ie h E Thus for h E Un we know that gok is one to one and hence onto So again we have veri ed Eq 182 Suppose that hl E U then with all arithmetic being done modn 7 ie in Zn we have gok a go h lz kl z gokl for all z E an This shows that map in Eq 181 is a homomorphism and hence an isomor phism since it is one to one and onto The inverse map is7 AutZn9gogtgplEUnl Third direct proof Suppose that hl 6 Zn then with all arithmetic being done modn 7 ie in Zn we have gpk a so 1611 hi I gold for all z E an Using this it follows that if h E U and h 1 is its inverse in Un then gogl 01671 so that gok E Aut Zn Conversely if d gcd hn gt 1 then 9 modn modn 0 which shows ker gok contains f 0 in an Hence gok is not an isomorphisml l Proposition 187 If go Z A Zn is a homomorphism then I hr hr modn where h l E Z Conversely to each h 6 Zn gok 2 hr de nes a homomorphism from Z A an The kernel and range of gok are given by Ran gok h gcd h C an Thus ker gok is never 0 and Ran gok Zn i h E U l and Proof Most of this is straight forward to prove and actually follows from Proposition 173 Since the order of h 6 Zn 1s gcdzzm we ave As a direct check notice that 0 gok hr modn happens iff nlhz iff n gchwL mornorphisrn lz iff z E ltgcdzzm lgtl We can also directly check that gok is a ho gok 1y hzymodn hz hyrnodn hzmodn hymodn 016 gok l Finally 9 Z W ltg0dk7ngt S u and therefore gok Z h Zn iff h is a generator of Zn iff gcd hn 1 iff h E U l l 19 Lecture 19 2182009 De nition 191 The external direct product of groups G1 G7 is GlanGlgtlt gtltG asaset with group operation given by 91gn 917 uyyl 9191gngl ie you just multiply componentwise It is easy to check this is a group with e I e e being the identity and 91gn 1 yflwwylll Example 192 Recall that U 5 1234 and Z3 012 and therefore U5XZ3ij1 i 4and0 j 2 Moreover we have 21 31 2 3mod511mod3 12 and 20 1 32 Example 193 Suppose that lGl 4 then G E Z4 or G E Z2 69 Z2 By La grange s theorem we know that lgl 1 2 or 4 for all g E G If there exists 9 E G with lgl 4 then G g E Z4 and if lgl S 2 for all g E G we know that G Z2 69 Z2 from results we have proved above In particular there are only two groups of order 4 and they are both abelian Fact 194 Here are some simple facts about direct products 1 GleGnl lall gtlt gtlt Gnll 2 Up to isomorphism the groups G1 69 69 On are independent of how the factors are ordered For example G1 69 G2 69 G3 9 91792793 A 93792791 6 G3 69 G2 69 G1 is an isomorphism 5 One may associate the direct product factors in any way you please up to isomorphism So for examp e Cl 69 G2 69 G3 9 91792 793 A 91792793 6 G1 69 G2 69 G3 is an isomorphism Remark 195 Observe that if g e egk e e and g eegle e for some l f h then 9 and g commute For exam ple in G1 gtlt G2 g1 e and eg2 commute since 9175 5792 91792 5792 9175 Theorem 196 Let g1 gn 6 G1 69 GB Gn then l91mynl 10ml91l7m7l9nlA Also see Proposition 133 Proof If t E Z1 then 917gnt e ee ltgt g efor alli and this happens iff lt for all i ie iff t is a common multiple of Therefore the order g1 gn must be lcm lgll l Example 197 Exercise 810 and 811 1 How many elements of order 9 does Z3 69 Zg have The elements of order 9 are of the form ab where lbl 9 ie b E U Thus the elements of order 9 are Z3 gtlt U 9 of which there are lstU9l3so93337318 Exercise 811 7 how many elements of order 4 are there in Z400 EB Z300 Recall that there is one subgroup of order 4 inside of Zn when 4ln which is gt All the elements of order 4 are inside this subgroup and hence there are go 4 2 of them The elements of order 2 in Zn are in and there is only one of them So Zn has 2 elements of order 4 and one each of order 2 and 1 The elements of order 4 inside of Zm 69 Zn are of the form ab where lal 1 or 2 and lbl 4 of which there are 22 4 of them or lal 4 and lbl 6 124 or which there are 24 8 so the total is 8 4 12 to 56 19 Lecture 19 2182009 Example 198 p 155 Example 5 Determine the number of cyclic subgroups of order 10 inside of Z100 69 Z25 The strategy is to observe that every cyclic subgroup H ltab of order 10 contains 10 1 4 4 elements of order 10 Thus if we count the number of elements of order 10 we must divide by 4 to get the number of cyclic subgroups of order 10 because no distinct cyclic subgroups of order 10 can share an element of order 10 We now count the number of elements a b E Z100 69 Z25 of order 10 Recall that labl lcm lal lbl and 100 1010 22 52 and 25 52 So in order to get an element of order 10 we must either 1 lal 10 and lbl 1 or 5 of which there are 10 go lgo5 4 14 20 of them or 2 lal 2 and lbl 5 ofwhich there are 2 go5 1 4 4 Therefore there are 20 4 4 6 cyclic subgroups of order 10 inside of Z100 69 Z25 Lemma 199 If G and H are groups such that G69 H is cyclic then both G and H are cyclic Alternatively put if either G or H is not cyclic then GED H is not cyclic Proof Let gh 6 G69 H be a generator of G 69 H Then every element of G 69 H is of the form ghk gkhk for some h E Z Thus every element of G must be of the form gk for some h E Z and every element of H must be of the form hk for some h E Z ie both G and H are cyclicl l Theorem 1910 Suppose that G and H are cyclic groups of nite order then G 69 H is cyclic i lGl and are relatively prime Proof Let m lGl and n and suppose that GED H is cyclic Then there exists ab E G 69 H such that labl mnl Now if d gcd mn then LIMP amiybna 636 676 so that d 2 labl mn and hence d 1 ie m and n are relatively primer Conversely if m and n are relatively prime and G a and H lt12 we have labl lcm mn mn lGEBHll Alternatively see Proposition 3 I Page 56 job algebra Example 1911 Using the above results Z10 BZ12 g Z2GBZ5 B Z4EBZ3 gZ2 BZ5 BZ4 BZ3 gZ5 BZ4 BZ2 BZ3EZ20 BZ5 and also Z10 69 Z12 g Z15 EB Z3 By the way mm 69 Zlgl 120 as is true of all of the other isomorphic groups appearing above Corollary 1912 Suppose that Gi is cyclic for each i then G1 69 GB Gn is cyclic and lGjl are relatively prime for all i f ji Proof This is proved by induction Rather than do this let me show how the case n 3 works First suppose that mi 2 and mj I lGjl are relatively prime for all i f ji Then by Theorem 1910 G 2 G2 69 G3 is cyclic and observe that 72127213 is relatively prime to mll Indeed look at the prime number decompositions Alternatively if d gt 1 is a divisor of m1 and 72127213 then by Euclidls lemma d is also a divisor of 7212 or 7213 and either m1 and mg or m1 and 7213 are not relatively primer So by another application of Theorem 1910 we know G1 69 G2 69 G3 2 G1 69 G is cyclic as well Conversely if 7212 and 7213 are not relatively prime for sake of argument then G 2 G2 69 G3 is not cyclic and therefore by Lemma 199 we know G1 69 G2 69 G3 2 G1 69 G is not cyclic as well I macro svmonob cls datetime 13Mar20099O4 20 Lecture 20 Review 2232009 Lemma 201 Let G be a group H S G and ab E H Then 1 G is the disjoint union of its distinct cosets 2 aH bH i ca lb E H Theorem 202 Lagrange s Theorem Suppose that G is a nite group and H S G then lGIHlX lHllGl7 where lG Hl I is the number of distinct cosets of H in G In particular divides lGl and lGl lG Hl Corollary 203 If G is a group of prime order p then G is cyclic and every element in G e is a generator of G Corollary 204 Fermat s Little Theorem Let p be a prime number and ap modp amodp Theorem 205 Ifgo G A G is a homomorphism then 1 go a go an for all n E Z 2 If lgl lt 00 then lgo divides lgl or equivalently go glgl e 5 go G S G and ker go S G 4 go a go b i ailb E ker go i aker go bker go and 5 Ifgo a a E G then go 1a I z E G goz a akergo Corollary 206 A homomorphism go G A G is one to one kergo e So go G A G is an isomorphism i kergo e and go G G Corollary 207 If G is a nite group and go G A G is a homomorphism then the following are equivalent 1 go is an isomorphism 2 ker go e 5 go is one to one 4 go G G ie go is onto Theorem 208 If go G A G is a group isomorphism then go preserves all group related properties For example 139 Maul lyl facallg 6 G 2 G is cyclic i G is cyclic Moreover g E G is a generator of G i go g is a generator of G 5 ab E G commute i go a go b commute in G In particular G is abelian i cG is abelian 4 For k E Z1 and b E G the equation 1k b in G and ik go b in C have the same number of equations In fact 1k b i go go b 5 K C G is a subgroup of G i go is a subgroup of G Theorem 209 Key Cyclic Group Facts Let a E G and n lal Then ai aj i i Ejmod n f hlm then am C ak oi aj gcd gcd j I ak agcdnk w lalgcd alyk ak is a generator of a i h E U If G is a cyclic group of order n there there are go I lU elements of order n in G which are given by ak h E U mN stakes A 2 Theorem 2010 Suppose that G is any nite group and d E Z1 then the number elements of order d in G is divisible by go d lU Theorem 2011 If G is a cyclic group then G E Z lGl 00 or G 2 Zn n I lGl lt 00 Proof Let a E G be a generator lf lGl 00 then go Z A G de ned by go h I ak is an isomorphism of groups If lGl n lt 00 then go Zn A G again de ned by go h I ak is an isomorphism of groups I Theorem 2012 Fundamental Theorem of Cyclic Groups Suppose that G a is a cyclic group 1 The subgroups of G are all of the form H am for some m E Z 2 fn lal lt 00 andHS G thenmz andH anm 58 20 Lecture 20 Review 2232009 5 To each divisor h 2 1 ofn there is precisely one subgroup ofG of order k namely H a Proposition 2013 If go Zn A Zm is a homomorphisms then go gok for Wgt where gok hx lt hx modm The list of distinct homomorphisms from Zn A Zm is given by m m z 7 39 lt 7 W k6ltedwumgt mmokltgawuml some h 6 Moreover Ranlt kgt so Zn W ltgcdm7kgt S Zm and mmwltwhltggszw Corollary 2014 If mn E Z1 are relatively prime there is only one homo morphism go Zn A Zm namely the zero homomorphism Theorem 2015 Let 91 9 6 G1 69 GB Gn then l91mynl lcmOylLAMlQnDA Theorem 2016 Suppose that G and H are cyclic groups of nite order then G 69 H is cyclic i lGl and are relatively prime Corollary 2017 Suppose that G is cyclic for each i then G1 69 69 G7 is cyclic and lGjl are relatively prime for all i f j 201 Examples Example 2018 Show all nontrivial subgroups H of Z are isomorphic to Z Solution from class we know that H for some n f 0 Now let go I nx for x E Z Then go is a homomorphism kergo 0 and go ltZ so go is an isomorphism Example 2019 Write out all of the left cosets of lt4 S Z and compute Z1 Answer lt4 0 lt4 1 lt4 2 lt4 3 lt4 7 this is it Why well these are all distinct since i lt4 is the only coset containing i for 0 S i S 3 Moreover you should check that every integer in Z is in precisely one of these cosets Thus it follows that Z 4 Page 58 job algebra Example 2020 Find Z12 First off recall that 3 W 4 and hence by Lagrange7s theorem lZlgl 12 wax 13 Z12 1 CW Example 2021 What are the orders of the elements which occur in the group G I Z5 69 Z10 To answer this suppose that ltab E G then we know lltabl lcm lal where lal E 1236 and lbl E 12510 Therefore one sees that lltabl 6 125 10 0 210 0 361530 0 630 12356101530 are the possible orders et us now compute the number element in G of order 10 This happens if lal 1 and lbl 10 or lal 2 and lbl 5 or 10 Noting that golt10 go 2 go 5 1 4 4 it follows that the number of elements of order 10 is 1414412 Example 2022 Suppose that go Z3 A Z4 is a homomorphism such that go 3 1 Find a formula for go and then nd ker Solution First off we know that lt3 ltgcd 83 lt1 Z3 alternatively 3 E Ult8 and is therefore a generator and therefore 3 is a generator of Z3 Hence it follows that go is determined by its value on 3 and since go 3 8 1 8 0 mod 4 it follows that there is such a homomorphism go Since 3 3 1 in Z3 it follows that golt1 golt33 Sgolt3 31 SinZ4 Therefore 901soz1zgo13zmod4 Now x E ker ltgo iff 3x mod4 0 ie iff 4lt3x iff 4lx Thus ker ltgo lt4 14 S Z3 Remark 2023 In general if h E U then we can nd st E Z by the division algorithm such that sh tn 1 Taking this equation mod n then allows us to conclude that h 3 mod n 1 in Zn For example if n 8 and h 3 we have 8232and321 and therefore 137237lt87233378 and thereforeSS 1 in Z3 macro svmonob cls datetime 13Mar20099 O4 Theorem 2024 Aut Zn 2 U All of the homomorphisms form Zn to itself are of the form gok hr modn for some h 6 Zn Moreover these gok is an isomorphism h E U Moreover the map Un 3 h A gok E Aut Zn is an isomorphism of groups 21 Lecture 21 Midterm II 2252009 22 Lecture 22 2272009 221 U n groups Lemma 221 If hn E Z1 and Mn then 04k U A U h de ned by 04k I zmodh is a homommphism Proof We rst must check that T 2 04k E U h for all z E U ie that gcd T h 1 To see this write I ah T and observe that if d is a common divisor of both h and T then d will divide z and n since Mn ie d is a common divisor of z and n But since I E U n z and n are relatively prime and therefore we must have d 1 ie gcd T h 1 and hence T E U The fact that Oak is a homomorphism follows from the basic properties of modh 7 arithmetic 04k zymodh Imodh ymodh modh 04k 04k 1 I If h is not a divisor of n then the map Oak is not well de ned in general For example say h 3 and n 10 then U10 13 7 9 and we have 133 3mod3 0 U3 De nition 222 F07 1971 6 Z1 with h gt 1 and Mn let Uk I kerak z E Un zmodh 1 S Example 223 If n 10 then U 10 13 7 9 and U2 10 U 10 while U5 10 On the other hand U3 10 1 7 lt7 S U 10 Example 2241fn 30 2 3 5 then U 30 1 711131719 23 29 U2 30gt U lt30 U3 30 1 7 13 19 U5 30 111 UB 30 1 7 13 19 U10 30gt 111 U15 30 Further let a U 30 A U 10 be the homomorphism a z mod10 then restricting a to U3 30 is given by 0 1 Us 30 U3 30 A U 10 I A zmod10 1 A 7 A 7 13 A 3 19 A 9 Notice that a U3 30 A U 10 is an isomorphism Similarly if we let 6 U 30 A U 3 be the homomorphism 1 mod 3 then restricting B to U10 30 is given by 5 lUg10 U10 30 A U 3 z A 1 mod 3 1 A 1 11 A 2 Therefore 6 U10 30 A U 3 is an isomorphism Lemma 225 Suppose that mn 2 2 aTe Telatively pTime then Um Un Proof By de nition I E Um mn Un iff z modm 1 and z modn 1 ie z am1 and z lm1 for some ab6 Z From these equations we see that am lm Hence Mam and it follows by Euclidls lemma that Ma Thus it follows that z nm 1 with an E Z ie z 1 mo nm 1 l Proposition 226 Suppose that mn gt 2 aTe Telzztz39vely pn39me then a Um A U de ned by a I z modn is an isomoTphz39sm Proof Since ker a Um Un 1 it follows that a is one to one So to nish the proof we must show a is onto ie to each h E U we 64 22 Lecture 22 2272009 have to nd an I E Um such that a zmodn h ie z qn h for some 0 S q lt m The condition that z E U is then 1 z modm qn h modm 221 We are now going to nish the proof by solving this equation for q 1 Since m and n are relatively prime there exists st E Z such that sntm 1 Taking this equation modm and replacing s by s modm if necessary we have found 1 S s lt m such that snmodm 1 2 Multiplying Eq 221 by s doing all arithmetic modm implies ssqnh qshian Solving this equation for 4 shows that q s 1 7 h modm 222 3 We now check that z qn h with q as in Eq 222 satis es 1 E U and a z modm Is First off doing all arithmetic in Zm we have zqnhs1ihnh 17hsnh1ihh1 ie zmodm 1 as desired So we are only left to check I E U Since h E U it follows that gcd z n gcd qn h n gcd h n1 Since I modm 1 we also know that gcd 1722 1 Therefore because m and n are relatively prime gcd zmn 1 by Euclidls lemma ie z E U l Lemma 227 Suppose that H K and G are groups and a G A H and G A K are homomorphisms then go G A H X K de ned by gog I a g 5 is a group homomorphism Proof This is a routine check so 9192 04 9192 75 9192 04 91a 92 75 91 92 a 91 7B 91 a 92 7B 92 so 91 so 92 I Theorem 228 Ifmn E Z1 are relatively prime then go U A U gtlt U de ned by go I I modm 1 mod n is an isomorphism of groups Page 64 job algebra Proof By Lemma 227 go is a homomorphism Since kergo z E Umn zmodm 1 and zmodn 1 Um Un 1 we know that go is one to one To see that go is onto let a b E U gtlt U By Proposition 226 there exists I 6 Un and y E Um such that zmodm a an ymo n b Then my 6 U and go go go I modm 1 mod n y modm ymod n lta1gtlt1bgtltabgt I Corollary 229 Ifm n E Z1 are relatively prime then go go go Corollary 2210 If n E Z factors as n p1 Hka with pi1 being dis tinct primes then k k s0ltngt 11p1p1 1gt Harm71 Fact 2211 Carl Gauss proved in 1801 that U 17 E anipna ifp is an odd prime and U 2 g 1 U4 13 Z2 while U 2 E Z2 69 Z2n72 for n 2 3 The only cyclic U 7 groups are the ones appearing in rst two rows of the above list 7 U is not cyclic for all other n Recall from Exercise 456 that it was shown that U 2 has two distinct elements of order 2 and therefore we already know that U 2 is not cyclic for n 2 3 222 Public Key Encryption Let us brie y explain the algorithm for sending public key77 encrypted mes sages For the input to this scheme the receiver of the message prepares 1 two large distinct primes p and 4 Let n 2 pg and observe that U n U 17 69 U q 2 21H 69 211 223 macro svmonob cls datetime 13Mar20099 O4 2 Compute m I lcm p 7 1 q 7 1 which is the maximal possible order of any element in U because of Eq 223 3 Choose any r E U other than 1 for example r m 7 1 would work 4 Tell the sender publicly to send herhis message M encrypted as R 2 MT mod n The message M should be a number in 1 2 min p q71 This latter condition ensures that gcd M n gcd Mpq 1 ie M E U The sender now sends hisher message M as R 2 MT mod n When the receiver gets the encrypted message R heshe uses the following algorithm to decode R back to the original message M 1 Compute s I r 1 E U This can be done by the division algorithm for nding st E Z such that sr tm 1 2 Observe that R MT as computed in U Since as we have seen above lMl lm it follows that Rs Mrs Mrs modm M1 M Thus we may recover the original message M from the encrypted message R via M R5 mod n 224 See the text book for an explicit example of the procedure in action 223 Extras This section may be safely skipped Remark 2212 Here is alternative proof of the assertion in Theorem 228 that U U gtlt U when m and n are relatively prime Recall that if ab E Zm gtlt Zn then h I labl lcmlal where m n 7 d l 7 a god mo 3 l god no Since any common divisor of lal and 1121 would have to be a common divisor of m and n we also know gcdlal 1 Therefore lal 39 lbl 1011100471171 39nglal7lbl 10mltlalslbl 1017101 for all a b E Zm gtlt Zn 1f la bl lal lbl divides m then we must have 1121 divides m as well How ever lbl divides n and therefore is a common divisor of m and n and is there fore equal to 1 and we must have b 0 Thus the only homomorphisms from Zm 7gt Zm gtlt Zn are of the form a 0610 for some h E Zm So accord ing to Lemma 2213 below if go Zm gtlt Zn 7 Zm gtlt Zn is a homomorphism Page 65 job algebra 223 Ektras This section may be safely skipped 65 then go I y hzly for some h l E Zm gtlt Zn Furthermore such a go is an isomorphism iff h E U and l E U Thus we have shown Um gtlt Un E Aut Zm gtlt Zn On the other hand since m and n are relatively prime we know that Zm gtlt Zn 2 Zmn and therefore Aut Zm gtlt Zn 2 Aut Zmn E U Thus we may conclude U gtlt U Aut Zm gtlt Zn Aut Zmn U The next lemma appeared on the second midterm Lemma 2213 Suppose that G1G2 and G are groups and go G1 gtlt G2 7gt G is a homomorphism Then 191 2 gogle and 592 2 goegg are homomorphism from G1 7gt G and G2 7gt C respectively Moreover the elements ofa G1 commute with all of the elements of G2 Conversely ifa G1 7gt G and G2 7gt G are homomorphisms such that the elements of aG1 commute with all of the elements of G2 then go 9192 2 a 91 B 92 is a homomorphism from G1 gtlt G2 7gt G See Proposition 2214 above as well Proof Observe that 1919 1 so 91916 so 9176 9176 so 917 6 so also a 91 a 9 1 showing a G1 7gt G is a homomorphism Furthermore a 91 B 92 so 9176 so 6792 so 9176 6792 so 91792 0 5792 917 5 0 5792 0 9175 B 92 0 91 which proves the commutativity property It is easy to check that go 9192 2 a 91 B 92 is a homomorphism I In this extra section we will put the proof of Theorem 228 into a more general context Proposition 2214 Suppose that G H and K are groups Then G is isomor phic to H X K i there exists homomorphisms go G 7gt H and 1 G 7gt K such that kergo keril e and go ker H and 1 ker go K Proof Suppose that 77 G 7gt H X K is an isomorphism of groups Since the projection maps on H X K are homomorphism it follows that 77 go where go G 7gt H and 1 G 7gt K are homomorphisms Moreover e kern ker go keril and since 77 is surjective for each h E H there exists a g E G such that he 779 go 9 1l Thus we see that g E keril and go 9 h showing go ker H Similarly we may show 1 ker go K macro svmonob cls datetime 13Mar20099 O4 66 22 Lecture 22 2272009 Conversely suppose that go G 7gt H and 7 G 7gt K such that kergo keriJ e and goker7J H and wker go K and de ne 77 I go7 G 7gt H X K It is easily checked that 77 is a homomorphism and the ker77 kergo kerw e Now suppose that h h E H X K and choose a E kerw and b E kergo such that go a h and 7 b h Then letting g I ah we nd 909soab90a90bh hand y ab a bekk This shows that 77 g h h and hence shows that 77 is surjective l Lemma 2215 Number Theoretic Suppose that st E Zur Then amod st bmod st implies amods bmods and amodt bmod t Moreover if gcdst l we have amodst bmodst amods bmods and amodt bmodt Proof First off amod st bmod st iff stl a 7 b amods bmods iff sl a 7 b and amodt bmodt iff tl a 7 12 Since it is clear that sl a 7 b and tl a 7 b if stl a 7 b the rst assertion is proved Moreover if gcd s t l and sl a 7 b and tl a 7 b then a7b ks and tlhs By Euclid s lemma this implies that tlh and therefore a 7 b st ie stl a 7 b so that amod st bmod st Alternatively use the fundamental theorem of arithmetic to prove the second assertion l Lemma 2216 Let abc E Z then gcd abc l i gcd ab l gcd a c Proof This is easily proved with the aid of the fundamental theorem of arithmetic Alternatively it is clear that gcd a b and gcd a c are divisors of both a and be and therefore if either of these is greater than 1 it would follows that gcd a be gt 1 Conversely if gcd a b l gcd a c there would exists st u v E Z such that sa 7 tb l and ua 7 UC 1 Hence it follows that 112 satb uavc Taking this equation moda then implies l tube moda from which it follows that gcd a be l l Lemma 2217 For all a b E Z we have I modab moda zmoda Proof Let r I 1 mod ab and write I ha 7 r Then I moda hab r moda rmoda z modab moda Page 66 job algebra Theorem 2218 Suppose that mn 2 2 and gcd mn 1 Then Umn 3 z 7gt zmodmzmodn E Um gtlt Un is an isomorphism In particular go I go go See Remark 2212 for another proof which is perhaps better Proof From Lemma 2216 we know that gcd 1 mn 1 implies gcd zm l and gcd z n 1 Thus ifz E U and r I zmodn we will have I hn r and hence l gcd z n gcd z r Therefore we may de ne maps go Umn 7gt Um and 7 Umn 7gt Un via go zmodm and 7 1 mod n Notice that both of these maps are homomorphisms lndeed go my modmn modn my modn z modn ymodn modn gozgo as desired Now goz 1 iff zmodn l and 7 1 iff zmodm 1 Therefore I E kergo keriJ iff nl z 71 and ml 1 71 As gcd m n 1 it follows by Euclid7s lemma that mnl z 71 as well ie zmodmn l and we have shown kergo keriJ As before we denote kergo by U7 and kerw by Um To nish the proof we must now show 7 Un U and so Um om U n Let 0 S h lt n and choose 1 S s lt m such that sn modm 1 which is possible since gcd m n 1 We claim there is an L E Z such that qn h modm 1 If such a 4 exists we must have s s qn k modm q 7 sh modm which is to say 4 s l 7 h modm Conversely if we take 4 I s l 7 h modm then qn h modm sn 1 7 h h modm 17 h h modm 1 With this fact in hand we see that for all h E U we can nd a 0 S q lt m such that qn7h modm 1 Thus if we let I I qn h we will have zmodm 1 so that gcd zm 1 and zmodn It so that gcd zn gcd hn l and therefore gcd zmn 1 Thus 9 I zmodmn satis es gcd gmn l ie g E U Moreover go 9 gmodn qn h modmn modn qn h modn h and 7 g gmodm qn h modmn modm qn h modm 1 Thus we have shown goker Similarly we may show 7 ker go U The result now follows by an application of Proposition 2214 I macro svmonobcls datetime 13Mar20099O4 224 Permutation Groups The following proposition should be veri ed by the reader Proposition 2219 Permutation Groups Let A be a set and S A I a z A A Al 0 is bijectivel If we equip G with the binary operation of function composition then G is a group The identity element in G is the identity function 5 and the inverse 0 1 to a E G is the inverse function to at De nition 2220 Finite permutation groups For n E Z1 let 1 121Hn and 5 I 5An be the group described in Proposition 2219 We will identify elements a 6 57 with the following 2 X n array 1 2 n a1a2 0n Notice that lSnl nl since there are n choices for a 1 n7 2 for a 2 n7 3 fora3lu1foranl For examples suppose that n 6 and let 5 itheidentity and 7 123456 243165 We identify a with the following picture 1 2 3 4 5 6 The inverse to a is gotten pictorially by reversing all of the arrows above to n 1gtgtlt1lt4 5X6 6 or equivalently Page 67 job algebra 224 Permutation Groups 67 1 2 3 4 5 6 1 1 2 3 4 5 6 a l 41 3 2 6 5 and hence Of course the identity in this graphical picture is simply given by 1 2 3 4 5 6 1 2 3 4 5 6 Now let 6 6 55 be given by 67 123456 214635 gtlt W6 1 2 3 or in pictures We can now compose the two permutations B o a graphically to nd 1 2 3 4 5 6 which after erasing the intermediate arrows gives 1 2 3 4 5 6 l 1 2 3 4 5 6 In terms of our array notation we have macro svmonob cls datetime 13Mar20099 O4 68 22 Lecture 22 2272009 5 7 123456 123456 oa 214635 243165 123456 164253 It is also worth observing that B splits into a product of two permutations 712345 12345 213456 124635 7123456 123456 7124635 2134567 corresponding to the noncrossing parts in the graphical picture for Each of these permutations is called a cycle Lemma 2221 Suppose that a 6 Sn and 1 S I S n then there exists It 2 1 such that 0k 11 Let h 2 1 be the minimal such 16 then 075 a I 1 a 1 1 1 akm 1 are distinct element in 171 We call 075 a the orbit of I under 01 Proof As in is a nite set it follows that am 10 are not all distinct elements and therefore am a for some l lt m and therefore 0k z wherehm7l211 Now let h h be the minimal 16 2 1 such that 0k 11 if 10 1 1 1 ak 1 were not all distinct then oi aj for some 0 iltj k7l anditwould follows that aj iz zwithlgj7ilt k7l which would violate the de nition of h 1 l De nition 2222 Given a 6 Sn and z E An we say 075 a is trivial 075 a ie a 11 Further let F01z AnzO a1zElnzazz be the xed points of 01 123456 Example 22231fa 2 4 316 5 then the orbits of a are 01 17274 02 047 03 3 and O5 56 051 Page 68 job algebra Notice that the orbits have partitioned 15 into disjoint sets In this case F 31 Also observe that the action of a on each of the orbits is rather simple For example the action ofa restricted to 01 may be summarized by 1 A 2 A 4 A 11 In fact we may summarize the action of 0 via the rules 4 e72 T 3 3 3 and 5 3 6 1 We will abbreviate this permutations as a 124 3 56 1 Here 124 is a 3 7 cycle 3 is a one cycle and 56 is a two cycle We say these cycles are disjoint since they have no elements of A5 in common We will formalize these notions now1 De nition 2224 An element a 6 Sn is said to be a cycle if it has at most one nontrivial orbit Alternatively put for all z F0 075 a An F01 Notation 2225 If a f 5 is a cycle and z is any element in the nontrivial orbit of a then we abbreviate a by a 10 z111al 1 where h is the rst time that 0k 11 Lemma 2226 fa a1111am is a cycle then 101 m1 The following lemma is sometimes useful1 Lemma 2227 Suppose that a a1111am is a cycle in 5 and 739 6 5 is any other permutation Then 7 I 70771 739 a1111739am 2215 so in particular conjugation of a m 7 cycle by some 739 6 Sn is again an m 7 cycle Proof Conjugation by 739 has the effect of relabeling 1 21 1 1 n to 739 1 1 1 1 739 1 Formally observe that ifj a1111 am then 7 T 139 T a 139 71 so that 739 is xed by 71 Moreover since 7k TO39k h12111m we nd VWTWDTUM WTWDT60TWMA From these observations we learn that 707 1 is given as in Eq1 2215 l 7 1 and ak Tk l al for macro svmonob cls datetime 13Mar20099O4 23 Lecture 23 322009 De nition 231 We say that two nontrivial cycles a a1l am and 739 121 127 are disjoint ah am 121 bn 0 Equivalently put the nontrivial orbit ofa and 739 should be disjoint It is easy to check that 0739 739039 whenever a and 739 are disjoint cycles Theorem 232 Every permutation a f 5 may be written as a product of non trivial disjoint cycles which are unique modulo order Since they all commute the ordering of the cycles in this product is irrelevant Proof Sketch Let i N j iff i 6 010 ile iff i 0k for some h E N This is easily seen to be an equivalence relation and therefore it follows that the distinct orbits of a form a partition of Anl Suppose that 01 0k are the distinct orbits of a and let i E 0 be a chosen point in each of these orbits For each l we let a I ila 02 Hamquot1 where m 2 1 is the rst time an ill One then checks that a 01 akl l Example 233 Here are some examples 2 i 3 i g 124 lt3 56 124 56 55 124 3 1 2 g i 132 465 465 132 124 413 13 24 24 13 413 124 12 34 124 513 13524 and 513 124 12435 Lemma 234 fa is written aproduct of disjoint cycles 01 0k then 101 lcm loll lakl Proof Let t E Z1 such that a 5 then 80 01 az taiuafc which can only happen if a 5 for each i why Therefore lail lt for all i ie t is a common multiple of loll lakl Therefore the order 0 a is the least common multiple of loll lakl This also could be proved by induction using Proposition 133 and Corollary 132 l Example 235 The for permutations appearing in Example 233 have order lcm 2 3 6 lcm 33 3 lcm 22 2 and 5 respectively Example 236 Let us observe that if 123456 a 243165 then 123456 35a 245163 a36 and 1 2 3 4 5 6 26a 643125 a15l Feel free to omit the following comment More generally if 739 6 55 then 2 3 4 7 1 5 6 W7 72T4T3T1T6T5 while 0739 can be viewed in the nonstandard form as UT 7 1 1 7 1 2 7 1 3 7 1 4 7 1 5 7 1 2 4 3 1 6 5 i The latter statement is easily veri ed by applying both sides to 7 1 for i12lu6l Using the above example we can easily prove the following proposition Proposition 237 Every permutation a 6 57 may be written as a product of two cyc es Proof The main point is to repeatedly use the following observationl If a 6 Sn and 1 S i lt j S n then the permutation 739 6 57 de ned so that 739 a 739 a and agrees with 739 otherwise may be expresses as either 739 aiaja or Taijl 7O 23 Lecture 23 322009 Example 238 Let us show how to write 712345 24531 as a product of 2 7 cycles We rst transform a to 5 by a series of ips ips 12345 5 24531 12 14532 24 12534 35 12354 45 12345 which is to say 45 35 24 12 a e and therefore a 45 35 24 3171 12 24 35 45 as can be veri ed directly There are of course many ways to do this so this representation is far from unique Lemma 239 Every two cycle may be written as a product of an odd number of two cycles of the form ii 1 for some 1 S i lt n Proof Suppose that i 1 lt j then 232 1 m 232 1 2 11 and therefore 23139ii1i1jii1 The proof now follows by induction Here is an example to see how this works in practice 273 374 475 37 4 27 3 273 375 273 27 5A I Combining Lemma 239 with Proposition 237 gives the following corollary Corollary 2310 Every permutation a 6 Sn may be written as a product of 2 7 cycles a 01H lam where each a is of the form aa 1 for some 1 S a lt n Page 70 job algebra 231 The sign of a permutation De nition 2311 We say a 6 Sn has an inversion at a b if a lt b while a a gt a Given a 6 Sn let 10 2 ab a lt b andaa gt a b NW 1 I0 Z 10igtoj7 and 1 iltj n sgnm AWN We call sgna the sign of a The main theorem see Theorem 2314 of this section states that sgn 5 A i1 is a homomorphism such that sgnij 71 for all i f ji Example 2312 For example if a 12345 34521 then 10 1747175727472757374737 504475 gt Na22217 andsgna71 while 12345 12345 45 1354211 and 23 1245311 sothat 145W074175727372747275737473757475 gt Na23218andsgna1 and Iltlt23gt a 11 15 24 25 34 35 45 gt Na 12216 andsgna1 where the hatted term is to be omitted from the list The following lemma generalizes this example Lemma 2313 If a 6 Sn and 1 g i lt n then Nii 1 a E N a 1 mod 2 or equivalently sgnii 1 a isgnal macro svmonob cls datetime 13Mar20099 O4 Proof Let 739 I iila and a I 0 1 and b I a 1il so that a a i anda b ili lfa lt b then a z 1a andIT IUUa 12 so that N 739 N ali While ifa gt 127 then ha 6 10 and 17 Ia 12 a and N 739 N a 7 1 In all cases we have N 739 E N a l rnocl2i Therefore Sgnm 71N7 71N7mod2 71No1mod2 71NU1 isgnai Theorem 2314 The function sgn Sn H il given by sgna I 71N0 is a homomorphism of groups Proof If a 6 Sn is written using Corollary 2310 in the forrn7 a aliuame where 5 is the identity permutation and each 01 is of the form a7 a l for some 1 S a lt n7 then by Lemma 23137 we know that sgna sgnalag i i i 0mg 71 sgnag i i i 0mg 702 sgnag i i i 0mg Hi 1msgn51mA Therefore if 739 6 Sn is another permutation and 739 7391 i i i m with Ti of the form a7 n1 for some 1 S a lt n7 then sgn7 71 7 039739 01 i i i amn i i i m and so sgn07 Dmk 1m1k sgn0 sgn 24 Lecture 24 342009 De nition 241 Alternating Groups For each n E Z let An I ker sgnsn S SW We call An the alternating group on n 7 letters Elements of An are said to be even while those not in An are odd ie o 6 5 is even if sgna l and odd if sgna 71 Corollary 242 Even 7 Odd Theorem If a ab with a y b then sgna 71 ie a b is odd More generally ifa 01 on where each a is a two cycle then sgna 7lnl So any decomposition ofa as a product of 2 7 cycles must have an odd number of terms if sgna 71 and even number of terms if sgna 1 Proof The second assertion follows from the rst because of the homomor phism property of sgn For the rst recall from Lemma 239 that a b may be expressed as a product of an odd number of adjacent ips 01 amt Therefore sgnalz 7lm 71odd 71 Example 243 Let us compute sgn2465l To do this observe that 26 25 2465 26 246 24 so that 2465 25 26 24 and it follows that sgn 2465 sgn 25 sgn 26 sgn 24 71 The general result is the content of the next corollaryl Corollary 244 fa is an in 7cycle then sgna 7lm71l So cycles of odd length are even and cycles of even length are odd Proof If a a1a2 am is a m 7 cycle then a1a2a a1a2a1 a2 am a1 a2 am a2 am or equivalently a a17a2 03927 H7039m Thus it follows by induction that a a1 a2 a2 a3 am72 am71 am71 am 241 Alternatively a1am a a1 am a1a2l am am a1 a2 am71 a1a2l am71 and therefore a a1am a1a2ul am71 a1am a1am1 a1 a2 Using either of these forms for a we learn that sgna 7lm71l I Example 245 What are the possible order of elements from S4 The elements of 54 have the following possible cycle structures K1234 4 K123 4l 3 242 K12 lt34 7 2 7 WM 5 1 Thus the possible orders are l 2 3 4 If we restrict to A4 we see that only 1 2 3 are now possible Note well both 12 34 and 12 have order 2 while sgnl2 34 l f 71 sgnl2 Therefore you can not compute the sign of an arbitrary permutation a just by knowing its order 74 24 Lecture 24 342009 Example 246 In this example we wish to compute the number of elements of order 3 inside of A4 From the form in Eq 242 we see that we have 4 choices for the element left out of the three cycle For each such choice there are two distinct three cycles For example if 4 is omitted from the three cycle then we have the two choices 123 and 132 Therefore there are 2 4 8 elements of order 3 in 4 Theorem 247 For each n 2 2 lAnl nl2 Proof This will be an easy consequence of the rst isomorphism theorem to come later Here is another proofl Since sgn 12 a esgnltagt it follows that 12 An not the cosets 5A and that these cosets are dis jointl Moreover if a 6 Sn then either sgna 1 in which case a E An or sgn 12 0 1 in which case a E 1 2 AW This shows lSnl 2SnAniii PM PM I Example 248 Converse t0 Lagrange s Theorem is False In this example we wish to show that A4 has no subgroup of order 6 even though 61 1A4 12 Suppose that H S A4 is a subgroup of order 6 Let a 6 A4 with 101 3 As A4 1H 2 we know that H O39H and 02H can not all be distinct 1f O39H 02H or O39H H we know that a E H and if 02H H then a2 E H and hence a a4 E H as well So in all case a E H This shows that A4 must contain all 8 see Example 246 the elements of order 3 in A4 which is absurd since 6 lt 8 Example 249 What is the maximal order of an element of AF Well we must divide 6 into an even number of bins If there are 2 bins we have 6152433with maxlcm5 if there are 4 bins then 611221113with maxlcm3 and so the maximal order is 5 Example 2410 What is the maximal order of an element of Ag Well we must divide 8 into an even number of bins If there are 2 bins we have 817263544with maxlcm15l Page 74 job algebra If there are 4 bins and there is a 1 in one of the bins we must consider 115124133223with maxlcm6 so we may assume no one appears and there are four bins we must have 8 2 2 2 2 which is not helpful If there are 6 bins then we must have at least two ones and we are back to A5 Thus the maximal order of an element in A3 is 15 Theorem 2411 Permutations and Determinants If A is an n X n 7 matrix then det A Z sgnaA101l Am 243 065 Proof Let us rst do the cases n 2 and n 3 by hand For n 2 det A det ll A 2 1 J 14111422 7 14121421 21 22 while 52 5 12 so that Z SgnaA1Ul 39 A202 14111422 7 A12A21 det A i 0652 Similarly by expanding det A by cofactors across one shows A11 A12 A13 det A det A21 A22 A23 A31 A32 A33 A1114221433 A1214231431 A1314211432 7 A1114231432 7 A1214211433 7 A13A22A31A Notice that there are 6 153 terms in this sum with each term corresponding to a permutation For example the third term corresponds to the 3 7 cycle a 132 with sgna 1 The fourth term corresponds to the transposition a 23 with sgna 71 1n the rst row each term is a 3 7 cycle with 1 for its signature and in the bottom row each permutation is a transposition with signature being 71 These observations complete the proof of Ed 243 for n 3 For general n let us make use of basic facts about the determinant functionl Let ei1 be the standard basis for R thought of as row vectorsl Then since det is a multilinear function of its rows macro svmonob cls datetime 13Mar20099 O4 n 2111 A1i1ei1 det A det 211 Anuei n n eii 2 A11Adet i11 in1 61 We also recall that the determinant is zero if any two rows are equal so the above sum may be reduced to 501 det A Z A101Anmdet Sn 06 6 Since the interchange of any two rows produces a 1 factor it follows that 501 51 det sgna det sgna eon en and the result is proved I 241 Symmetry and Transformation Groups Theorem 2412 Cayley s Theorem Every group G is isomorphic to some subgroup of a permutation group Proof To x ideas we will suppose that lGl lt 00 and let 5G be the permutation group on the alphabet of letters from G We then de ne a homo morphism go G A S G via go g I Lg where Lg G A G is left translation by G ie ng yr for all z E G Notice that L1 Lga and so 9 0 so 0 I LthI 9hr Lghr so oh I which shows go gh gog a go Thus go is a homomorphism of groups Moreover if go g idg then in particular e go g e ge g which shows ker go e Therefore G is isomorphic to go G C S G l Notice that in Cayleyls theorem if lGl n we are embedding G into 5 where lSnl nl We can often do better Page 75 job algebra 242 Normal Subgroups 75 Example 2413 We may embed Dn inside of 5 for each n lndeed let v1vn be the vertices of the n 7 gon which is xed by D7 Then for g 6 D7 let go g 6 5 be de ned by go g j if gvi vj ie gvi vwgw Observe that on one hand 919M 91vs092i v momma while on the other 919215 vsog192i Thus it follows that go 9192 go gl 0 go g2 so that go Dn A 5 is a homo morphism Moreover if go g id then gvi vwgw vi for all i and therefore g Id 6 D7 Therefore go D7 A go D7 S 5 is an isomorphism of groups Corollary 2414 When n 3 53 2 D3 For n 2 4 D7 and 5 are not isomorphic Proof Given example 2413 we need to show go D3 53 However ngl 6 153 and go is one to one and therefore it is onto Alternatively just convince yourself that D3 move the three vertices of the triangle to all possible locations When n 2 4 the groups have different orders 2n lt nl and hence are not isomorphic I 242 Normal Subgroups Theorem 2415 Let G be a subgroup and H S G be a subgroup Then the following are equivalent 1 gHg 1 C H for allg E G 2 gHg 1 H for all g E G and 5 gH Hg for all g E G ie right and left cosets are the same Proof In this proof we will make use of the fact that right and left mul tiplication by any g E G are bijections on G and hence preserve set inclusions and equalities With this said the proof is straightforward l ltgt 2 If item 1 holds for all g E C it holds for g 1 E G and therefore g ng C H Multiplying this relation on the right by g and left by g 1 shows H C gHg 1 which combined with the original expression in item 1 shows that gHg 1 H ie item 2 holds The converse direction is trivial 2 ltgt 3 If gHg 1 H then multiply the identity through on the right by g to learn gH Hg Multiplying this identity through on the right by g 1 then takes us back to 2 l macro svmonob cls datetime 13Mar20099 O4 De nition 2416 A subgroup H g G is said to be normal if any one of the equivalent conditions in Theorem 2415 hold We will write H lt1 G to indicate that H is a normal subgroup of G Lemma 2417 Every subgroup of an abelian group is normal The center of any group is a normal subgroup Any subgroup of the center including e is also a normal subgroup Proof If G is abelian then ghg 1 h for all h E G and therefore gHg 1 H for any subset H C G Thus all subgroups are normal If H Z G then ghg 1 h for all h E G and therefore gHg 1 H I Be aware then H S G can be a normal subgroup even if ghg 1 h for h E H and g E G The condition of being normal only says that ghg 1 E H not that it is equal to h see Example 2419 below Lemma 2418 If 0 G A K is a homomorphism of groups then ker go is a normal subgroup of G More generally ifN lt1 K then 0 1 N lt1 G Proof If a E G and z E ker go then so Mail so a so I so 0071 so a 680 071 6 Therefore aza 1 ker go for all a E G and z E ker go ie aker go a 1 C ker Let H I 0 1 N where N lt1 K Then for g E G and h E H we have so ghg l so yso hso 971 6 so 9Nso 9V1 N which shows that ghg 1 E 0 1 N H Thus we have shown H lt1 G as well I Example 2419 lfn E Z1 then An lt1 5 as it is the kernel of sgn Sn A i1 Alternatively see Example 253 below When n 3 we have A3 5 123 132 Notice that 12 123 12 1 12 123 12 132 yo 123 Example 2420 The subgroups H z 8 12 S 53 of 53 is not normal In deedb 13 12 1371 13 12 13 23 H Alternatively notice that 13 H 13 7 13 12 13 7 123 while H 13 13 12 13 13 132 3 13 H 25 Lecture 25 362009 Example 25 Let G CL nlR denote the set of n X n invertible matrices with the binary operation being matrix multiplication and let H I R 0 equipped with multiplication as the binary operationt Then det G 7gt H is a homomorphism Ran det R 0 and kergo SL nR A e CLnR detA 1 This shows that SL nR lt1 GL mm It also follows that H z A e GLnR detA gt 0 lt1 Guam Indeed H det l BL and R 000 lt1 R 0 Example 252 Translation and Rotation Subgroups Let G denote the Eu clidean group of R2 consisting of transformations of the form Tz RzawithR 02 andaERQt lf 51 R z a then SoTz RRera a RRz R aa is another Euclidean transformation It also follows from this that T71 R711 7 Rila is back in G Thus G is a subgroup of the bijective maps on R There are two natural subgroups in G namely the rotations O 2 S G and the translations H 2 Ta a E R2 S G where Ta I z at If R 6 02 and Ta 1 I z a we have TaRTa TaR z 7 a Ta RI 7 Ra RI 7 Ra a which shows that 02 is not a normal subgroup of Cl On the other hand if Tz RzaandTbE K then T a T5 0 T71 T a T5 R711 7 Rila T R711 7 Rila b RR7117R71ab az7aRb z Rb TRbt This shows that H lt1 Gt Example 253 If G is a group and H S G with lG Hl 2 then H is normal To see this let a H then G is the disjoint union of H and Ha and also of H and aHt Therefore Ha G H aHt 251 Factor Groups and the First Isomorphism Theorem Suppose we have a homomorphism go G 7gt K which is onto but not injectivet We would like to nd some way to make an isomorphism out of so To see what we should do let H I ker go and recall that for any h E K go l h gker go gH where g is any element in go 1 h t So to make go injective we need to identify all the points in 9H Hg as being the same That is we want to make a new group whose elements are the left cosets of H in G ie the new group should be GHt We then de ne g2 GH 7gt K by so gH g for any 9 6 Gt The map g2 GH 7gt K is now one to one and onto Moreover if it makes sense and it does see Theorem 254 to de ne a group structure on GH via the formula 91H 92H gngH for all 9192 6 G 251 then we will have proved the rst isomorphism theorem namely g5 GH 7gt K is an isomorphism see Theorem 256i Theorem 254 Factor Quotient Groups IfH lt1 G then the multipli cation rule in Eq 251 is well de ned and make GH into a group Moreover 7r G 7gt GH de ned by 7r 9 2 9H is a surjective group homomorphism with ker 7r H t Proof The main thing we have to show that the multiplication rule in Ed 251 is well de ned Namely if 1H 91H and 2H gH then gngH 1 2Ht To see this is the case recall that 91H giH ltgt gfl l hl e H and 2H 92H ltgt 927192 h2 E H Now consider 78 25 Lecture 25 362009 71 7 a 2 2 9192 9192 92 191 19192 92 1h192 921929 1h192 h2 9 1h192 E H wherein we used the normality of H in the last line This shows that gngH glggH as desired The proof that GH is a group is straight forward lndeed H eH is the identity element gH 1 g lH and the multiplication rule is associative since the binary operation on G was associative By construction 7r G A GH is operation preserving irei W 9192 9192H 91H 39 92H 7F 91 39W 92 So it only remains to show ker 7r H which we do now g6ker7r ltgt 7rgeH ltgt gHH ltgt gEHi I Corollary 255 A subgroup H S G is normal i it is the kernel of some homomorphism from G to another group Given our discussion before Theorem 254 we have also proved the rst isomorphism theorems Theorem 256 15t Isomorphism Theorem Suppose go G A K is a surjective homomorphism and H I ker Then go GH A K de ned by go gH go g for all g E G is an isomorphism of groups Notice that we have factored go through 7r ie go go a 7L This is often summarized by the saying the following diagram G L GH so O so K Example 257 Since go Z A Zn de ned by go 16 hmodn is an onto homo morphism with ker go nZ it follows that go Z A Zn is an isomorphism where go h h mod n Example 258 Since go Z5 A Z3 go xmod3 is a homomorphism with x E ker go iff x is a multiple of 3 iieiker go 03 we have Z503 3x03 meodSEZg is an isomorphism of groups Page 78 job algebra Example 259 Let go R A 5391 be de ned by got9 2 e112 Then go is a homomorphism with ker go Zr Therefore RZ 51 So called periodic boundary conditions Notice that 01 3 x A x Z E RZ is a bijection Example 2510 Let G be any group and de ne go G A Aut G via go g gxg li Notice that so 91 0 so 92 I 91 9219271 91 9192 I 9192 1 so 9192 I which shows that go is a homomorphismi Moreover g E ker go iff go g id iier iff gxg 1 x for all x E G irei iff g E Z G 1 Therefore it follows that 62 lt0 o so 0 Inn 0 where go G Inn G are the so called inner automorphisms of Cr Here is a variant of the rst isomorphism theorem which has essentially the same proofs Theorem 2511 15t Homorphism Theorem Suppose go G A K is a surjective homomorphism and H is a normal subgroup of G such that H C kergoi Then go GH A K de ned by gogH gog for all g E G is a homomorphism of groups Again we have factored go through 7r G A GH ie 0 5 0 7r G L GH so O so K Moreover ker go 7r ker xH x E ker Example 2512 Suppose that go Z A Zm is de ned as usual by gox I xmodm and h lm for some l E Zi Then 16 S ker go and there fore there exists a homomorphism go Z k A Zm such that gox xmodmi Furthermore we know that Z k 3 x h A xmodh E Zk is an isomorphisms Therefore it follows that A HZM an xgtxhgtxmodm is a homormorphism of groups A fact we have seen before macro svmonob cls datetime 13Mar20099 O4 26 Lecture 26 392009 Lemma 261 An order observation Suppose that go G A C is 2 onto homomorphism and H S G and H I go 1 Then H S G and lHl lkergol 261 Proof If h1h2 E H then go hflhg go h171go hg E H which shows that hflhg E H Thus H S G as claimed To prove 261 let us ob serve that for any onto function f z X A Y X is partitioned by the sets f l z y E Y Therefore le Z lf 1yll 262 yEY Applying this to go H A H making use that go 1 hker go provided go h h we learn that W lhkersol Z lkersol lHl lkersoll he he Lemma 262 fa and b be elements from a group G then labl lbal Proof Let go I aza l so that go 6 lnn G C Aut Since goba a ha a 1 ab and automorphisms preserve order it follows that labl lbal Alternative Proof Notice that own abab ab a bah aha ail a Una oil so that e awn iff e a Una oil which happens iff e ailea Una and therefore labl lbal l Example 263 Since sgn 5 H i1 is a homomorphism with ker sgn An it follows that SnAn 2 i1 2 Z2 Theorem 264 The GZ Theorem Let G be a group with Z ZG If GZ is a cyclic group then G is a abelian ie Z G Proof Let g E G be chosen so that GZ 92gt ngz k e Z Recall that it follows that G UkeZQkZA So if Ly E G then I gkzl and y gl22 for some hl E Z and 2122 6 Z Therefore 19 9k219l22 9k9l2122 gkl2122 while or 992991 9162221 gkl2122 my The contrapositive of this theorem is the statement that if G is nonabelian then Z G can not be too big Here is an example Corollary 265 Let pq be distinct primes and G be a nite nonabelian group of order pq Then Z G e Proof Let Z ZG lt1 C By Lagrange7s theorem lZl lpq and therefore lZl is either 1 p q or pq If it is one we are one and it can not be pq since G is nonabelian So suppose that lZl p Then lGZl g which is prime and hence must be cyclic In this case it follows that G is abelian by Theorem 264 Thus lZl p is not allowed and similarly lZl q is not allowed as well Therefore lZl l and we are done I 261 Internal Direct Products Lemma 266 Suppose that H and K are two normal subgroups ofG and H N Ke thenhhhhforallh6H andhEK 80 26 Lecture 26 392009 Proof If h E H and h 6 K7 then using normality of both H and K we nd7 K 3 hkhil kil hkhilkil h khilkil E H and therefore hhh lh l E H N K e7 ie hhh lh l e That is7 hh hh forallhEHandhEK l Proposition 267 Suppose that H and K are groups inside G which are nor mal and satisfy H K e and HK G Then G 2 H69 K Proof De ne a H A G and K A G to be the homomorphisms7 ah h and h for all h E H and h E K Then by Lemma 266 and the rst problem on Test 2 we know that g0 H X K A G de ned by 800177 10050 M is a homomorphism For sake of completeness here is the proof so 017 k W 7W 0 WI77615 hhkk hkhk MUM sow715 as required by the homomorphism property We now show so is an isomorphism First off hJc E kerg0 ltgt hh e ltgt h h 1 E H K e ltgt hJc ee which shows ker g0 e7 e Since g0 H 69 K HK G by assumption7 the proof is compete l De nition 268 When H and K are normal subgroups ofG such that H K e and HK G we say that G is the internal direct product ofH and K and write G H X K Remark 269 Suppose that G H 69 K where H and K are groups and let H 2 H69 e and K I e B K Then it is easy to check that G H X K7 ie G is the internal direct product of H and K Example 2610 If V7 W are subspace of a vector space Z7 then Z is the internal direct product of V and W iff V N W 0 and V W Z This is precisely what is written as the internal direct sum of vector spaces in linear algebra Example 2611 Recall that we know if gcd mn 17 then Zm 69 Zn 2 Zmn e may realize this as an internal direct some as well In this case take H I S Zmn and K I S Zmn Notice that ifz E H K7 then I an bm for some a7 12 E N and therefore nlbm and so by Euclidls lemma7 nlb Therefore I Enm 0 E Zmn This shows Page 80 job algebra that H N K 0 7 or see Problem 454 Moreover since gcd mn 17 it follows that there exists ab 6 Z such that am In 1 Therefore if h E Zmn then It ham him 6 Therefore H K Zmn and therefore H X K Zmn To complete the circle observe that m and n so that HltngtEZm andKltmgt EZn Thus we have shown7 ameaangHeaKngKZm macro svmonob cls datetime 13Mar20099O4 27 Lecture 27 3112009 We may generalize Proposition 267 as follows Theorem 271 Suppose that H and K are subgroups of G such that his hh for all h E H and h E K Then HK is a subgroup ofG go I HEBK A HK de ned by go h h 2 his is a homomorphism with mzkergo 1171 1 EH K Therefore HK g H e Km and H N K 3 z A 1171 6 H 271 is an isomorphism of groups Proof Most of this proof is straightforward The main thing to notice is that H N K is an abelian group since if Ly E H N K then I E H and y E K and therefore my yr by assumption With this fact in hand it is easy to check that the map in Eq 271 de nes an isomorphism l Corollary 272 IfH and K are nite subgroups of G such that his hh for allhE H andh E K then lHl 39 lKl HK7 H K Proof Using Theorem 271 Lagrangels theorem and the fact that isomor phisms preserve orders we nd Heam Heam H m bibKl lH Kl lH Kl HKl H69 KW Remark 273 Corollary 272 turns out to be true in full generality To prove this let f H X K A HK be the function not in general a homomorphism and in fact HK need not be a subgroup de ned by f h h hk for all h h e H X K Making use of Eq 262 form the proof of Lemma 261 we have lHllKlleKl Z lf 1gl 272 gEHK We now must work out f 1 g where g hoho for some he 6 H and he 6 K From our de nition of f it follows that h h E f 1 hoho iff hh hoho which happens iff hglh hoh l z E H N K Therefore we have shown f 1h0h0 hozwilho z E H N K As all the elements in the above list are distinct it follows that lfil h0h0l lH Kl Using this back in Eq 272 gives the desired result HKHgtltK Z HmKHKHHan 51er 271 The Structure of Finite Abelian Groups Theorem 274 The Fundamental Theorem of Finite Abelian Groups Every nite abelian group is isomorphic to a direct sum of cyclic groups The full proof of this theorem and more may be found in chapter 11 of the book We will give some parts of the proof later with the full details being left to you to read in the book if you are so interested Let us work out a couple of simple examples Example 275 Let us now consider U 9 1245 7 8 Again we compute the cyclic subgroups 2 124875 U9 EZgwhere63273 ltgt 7 7 82 27 Lecture 27 3112009 Example 276 Let us consider U16 135791113151 We begin by looking for cyclic subgroups lt3 13911 lt5gt 15913 lt7gt 177 lt15gt 115 Notice that lt3 9 lt7 1 and therefore 2 4 8 and hence it follows that U 16 lt3 gtlt lt7 2 Z4 69 Zgi Note we have use the fact that ifH K e as HXK 3 h h 7gt hh E HK is a bijection in this case Fact 277 Carl Gauss proved in 1801 that U 17 E anipna ifp is an odd prime and U 2 E 1 U4 13 2 Z2 while U 2 E Z2 69 Z2n72 for n 2 3 The only cyclic U 7 groups are the ones appearing in rst two rows of the above list 7 U is not cyclic for all other nl Recall from Exercise 456 that it was shown that U 2 has two distinct elements of order 2 and therefore we already know that U 2 is not cyclic for n 2 3 Example 278 If mn E Z are relatively prime then U Um gtlt Un iiel U is the internal direct product of Um and Un To check this recall that go U 7gt U 69 U de ned by go 1 mod n zmodm is an isomorphisml Therefore making use of Remark 269 U m 90 11 B U m x 90 1Un691 2713 Lastly observe that goz E 1 69 Um iff zmodn 1 ie iff z 6 Un Therefore 9471 1 EB U m Un m 274 Page 82 job algebra and similarly 9471 U n ea 1 Um n 275 Combining Eqsl 273 7 275 shows that U Um gtlt Un Alternatively Here is a more direct checkl First off all subgroups of the abelian group U are normall By Lemma 225 we know that Um 9 U7 Lastly if z E U we may use Proposition 226 to nd a E Um and b 6 Un such that zmodn amodn and zmodm bmodml It then follows that zb la 1modn 1 and zb la 1modm 1 ie Ibilail E Um 9 Un Therefore I ab which proves U Um Un i 272 Public Key Encryption Let us brie y explain the algorithm for sending public key77 encrypted mes sages For the input to this scheme the receiver of the message prepares 1 two large distinct primes p and q p and L can be found easily 2 Let n 2 pg 7 it is hard to factor Observe that U U p 69 U 4 Z1771 69 ZqLL 276 3 Compute m I lcm p 714 71 Note that m is the maximal possible order of any element in U because of Eq 216 4 Choose any r E U other than 1 for example r m 7 1 would work 5 Tell the sender publicly to encrypt herhis message ME12lHminpq71 277 by M enman MT modn Ri The restriction in Ed 27 ensures that gcd M n gcd M pq 1 ie M E U l 6 The sender now sends hisher encrypted message Ri Decoding the message To decode the message R the receiver performs 1 Compute s I r 1 E U i This can be done by the division algorithm for nding st E Z such that sr tm 1l macro svmonob cls datetime 13Mar20099O4 2 Then heshe computes RsrnodnM rnodnM modmrnodnMrnodnM 278 wherein we have used as we have seen above that lm so that Mm 1 in U i In this way the receiver has recovered the original message7 Mi See the text book for an explicit example of the procedure in action 28 Lecture 28 3132009 281 Permutation Group Remarks 1 2 3 4 5 Eromyle 281 Canjugatwn Consider 47 1 2 3 andT 14 25 3o then 5 w 3 1171 1 14 25 36 123 36 25 14 9 1o 11 17 111 19 25 26 27 33 34 35 12 111 13 20 f1 1 21 28 39 1 29 36 37 1 2 3 4 5J5 4 5J5 71 JO r18 v M 5 5 22 3 24 30 quot5quot 32 35 quot3quot 4 The following useful lernrna gives the general result suggested by th1s examr 41 42 3 ple 44 bouuln 45 46 47 48 Lemma 282 Conjugation of Cycles Suppase that 47 a1 Navy 15 a cycle m SL an 1 e SL 25 any ytlm parmutatwn Then Fig 281 Rubik s cube layed out 7 to ta1 am 281 at m ntmcaltr canjugatwn 17f a m e cycle by some t e S 15 tyam to m e WP lt1gt3rsr5gtlt2r5r7r4gtltgr33gt25r1000343518gtlt1lr35r27119gt cycle an left 9111131410131512117414042044376224635 7a1 amr1 7a1 117amv front 17 192422182123206254316728421383041 11 Proof Conjugation by 1 has the e ect of relabehng l2n to 3M4 27gt 3230x25129131gt28X3gt38gt43gt19gt5135145gt218gt33gt481 24 171 ra Formally observe that 11739 e oi aw then rear 33354038x614373936gtlt394632gt2a12a47a29gt1144827gt bottorn 41 43 48464245474414 22 30 3815 23 31 3916 24 3240 1W7 WUW 70 so that y 739 1s xed by 7 Moreover since 7k wkrl and a 71H ml for 1a 7 d 71424111 g 4andsgngil Notice that for all of the generators 1k 1a WkT l 1a 70ka1 1 at Using GAP We may easily compute y top 1le1t Here 1s the GAP transcript y y y gt top1135271910342618933251725741386 From these observat1ons we learn that Tori 1s gwen as 1D Eq 281 I 1386257493325171034261811352119 gapgt1eft622463542U4437117414U101315129111614 2811 Rubik1s cube ll Al A VA AA V13 41 3o11113141n1 l l gapgt top left The following moves generate the Rubik s cube group 1 413 3 10 113 14 Q 3 41 411W 3 11 44 4V13 1 11 10342618l315l2 gapgt lefttop 3 4 n44 13 413 101111314 3141411 86 28 Lecture 28 3132009 10131512342618 So 9 top 96 left 1 9 35 2 5 7 4 20 44 37 3 8 6 22 46 2719111614 33 2517 41 40 6 10131512 34 2618 Notice that the lengths of the cycles in g are 3 7 15 and 7 and hence sgng 1 and 191 lcm 37157 105 282 More Abelian Group Theorem Theorem 283 Cauchy s Theorem for Abelian Groups Let G be a nite abeliah gToup and p be a piime divisoT 0f 16quot Then G has an element of UTdeT p Proof There is nothing to prove if G e Based on this trivial case we may now proceed by induction So let G be a nontrivial nite group and suppose that statement of the theorem holds for all groups with order strictly less than 1G1 Pick an element 1 E G e and let it I Case 1 If pln then 9 I I 1 has order p and we are done Case 2 Suppose now that p does not divide it and let H I and G I GH If h 2 lg then 1G1 h h it As pl 1G1 but not it it follows that plh lGl lt So by the induction hypothesis there is an element 9H 6 G I GH such that lng p Thus it follows that ng gHp eH while 9TH eH for 1 S T lt p which may be stated equivalently as gT Hfor1 Tltpwhilehgp6H 282 Let h I 9quot E H and d I lhl lgpl We will complete the proof by showing u I 9 1 has order p First off up gd39p gp39d hd e and therefore 1p Because p is prime to nish the proof we need only show f 1 ie u f e We are going to do this by showing u 9 1 H Since h 9quot E H we know that d lhl 1 it Since pt n we must also have pt d and therefore we may write d hp T with 1 S T lt p and h E N Therefore 9 1 916174 hkgT which is not in H since if it were it would violate Eq 282 I Page 86 job algebra For motivation for our next lemma suppose that H and K are groups such that m I and n I are relatively prime 1 claim that Hehh EHGBK hhmeee H0 Indeed by Lagrange7s theorem h em hme ee for all h E H which shows that H 69 e C H0 Conversely if h h 6 H0 then e e h Mm e km and therefore hm e Hence it follows that W must divide m Again by La grange s theorem we know that W also divides it Since gcd Tn n 1 it follows that W 1 and therefore h e Thus h h 6 H0 iff h e Lemma 284 Suppose that G is a nite abelizm gToup such that 1G1 mn wheTe m and n aTe Telatively piime Let HZIEGZIm athz Gzzne Then G is the inteTmzl diTect sum ofH and K m and n Proof Since gcd Tn n 1 there exists st E Z such that 1 s m tn So if z E G we have I zmzsm hh where h I It and h I 1 Since hm rpm et e and h 15 quotm e5 e it follows that h E H and h E K This shows that G HK Moreover if z E H K then we know rm e I and therefore divides both m and it Again as gcd mn 1 it follows that 1 ie z e Thus we have shown H N K e and this proves the assertion that G H X K We now know that m n 1G1 Suppose that p is a prime which divides By Cauchyls Theorem 283 there exists h E H such that lhl p As h E H we also know that hm e and therefore p lhl divides m As m and n are relatively prime p does not divide it nor as the same argument would show pln Therefore if pi p and 4111 1 H 41 are the prime factorizations of and then p1 pl are disjoint 41 qr and a a b bT mnp11pl qllqT where pi i n and qj tm for all i and j From this it follows that lHlp 111p mand lKlqll 1qlT Tn macro svmonobcls datetime 13Mar20099O4

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.