Mathematics 243, section 3 – Algebraic Structures Problem Set 9 due: Friday, November 30

‘A’ Section

1. For each of the following values of n,

• Find all distinct generators of the group (ℤ_{n}, +),

• Find all subgroups of (ℤ_{n}, +) and their orders

• Find all elements of (ℤ_{n}^{×}, ·) and their orders (for the multiplication operation mod n now)

n = 13, 16, 30

(Use the “big theorem” on cyclic groups for as much of this as possible. It is not necessary to do a lot of computations in most cases.)

Solution: For n = 13, by the “big theorem” we know that the generators of ℤ_{13} are the [a] such that gcd(a, 13) = 1, which are [1], [2], [3], [4], …, [12]. The only subgroups are {[0]} and ℤ_{13} itself.

For the multiplication operation, ℤ_{13}^{×} = {[1], [2], …, [13]}, and now taking powers [2]^{k} we get:

⟨[2]⟩ = {[1], [2], [4], [8], [3], [6], [12], [11], [9], [5], [10], [7]} = ℤ_{13}^{×}

This shows ℤ_{13}^{×} is cyclic of order 12 with generator [2]. That says that [1] generates the trivial subgroup consisting of just the identity. The elements [2]^{5} = [6], [2]^{7} = [11], [2]^{11} are the other generators of ℤ_{13}^{×} and have multiplicative order 12. Then [2]^{2} = [4] and [2]^{10} = [10] generate the cyclic subgroup of order 6, so have multiplicative order 6. Also, [2]^{3} = [8] and [2]^{9} = [5] generate the cyclic subgroup of order 4, so have multiplicative order 4, Next, [2]^{4} = [3] and [2]^{8} generate a cyclic subgroup of order 3 and have multiplicative order 3. Finally, [2]^{6} = [12] generates a cyclic subgroup of order 2 and has multiplicative order 2.

n = 16: By the “big theorem” we know that the generators of the cyclic group (ℤ_{16}, +) are the [a] such that gcd(a, 16) = 1, which are [1], [3], [5], [7], [9], [11], [13], [15]. The additive subgroups of ℤ_{16} are

{[0]} = ⟨[0]⟩
ℤ_{16} = ⟨[1]⟩ = ⟨[3]⟩ = ⋯ = ⟨[15]⟩
{[0], [2], [4], [6], [8], [10], [12], [14]} = ⟨[2]⟩ = ⟨[6]⟩ = ⟨[10]⟩ = ⟨[14]⟩
{[0], [4], [8], [12]} = ⟨[4]⟩ = ⟨[12]⟩
{[0], [8]} = ⟨[8]⟩.

The number of generators in each case is given by the Euler function from Problem Set 7: There are φ(o([a])) different generators of the group if the order is o([a]).

For the multiplication operation, ℤ_{16}^{×} = {[1], [3], [5], [7], [9], [11], [13], [15]}. We have the following (finding the smallest positive powers giving the multiplicative identity [1]):

o([1]) = 1
o([3]) = 4 since [3]^{4} = [81] = [1]
o([5]) = 4 since [5]^{4} = [625] = [1]
o([7]) = 2 since [7]^{2} = [49] = [1]
o([9]) = 2 since [9]^{2} = [81] = [1]
o([11]) = 4 since [11]^{4} = [1]
o([13]) = 4 since [13]^{4} = [1]
o([15]) = 2 since [15]^{2} = [1].

(Note that this shows ℤ_{16}^{×} is not a cyclic group under multiplication.)

n = 30: By the “big theorem” we know that the generators of the cyclic group (ℤ_{30}, +) are the [a] such that gcd(a, 30) = 1, which are [1], [7], [11], [13], [17], [19], [23], [29]. The additive subgroups of ℤ_{30} are

{0} = ⟨[0]⟩
ℤ_{30} = ⟨[1]⟩ = ⟨[7]⟩ = ⋯ = ⟨[29]⟩
{[0], [2], [4], …, [28]} = ⟨[2]⟩ = ⟨[4]⟩ = ⟨[8]⟩ = ⟨[14]⟩ = ⟨[16]⟩
= ⟨[22]⟩ = ⟨[26]⟩ = ⟨[28]⟩
{[0], [3], [6], …, [27]} = ⟨[3]⟩ = ⟨[9]⟩ = ⟨[21]⟩ = ⟨[27]⟩
{[0], [5], [10], [15], [20], [25]} = ⟨[5]⟩ = ⟨[25]⟩
{[0], [6], [12], [18], [24]} = ⟨[6]⟩ = ⟨[12]⟩ = ⟨[18]⟩ = ⟨[24]⟩
{[0], [10], [20]} = ⟨[10]⟩ = ⟨[20]⟩
{[0], [15]} = ⟨[15]⟩.

Again, number of generators in each case is given by the Euler function from Problem Set 7: φ(o([a])) .

For the multiplication operation, ℤ_{30}^{×} = {[1], [7], [11], [13], [17], [19], [23], [29]}. We find that

