sentences, we will say coset when we mean “right coset.

”
When we deal with cosets in a group G, we must keep in mind that every coset in G is a subset of G.
Thus, when we need to prove that two cosets Ha and Hb are equal, we must show that they are equal sets.
What this means, of course, is that every element x ∈ Ha is in Hb, and conversely, every element y ∈ Hb
is in Ha. For example, let us prove the following elementary fact:

If a ∈ Hb, then Ha = Hb (1)

We are given that a ∈ Hb, which means that a = h1b for some h1 ∈ H. We need to prove that Ha = Hb.
Let x ∈ Ha; this means that x = h2a for some h2 ∈ H. But a = h1b, so x = h2a = (h2h1)b, and the latter
is clearly in Hb. This proves that every x ∈ Ha is in Hb; analogously, we may show that every y∈ Hb is
in Ha, and therefore Ha = Hb.
The first major fact about cosets now follows. Let G be a group and let H be a fixed subgroup of G:

Theorem 1 The family of all the cosets Ha, as a ranges over G, is a partition of G.

PROOF: First, we must show that any two cosets, say Ha and Hb, are either disjoint or equal. If they
are disjoint, we are done. If not, let x ∈ Ha ∩ Hb. Because x ∈ Ha, x = hxa for some h1 ∈ H. Because x
∈ Hb, x = h2b for some h2 ∈ H. Thus, h1a = h2b, and solving for a, we have

Thus,

a ∈ Hb

It follows from Property (1) above that Ha = Hb.

Next, we must show that every element c ∈ G is in one of the cosets of H. But this is obvious,
because c = ec and e ∈ H; therefore,

c = ec ∈ Hc

Thus, the family of all the cosets of H is a partition of G. ■

Before going on, it is worth making a small comment: A given coset, say Hb, may be written in more
than one way. By Property (1) if a is any element in Hb, then Hb is the same as Ha. Thus, for example, if
a coset of H contains n different elements a1, a2, …, an, it may be written in n different ways, namely,
Ha1, Ha2, …, Han.
The next important fact about cosets concerns finite groups. Let G be a finite group, and H a
subgroup of G. We will show that all the cosets of H have the same number of elements! This fact is a
consequence of the next theorem.
 Theorem 2 If Ha is any coset of H, there is a one-to-one correspondence from H to Ha.
PROOF: The most obvious function from H to Ha is the one which, for each h ∈ H, matches h with
ha. Thus, let f: H → Ha be defined by

f(h) = ha

Remember that a remains fixed whereas h varies, and check that f is injective and surjective.
f is injective: Indeed, if f(h1) = f(h2), then h1a = h2a, and therefore h1 = h2.
f is surjective, because every element of Ha is of the form ha for some h ∈ H, and ha = f(h).
Thus, f is a one-to-one correspondence from H to Ha, as claimed. ■
By Theorem 2, any coset Ha has the same number of elements as H, and therefore all the cosets have
the same number of elements!

Let us take a careful look at what we have proved in Theorems 1 and 2. Let G be a finite group and
H any subgroup of G. G has been partitioned into cosets of H, and all the cosets of H have the same
number of elements (which is the same as the number of elements in H). Thus, the number of elements in
G is equal to the number of elements in H, multiplied by the number of distinct cosets of H. This
statement is known as Lagrange’s theorem. (Remember that the number of elements in a group is called the
group’s order.)

Theorem 3: Lagrange’s theorem Let G be a finite group, and H any subgroup of G. The order of
G is a multiple of the order of H.
In other words, the order of any subgroup of a group G is a divisor of the order of G.
For example, if G has 15 elements, its proper subgroups may have either 3 or 5 elements. If G has 7
elements, it has no proper subgroups, for 7 has no factors other than 1 and 7. This last example may be
generalized:
Let G be a group with a prime number p of elements. If a ∈ G where a ≠ e, then the order of a is
some integer m ≠ 1. But then the cyclic group 〈a〉 has m elements. By Lagrange’s theorem, m must be a
factor of p. But p is a prime number, and therefore m = p. It follows that 〈a〉 has p elements, and is
therefore all of G! Conclusion:

Theorem 4 If G is a group with a prime number p of elements, then G is a cyclic group.

Furthermore, any element a ≠ e in G is a generator of G.
Theorem 4, which is merely a consequence of Lagrange’s theorem, is quite remarkable in itself.
What it says is that there is (up to isomorphism) only one group of any given prime order p. For
example, the only group (up to isomorphism) of order 7 is 7, the only group of order 11 is 11, and so on!
So we now have complete information about all the groups whose order is a prime number.
By the way, if a is any element of a group G, the order of a is the same as the order of the cyclic
subgroup 〈a〉, and by Lagrange’s theorem this number is a divisor of the order of G. Thus,

