MATH 241 Homework 3, Fall 2011

Math 241 Problem Set 3 solution manual Exercise. A3.1 Let a, b ∈ Z+. a- aZ, and bZ are both subgroups of Z, so by previous ex (section 5, ex: 54) we have that their intersection is a subgroup of Z. Consider the element a.b ̸= 0, a.b ∈ aZ, and a.b ∈ aZ, so a.b ∈ aZ ∩ bZ. So we have aZ ∩ bZ is a non-empty subgroup of Z b- we have aZ ∩ bZ = mZ, we are required to show that m=LCM(a, b). m ∈ aZ then m is a multiple of a, similarly it is a multiple of b. So m is a common multiple of a and b. Now let n¿0 be such that n is a common multiple of a and b. Then n ∈ aZ and n ∈ bZ , =⇒ n ∈ aZ ∩ bZ = mZ =⇒ n < m ( since both are positive and m is smallest positive integer in mZ). So m is the smallest common multiple of a and b. c- Let c be a common multiple of a and b, then c ∈ aZ, and c ∈ bZ =⇒ c ∈ mZ =⇒ c is a multiple of m. d- d = GCD(a, b) . a ′d = a and b ′d = b. GCD(a ′, b ′)=1 =⇒ ∃ k1, K2 ∈ Z such that a ′k1 + b ′k2 = 1. Now multiply both side by m = LCM(a, b), we get: ma ′k1 + mb ′k2 = m (⋆). Now notice that since m is the LCM of a, and b then m = ac1, and m = bc2 then replace them in (⋆) we get : m = c2ba ′k1 + c1ab ′k2. But ba ′ − db ′a ′ = ab ′. so we get : m = da ′b ′c2k1 + da ′b ′c1k2 = da ′b ′(c1k2 + c2k1). implies m is a multiple da ′b ′. On the other hand da ′b ′ = ab ′, so da ′b ′ is a multiple of a , similarly da ′b ′ is a multiple of b, then by part (c) we get that da ′b ′ is a multiple of m. But two positive number are multiples of each other only if they are equal, so we get m = da ′b ′. Finally : multiply by d on both sides of the relation m = da ′b ′ we get md = a.b, =⇒ m = ab d =⇒ LCM(a, b)= ab GCD(a,b). Section. 6 Exercise. 53 G is cyclic =⇒ G is generated by one element (i.e G =< g > for some g ∈ G). 1 Let x ∈ G , be such that xm = e , then since x ∈ G we can write x = gi for some i ∈ {0, 1, .., n − 1}. Then we have (gi)m = e =⇒ gim = e, but since g is the generator of G and is of order n, then n is the smallest power of g such that g raised to this power is e, and any other power k such that gk = e should be a multiple of n. And from this we deduce that im is a multiple of n, so im = kn for some k ∈ Z =⇒ i = kn m (note that this fraction is still in Z since m divides n). Finally the set of solutions of xm = e is {gi | i = kn m , k ∈ Z}={g kn m | k ∈ {0, 1, 2..(m − 1)}}. Since for i = kn m with k > m, we can write k = b.m + r with b ∈ Z and 0 ≤ r < m, then kn m = (b.m+r)n m = b.n + rn m , and then gi = g r.n m which belong to the set described above. So the number of solutions of the equation xm = e is m. Exercise. 56 a- Let H =< h > and K =< k > be two cyclic subgroups of G generated by h of order r, and k of order s respectively. Note that since G is commutative (ab)n = (ab)(ab)...(ab) = (a.....a)(b.....b) = anbn. We need to find a subgroup of G of order rs. Consider the subgroup L generated by the element hk (i.e L =< hk >). L is a cyclic subgroup of G of order equal the order of the element hk. We know that (hk)rs = hrskrs = (hr)s(ks)r = e, in order to have order of hk equal rs we must prove that rs is the smallest positive integer i such that (hk)i = e. Let n be such that (hk)n = e, we will show that n ≥ rs. (hk)n = hnkn = e =⇒ hn = k−n =⇒ hn ∈< k > , and hn = ks−n. Let j be the order of hn, since hn ∈< k >, j is equal to s GCD((s−n),s) =⇒ j divides s, similarly j divides r =⇒ j = 1, since r and s are relatively prime. So hn = e =⇒ n is a multiple of r. In a similar way we can prove that n is a multiple of s. Finally since r and s are relatively prime, there LCM is rs (by A3.1) and then n ∈ rsZ, =⇒ n ≥ rs. So the order of hk is rs. b- Now we have the same elements given above but this time r and s are not relatively prime. Factorize r and s into powers of primes. That is write r = pe1 1 ....pet t and s = pf1 1 ....pft t where the ei, fi are ≥ 0. Then the lcm(r, s) = Πpci i where ci = max(ei, fi). Then we choose the following elements according to the following:      if ci = ei let ai = x ( Π j̸=ip ej j ) . if ci = fi let ai = y ( Π j̸=ip fj j ) . 2 Note that the order of each ai is pci i Then the elements ai have their orders pair wise relatively prime, so repeating part a) suc- cessively we get that Πai is of order Πpci i = lcm(r, s). For example : Suppose r = 23325 = 233251110, s = 223711 = 223750111, so lcm(r, s) = 233751111. Then since x has order r, we define x′ = x(325) which has order 23 y′ = y(2211) which has order 37 x′′ = x(2332) which has order 5 y′′ = y(2237) which has order 11. Note that we have separated the powers of the primes 2, 3, 5, 11 that occur. These powers are pair wise relatively prime. Now by repeated application of part a, we obtain that x′y′x′′y′′ has order 2337511 = lcm(r, s). Section. 8 Exercise. 1 τσ= � 1 2 3 4 5 6 2 4 1 3 6 5 � Exercise. 4 σ−1τ= � 1 2 3 4 5 6 5 1 6 2 4 3 � Exercise. 5 σ−1τσ= � 1 2 3 4 5 6 2 6 1 5 4 3 � τ=(1243)(56). σ−1τ−1=(1263)(45). Exercise. 6 σ=(134562), =⇒ σ is a cycle of order 6, then the order of σ is 6. Exercise. 7 τ=(14)(23), so τ is the product of two disjoint transpositions, so the order τ is 2. 3 Exercise. 8 σ100 = (σ6)16.σ4 = σ4 = � 1 2 3 4 5 6 6 5 2 1 3 4 � Exercise. 16 {σ ∈ S4 | σ(3) = 3}. Note that this set contains all the permutations of {1,2,3,4} which keep the element 3 untouched, so it is like we are permuting the three elements 1,2,4. Then the number of elements of this set is 3!=6. Exercise. 21 a- Applying the matrices to the vector   1 2 3   we get all the possible permutations of the columns of this vector. Moreover, the product of two matrices is the compositions of two permutation of the columns of the vector which is again a permutation. Then this set of matrices form a group under matrix multiplication, where the identity element is I3. b- This group of matrices is isomorphic to S3 since it is permuting the 3 columns of a vector, similar to S3 which permutes the three elements of a set. So one can simply find an isomorphism between them. Exercise. 46 Consider σ1 and σ2 ∈ Sn, since n ≥ 3 we can consider three distinct elements denote them by 1,2,3. Now let σ1=(123), and σ2 = (13). Then σ1σ2(1) = 1 , but σ2σ1(1) = 2 , so they don’t commute =⇒ Sn is not abelian Section. 9 Exercise. 7 � 1 2 3 4 5 6 7 8 4 1 3 5 8 6 2 7 � Exercise. 13 a- σ=(1 4 5 7), we can easily notice that σ4=id , then the order of σ=4. b- The order of a cycle of length m is m. c- σ=(4 5)(2 3 7) , then σ6=id , so the order of σ=4. τ=(1 4)(3 5 7 8), then τ 8=id , so the order of τ=8. 4 d- for exercise 10: the order is 6, for exercise 11 order is 6, and for exercise 12 order is 8. e- Any permutation expressed as the product of disjoint cycles has its order the lcm of the length of those cycles. Exercise. 39 Lemma 1. Let (a1a2...am) with m ≤ n be a cycle, and let f be any permutation in Sn. Then fr(a1a2...am)f−r = (fr(a1)fr(a2)...fr(am)). Proof: We prove it by induction on r: basic step: for r=1: σ1 = f(a1a2...am)f−1, and σ2 = (f(a1)f(a2)...f(am)) let x be any number between 1 and n , we have 2 cases: there exist ai such that x = f(ai) then we get σ1(x) = σ1(f(ai)) = f(ai+1), and σ2(f(ai)) = f(ai+1), so they are equal. Or there exist no ai such that x = f(ai) then f−1(x) /∈ {ai | i = 1, ..., m} , so we get σ1(x) = x, and σ2(x) = x. Hence σ1 and σ2 are equal for all x ∈ {1, ..., n}. Inductive step: Suppose it is true up to r − 1, and let us prove it for r . σ1 = fr(a1a2...am)f−r, and σ2 = (fr(a1)fr(a2)...fr(am)). Then σ1 = fr(a1a2...am)f−r = f.fr−1(a1a2...am)f−(r−1)f−1 = f(fr−1(a1)fr−1(a2)...fr−1(am))f−1 = (fr(a1)fr(a2)...fr(am)) = σ2 , where in the last step we use the same argument as for the base step but for the cycle (fr−1(a1)fr−1(a2)...fr−1(am)). then we now have : fr(a1a2...am)f−r = (fr(a1)fr(a2)...fr(am)) Lemma 2. The transposition (i j)=(i k)(j k)(i k) for any k not equal to i and j, and hence we can deduce that any transposition can be written as the product of adjacent transpositions. Proof: easily one can check (ij) = (ik)(jk)(ik), and now to deduce the second part of the lemma we can do it by induction on the difference between i, and j in (ij): Base step: if |i − j| = 1, we are done since (ij) will be an adajcent transposition. Inductive step step: suppose it is true for |i − j| = k − 1 (k < n), let us prove it for |i − j| = k Without loss of generality we can assume i > j, then write (i j)=(i i + 1)(j i + 1)(i i + 1), now by given of induction we can write (j i + 1) as the product of adjacent transpositions ( since |j − i + 1| = k − 1) , so (ij) can be written as the product of adjacent transpositions. Now the exercise : 5 From lemma 1 , we can easily deduce that (12...n)r(12)(12...n)n−r will generate all adjacent transpositions. ( Notice that (12...n)n−r = (12...n)−r since (12...n) is of order n) Then from lemma 2 and from the fact that any permutation can be written as the product of transpositions, then any permutation can be expressed as the product of the two elements given by the exercise. 6