o([1]) = 1
o([7]) = 4 since [7]^{4} = [1]
o([11]) = 2 since [11]^{2} = [1]
o([13]) = 4 since [13]^{4} = [1]
o([17]) = 4 since [17]^{4} = [1]
o([19]) = 2 since [19]^{2} = [1]
o([23]) = 4 since [23]^{4} = [1]
o([29]) = 2 since [29]^{2} = [1].

(Note that this shows ℤ_{16}^{×} is not a cyclic group under multiplication.)

2. Let φ : ℤ_{18} → ℤ_{9} be defined by φ([x]) = [3x].

(a) Verify that φ is a group homomorphism. Solution: φ is a group homomorphism since for all [x] and [y] in ℤ_{18},

φ([x] + [y]) = φ([x + y]) = [3(x + y)] = [3x] + [3y] = φ([x]) + φ([y]).

(b) Determine the kernel of φ. Solution: The kernel of φ is

φ^{−1}({[0]}) = {[0], [3], [6], [9], [12], [15]} = ⟨[3]⟩ ⊂ ℤ_{18}

(c) Determine the image of φ. Solution: The image of φ is

φ(ℤ_{18}) = {[0], [3], [6]} = ⟨[3]⟩ ⊂ ℤ_{9}

‘B’ Section

1. Let G be a group and consider the mapping φ : G → G defined by φ(x) = x^{−1}. Show that φ is always one-to-one and onto, but that φ is an isomorphism of groups if and only if G is an abelian group.

Solution: The map φ is one-to-one since φ(x) = φ(y) implies x^{−1} = y^{−1}, and taking inverses of both sides we get x = y. The map φ is onto because given any x ∈ G, x = (x^{−1})^{−1} = φ(x^{−1}). This is a group isomorphism if and only if

(x ∗ y)^{−1} = φ(x ∗ y) = φ(x) ∗ φ(y) = x^{−1} ∗ y^{−1} = (y ∗ x)^{−1}.

where the last equality follows from the reverse order law. Since φ is one-to-one, this is equivalent to saying that x ∗ y = y ∗ x for all x, y ∈ G and hence G is abelian. Hence φ is an isomorphism of groups if and only if G is an abelian group.

2. An automorphism of a group G is an isomorphism of groups φ : G → G (that is, the domain and the range are both the same group G).

(a) Let A = {a, b, c} and G = S(A) be the group of permutations of A. Show that φ : G → G defined by φ(f) = R_{a} ∘ f ∘ R_{a} is an automorphism of G. Solution: φ is a one-to-one mapping from G to itself since if φ(f) = φ(g), then R_{a} ∘ f ∘ R_{a} = R_{a} ∘ g ∘ R_{a}. Composing with R_{a} again on the left and right on both sides, since R_{a} ∘ R_{a} = I_{A}, we get f = g. Since S(A) is a finite set and φ is one-to-one, it is also onto. Finally, φ is an isomorphism of groups since

φ(f ∘ g) = R_{a} ∘ f ∘ g ∘ R_{a}
= R_{a} ∘ f ∘ R_{a} ∘ R_{a} ∘ g ∘ R_{a} since R_{a} ∘ R_{a} = I_{A}
= (R_{a} ∘ f ∘ R_{a}) ∘ (R_{a} ∘ g ∘ R_{a}) (associativity of composition)
= φ(f) ∘ φ(g).

(b) Show that the collection of all automorphisms of a general group G is itself a group under the operation of function composition. Solution: We must show that the four axioms (properties) in the definition of a group are satisfied.

• First, if φ, ψ are automorphisms of G, then φ∘ψ is one-to-one and onto by theorems from Chapter 1. The composition is also an isomorphism of groups since

(φ ∘ ψ)(x ∗ y) = φ(ψ(x ∗ y))

= φ(ψ(x) ∗ ψ(y)) since ψ is a homomorphism = φ(ψ(x)) ∗ φ(ψ(y)) since φ is a homomorphism = (φ ∘ ψ)(x) ∗ (φ ∘ ψ)(y).

Thus the set of automorphisms is closed under composition.

• Function composition is always associative, so there is nothing more to prove for that property in the definition of a group.

• The identity map I_{G}, defined by I_{G}(x) = x for all x ∈ G, is one-to-one and onto

and satisfies

I_{G}(x ∗ y) = x ∗ y = I_{G}(x) ∗ I_{G}(y).

Hence it is an isomorphism from G to itself, and it is the identity under composition, since φ ∘ I_{G} = φ = I_{G} ∘ φ for any automorphism φ of G.

• Finally, if φ is an isomorphism, then the inverse mapping φ^{−1} exists as a mapping from G to itself and is also one-to-one and onto. We want to show that φ^{−1} also has the homomorphism property. So let x, y ∈ G. Since φ is onto, we know x = φ(a) and y = φ(b) for some unique a, b ∈ G. Therefore since φ is a homomorphism, we have φ(a ∗ b) = x ∗ y. But this also says φ^{−1}(x) ∗ φ^{−1}(y) = a ∗ b = φ^{−1}(x ∗ y). Hence φ^{−1} is also a group homomorphism.