Theorem 5 The order of any element of a finite group divides the order of the group.
Finally, if G is a group and H is a subgroup of G, the index of H in G is the number of cosets of H in
G. We denote it by (G:H). Since the number of elements in G is equal to the number of elements in H,
multiplied by the number of cosets of H in G,

EXERCISES

A. Examples of Cosets in Finite Groups

In each of the following, H is a subgroup of G. In parts 1–5 list the cosets of H. For each coset, list the
elements of the coset.
Example G = 4, H = {0, 2}.
(REMARK: If the operation of G is denoted by +, it is customary to write H + x for a coset, rather than
Hx.) The cosets of H in this example are

H = H + 0 = H + 2 = {0, 2} and H+ 1 = H + 3 = {1, 3}

1 G = S3, H = {ε, β, δ}.

2 G = S3, H = {ε, α}.
3 G = 15, H = 〈5〉.
4 G = D4, H ={R0, R4}.(For D4, see page 73.)
5 G = S4, H = A4.(For A4, see page 86.)
6 Indicate the order and index of each of the subgroups in parts 1 to 5.

B. Examples of Cosets in Infinite Groups

Describe the cosets of the subgroups described in parts 1–5:
1 The subgroup 〈3〉 of .
2 The subgroup of .
3 The subgroup H = {2n: n ∈ } of *.
4 The subgroup 〈 〉 of R*; the subgroup 〈 〉 of .
5 The subgroup H = {(x, y): x = y} of ( × .
6 For any positive integer m, what is the index of 〈m〉 in ?
7 Find a subgroup of * whose index is equal to 2.

C. Elementary Consequences of Lagrange’s Theorem

Let G be a finite group. Prove the following:
1 If G has order n, then xn = e for every x in G.
2 Let G have order pq, where p and q are primes. Either G is cyclic, or every element x ≠ e in G has
order p or q.
3 Let G have order 4. Either G is cyclic, or every element of G is its own inverse. Conclude that every
group of order 4 is abelian.
4 If G has an element of order p and an element of order q, where p and q are distinct primes, then the
order of G is a multiple of pq.
5 If G has an element of order k and an element of order m, then |G| is a multiple of lcm(k, m), where
lcm(k, m) is the least common multiple of k and m.
# 6 Let p be a prime number. In any finite group, the number of elements of order p is a multiple of p − 1.

D. Further Elementary Consequences of Lagrange’s Theorem

Let G be a finite group, and let H and K be subgroups of G. Prove the following:
1 Suppose H ⊆ K (therefore H is a subgroup of K). Then (G: H) = (G: K)(K: H).
2 The order of H ∩ K is a common divisor of the order of H and the order of K.
3 Let H have order m and K have order n, where m and n are relatively prime. Then H ∩ K = {e}.
4 Suppose H and K are not equal, and both have order the same prime number p. Then H ∩ K = {e}.
5 Suppose H has index p and K has index p, where p and g are distinct primes. Then the index of H ∩ K is
a multiple of pq.
# 6 If G is an abelian group of order n, and m is an integer such that m and n are relatively prime, then the
function f(x) = xm is an automorphism of G.

E. Elementary Properties of Cosets

Let G be a group, and H a subgroup of G. Let a and b denote elements of G. Prove the following:
1 Ha = Hb iff ab−1 ∈ H.
2 Ha = H iff a ∈ H.
3 If aH = Ha and bH = Hb, then (ab)H = H(ab).
# 4 If aH = Ha, then a−1H = Ha−1.
5 If (ab)H = (ac)H, then bH = cH.
6 The number of right cosets of H is equal to the number of left cosets of H.
7 If J is a subgroup of G such that J = H ∩ K, then for any a ∈ G, Ja = Ha ∩ Ka. Conclude that if H and K
are of finite index in G, then their intersection H ∩ K is also of finite index in G.
Theorem 5 of this chapter has a useful converse, which is the following:
Cauchy’s theorem If G is a finite group, and p is a prime divisor of |G|, then G has an element of
order p.
For example, a group of order 30 must have elements of orders 2, 3, and 5. Cauchy’s theorem has an
elementary proof, which may be found on page 340.
In the next few exercise sets, we will survey all possible groups whose order is ≤10. By Theorem 4
of this chapter, if G is a group with a prime number p of elements, then G ≅ p. This takes care of all
groups of orders 2, 3 5, and 7. In Exercise G6 of Chapter 15, it will be shown that if G is a group with p2
elements (where p is a prime), then G ≅ p2 or G ≅ p × p. This will take care of all groups of orders 4
and 9. The remaining cases are examined in the next three exercise sets.
† F. Survey of All Six-Element Groups
Let G be any group of order 6. By Cauchy’s theorem, G has an element a of order 2 and an element b of
order 3. By Chapter 10, Exercise E3, the elements

e, a, b, b2, ab, ab2

are all distinct; and since G has only six elements, these are all the elements in G. Thus, ba is one of the
elements e, a, b, b2, ab, or ab2.
1 Prove that ba cannot be equal to either e, a, b, or b2. Thus, ba = ab or ba = ab2.
Either of these two equations completely determines the table of G. (See the discussion at the end of
Chapter 5.)
2 If ba = ab, prove that G ≅ 6.
3 If ba = ab2, prove that G ≅ S3.
It follows that 6 and S3 are (up to isomorphism), the only possible groups of order 6.

† G. Survey of All 10-EIement Groups

Let G be any group of order 10.
1 Reason as in Exercise F to show that G = {e, a, b, b2, b3, b4, ab, ab2, ab3, ab4}, where a has order 2
and b has order 5.
2 Prove that ba cannot be equal to e, a, b, b2, b3, or b4.
3 Prove that if ba = ab, then G ≅ 10.
4 If ba = ab2, prove that ba2 = a2b4, and conclude that b = b4. This is impossible because b has order 5;
hence ba ≠ ab2. (HINT: The equation ba = ab2 tells us that we may move a factor a from the right to the
left of a factor b, but in so doing, we must square b. To prove an equation such as the preceding one, move
all factors a to the left of all factors b.)
5 If ba = ab3, prove that ba2 = a2b9 = a2b4, and conclude that b = b4. This is impossible (why?); hence ba
≠ ab3.
6 Prove that if ba = ab4, then G ≅ D5 (where D5 is the group of symmetries of the pentagon).
Thus, the only possible groups of order 10 (up to isomorphism), are 10 and D5.

† H. Survey of All Eight-Element Groups

Let G be any group of order 8. If G has an element of order 8, then G ≅ 8. Let us assume now that G has
no element of order 8; hence all the elements ≠ e in G have order 2 or 4.
1 If every x ≠ e in G has order 2, let a, b, c be three such elements. Prove that G = {e, a, b, c, ab, bc, ac,
abc}. Conclude that G ≅ 2 × 2 × 2.
In the remainder of this exercise set, assume G has an element a of order 4. Let H = 〈a〉 = {e, a, a2,
a3}. If b ∈ G is not in H, then the coset Hb = {b, ab, a2b, a3b}. By Lagrange’s theorem, G is the union of
He = H and Hb; hence

G = {e, a, a2, a3, b, ab, a2b, a3b}

2 Assume there is in Hb an element of order 2. (Let b be this element.) If ba = a2b, prove that b2a = a4b2,
hence a = a4, which is impossible. (Why?) Conclude that either ba = ab or ba = a3b.
3 Let b be as in part 2. Prove that if ba = ab, then G ≅ 4 × 2.
4 Let b be as in part 2. Prove that if ba = a3b, then G ≅ D4.
5 Now assume the hypothesis in part 2 is false. Then b, ab, a2b, and a3b all have order 4. Prove that b2 =
a2. (HINT: What is the order of b2? What element in G has the same order?)
6 Prove: If ba = ab, then (a3b)2 = e, contrary to the assumption that ord(a3b) = 4. If ba = a2b, then a = b4a
= e, which is impossible. Thus, ba = a3b.
7 The equations a4 = b4 = e, a2 = b2, and ba = a3b completely determine the table of G. Write this table.
(G is known as the quarternion group Q.)
Thus, the only groups of order 8 (up to isomorphism) are 8, 2 × 2 × 2, 4 × 2, D4, and Q.

† I. Conjugate Elements
If a ∈ G, a conjugate of a is any element of the form xax−1, where x ∈ G. (Roughly speaking, a conjugate
of a is any product consisting of a sandwiched between any element and its inverse.) Prove each of the
following:
1 The relation “a is equal to a conjugate of b” is an equivalence relation in G. (Write a ∼ b for “a is
equal to a conjugate of b.”)
This relation ∼ partitions any group G into classes called conjugacy classes. (The conjugacy class
of a is [a] = {xax−1: x ∈ G}.)
For any element a ∈ G, the centralizer of a, denoted by Ca, is the set of all the elements in G which
commute with a. That is,

Ca = {x ∈ G: xa = ax} = {x ∈ G: xax−1 = a}

Prove the following:

2 For any a ∈ G, Ca is a subgroup of G.
3 x−1ax = y−1ay iff xy−1 commutes with a iff xy−1 ∈ Ca.
4 x−1ax = y−1ay iff Cax = Cay. (HINT: Use Exercise El.)
5 There is a one-to-one correspondence between the set of all the conjugates of a and the set of all the
cosets of Ca. (HINT: Use part 4.)
6 The number of distinct conjugates of a is equal to (G: Ca), the index of Ca in G. Thus, the size of every
conjugacy class is a factor of |G.

† J. Group Acting on a Set

Let A be a set, and let G be any subgroup of SA. G is a group of permutations of A; we say it is a group
acting on the set A. Assume here that G is a finite group. If u ∈ A, the orbit of u (with respect to G) is the
set

O(u) = {g(u): g ∈ G}
1 Define a relation ∼ on A by u ∼ υ iff g(w) = υ for some g ∈ G. Prove that ∼ is an equivalence relation
on A, and that the orbits are its equivalence classes.
If u ∈ A, the stabilizer of u is the set Gu = {g ∈ G: g(u) = u}, that is, the set of all the permutations
in G which leave u fixed.
2 Prove that Gu is a subgroup of G.
# 3 Let α = (1 2)(3 4)(5 6) and β = (2 3) in S6. Let G be the following subgroup of S6: G = {ε, α, β, αβ,
βα, αβα, βαβ, (αβ)2}.Find O(1), O(2), O(5), G1, G2, G4, G5.
4 Let f, g ∈ G. Prove that f and g are in the same left coset of Gu iff f(u) = g(u). (HINT: Use Exercise El
modified for left cosets.)
5 Use part 4 to show that the number of elements in O(u) is equal to the index of Gu in G. [HINT: If f(u) =
υ, match the coset of f with υ.]
6 Conclude from part 5 that the size of every orbit (with respect to G) is a factor of the order of G. In
particular, if f ∈ SA, the length of each cycle of f is a factor of the order of f in SA.

K. Coding Theory: Coset Decoding

In order to undertake this exercise set, the reader should be familiar with the introductory paragraphs
(preceding the exercises) of Exercises F and G of Chapter 3 and Exercise H of Chapter 5.
Recall that is the group of all binary words of length n. A group code C is a subgroup of . To
decode a received word x means to find the codeword a closest to x, that is, the codeword a such that the
distance d(a, x) is a minimum.
But d(a, x) = w(a + x), the weight (number of Is) of a + x. Thus, to decode a received word x is to
find the codeword a such that the weight w(a + x) is a minimum. Now, the coset C + x consists of all the
sums c + x as c ranges over all the codewords; so by the previous sentence, if a + x is the word of
minimum weight in the coset C + x, then a is the word to which x must be decoded.
Now a = (a + x) + x; so a is found by adding x to the word of minimum weight in the coset C + x. To
recapitulate: In order to decode a received word x you examine the coset C + x, find the word e of
minimum weight in the coset (it is called the coset leader), and add e to x. Then e + x is the codeword
closest to x, and hence the word to which x must be decoded.

1 Let C1 be the code described in Exercise G of Chapter 3.

(a) List the elements in each of the cosets of C1.
(b) Find a coset leader in each coset. (There may be more than one word of minimum weight in a coset;
choose one of them as coset leader.)
(c) Use the procedure described above to decode the following words x: 11100, 01101, 11011, 00011.
2 Let C3 be the Hamming code described in Exercise H2 of Chapter 5. List the elements in each of the
cosets of C3 and find a leader in each coset. Then use coset decoding to decode the following words x:
1100001, 0111011, 1001011.
3 Let C be a code and let H be the parity-check matrix of C. Prove that x and y are in the same coset of C
if and only if Hx = Hy. (HINT: Use Exercise H8, Chapter 5.)
If x is any word, Hx is called the syndrome of x. It follows from part 3 that all the words in the same
coset have the same syndrome, and words in different cosets have different syndromes. The syndrome of a
word x is denoted by syn(x).
4 Let a code C have q cosets, and let the coset leaders be e 1, e 2, …, e q. Explain why the following is true:
To decode a received word x, compare syn(x) with syn(e 1, …, syn(e q) and find the coset leader e i such
that syn(x) = syn(e i). Then x is to be decoded to x + e i.
5 Find the syndromes of the coset leaders in part 2. Then use the method of part 4 to decode the words x =
1100001 and x = 1001011.