(c) Show if G is a general group and g ∈ G, then the conjugation mapping defined by φ_{g}(x) = gxg^{−1} is an automorphism of G. (Note that the example in part (a) has this form.)

Solution: φ_{g} is one-to-one since if φ_{g}(x) = φ_{g}(y), then gxg^{−1} = gyg^{−1}. But that implies g^{−1}gxg^{−1}g = g^{−1}gyg^{−1}g, so x = y. Next, φ_{g} is onto since given y ∈ G, y = φ_{g}(g^{−1}yg) = gg^{−1}ygg^{−1}. Finally, φ_{g} is a group homomorphism since for all x, y ∈ G, as in part (a) above

φ_{g}(xy) = gxyg^{−1}
= gx(g^{−1}g)yg^{−1}, since g^{−1}g = e
= (gxg^{−1})(gyg^{−1}) by associativity
= φ_{g}(x)φ_{g}(y).

(d) Show that the collection of φ_{g} for all g ∈ G (as in part (c)) is a subgroup of the group of automorphisms of G.

Solution: We will use the “shortcut method” from Theorem 3.10. First, this collection of automorphisms is certainly nonempty since we have one of them for each g ∈ G. (They might not be distinct, of course.) Let φ_{g} and φ_{h} be any two such automorphisms. Note that φ_{h}^{−1} is the mapping φ_{h^{−1}} since

y = φ_{h}(x) = hxh^{−1} ⇔ x = h^{−1}yh = φ_{h^{−1}}(y).

Then φ_{g} ∘ φ_{h}^{−1} is the mapping defined by

(φ_{g} ∘ φ_{h}^{−1})(x) = gh^{−1}xhg^{−1} = (gh^{−1})x(gh^{−1})^{−1} = φ_{gh^{−1}}(x).

This is the automorphism φ_{k} for k = gh^{−1} ∈ G. Hence this collection of automorphisms is a subgroup of the group of all automorphisms.

3. We can consider isomorphism of groups as a relation on the collection of all groups: GRH ⇔ there exists an isomorphism φ : G → H. Show that isomorphism of groups is an equivalence relation on the collection of all groups.

Solution: Every group is isomorphic to itself via the identity mapping I_{G} : G → G with I_{G}(g) = g for all g ∈ G. This is clearly one-to-one, onto, and a group homomorphism. Thus the isomorphism relation is reflexive. Next, if G is isomorphic to H via φ : G → H, then since φ is one-to-one and onto, we have the inverse mapping φ^{−1} : H → G. We want to show that φ^{−1} also has the homomorphism property. So let x, y ∈ H, Since φ is onto, we know x = φ(a) and y = φ(b) for some a, b ∈ G. Therefore since φ is a homomorphism, we have φ(a ∗ b) = x ∗ y. But this also says φ^{−1}(x) ∗ φ^{−1}(y) = a ∗ b = φ^{−1}(x ∗ y). Hence φ^{−1} is also a group homomorphism from H to G. Thus φ^{−1} is also an isomorphism of groups. Hence H is isomorphic to G and the isomorphism relation is symmetric. Finally, say G is isomorphic to H via φ : G → H and H is isomorphic to K via ψ : H → K. Consider ψ ∘ φ : G → K.

We know from general results from Chapter 1 that ψ ∘ φ is one-to-one and onto. Moreover, for all x, y ∈ G,

(φ ∘ ψ)(x ∗_{G} y) = φ(ψ(x ∗_{G} y))
= φ(ψ(x) ∗_{H} ψ(y)) since ψ is a homomorphism
= φ(ψ(x)) ∗_{K} φ(ψ(y)) since φ is a homomorphism
= (φ ∘ ψ)(x) ∗_{K} (φ ∘ ψ)(y).

Thus φ ∘ ψ is also an isomorphism from G to K. This shows the isomorphism relation is transitive.

Comment: You should note that the ideas here are the same as those in the proof of part (b) of question 2 above(!)

4. Let G = ⟨a⟩ be a cyclic group and let φ : G → H be a group homomorphism. Show that if we know the one element φ(a), then we know where φ maps every element of G.

Solution: If G = ⟨a⟩ is a cyclic group, then every element of the group G is a^{n} for n ∈ ℤ. If n = 0, then a^{0} = e_{G} and φ(e_{G}) = e_{H}. If n > 0, then we argue by induction that φ(a^{n}) = (φ(a))^{n} (so knowing φ(a) determines all of those elements too). The base case for the induction is n = 1, and there is nothing to prove there. Assume we know φ(a^{k}) = (φ(a))^{k}. Then

φ(a^{k+1}) = φ(a^{k} ∗ a) by definition of the power

= φ(a^{k}) ∗ φ(a) by the homomorphism property

= (φ(a))^{k} ∗ φ(a) by the induction hypothesis

= (φ(a))^{k+1} by the definition of the power.

This shows φ(a^{n}) = (φ(a))^{n} for all n ≥ 1. A similar induction also shows φ(a^{n}) = (φ(a))^{n} for all n ≤ −1. The base case there is the fact we proved in general before: φ(a^{−1}) = (φ(a))^{−1}.