All right cosets contain |H| elements. If Ha Hb , then Ha = Hb A function that is both one-to-one and onto, that is if f(x) = f(y) then x = y, and for every y of the domain there is an x of the range so that f(x) = y. A commutative group The number of elements in a cyclic group. The set of integers. The set of real numbers. The set of natural numbers. The set residue classes mod n. H is closed under · ; that is, for x,y H, we have x · y H. 1G H. If x H, then x-1 H. Let H G, H . Then H is a subgroup if and only if for a,b H, we have a · b-1 H. Let a be a nonnegative integer and let b be a positive integer. Then there exist natural numbers q and r such that 0 < r < b and a = bq + r.

### Subgroups and Cosets

Throughout this section let G denote a group, H G a nonempty subset. Our goal is to study the properties of those subsets H which are groups.

Definition 1: We say that H is a subgroup of G if H is a group with respect to the multiplication · of G.

Since · is already associative with respect to the elements of G, it is automatically associative for elements of H. Therefore, from the group axioms, we deduce that H is a subgroup of G if and only if H has the following properties

SG1: H is closed under · ; that is, for x,y H, we have x · y H.

SG2: 1G H.

SG3: If x H, then x-1 H.

These three properties can be combined into a simple test for H to be a subgroup:

Proposition 2: Let H G, H . Then H is a subgroup if and only if for a,b H, we have a · b-1 H.

Proof: There are two statements to prove. First assume that H is a subgroup of G and that a,b H Let us show that a · b-1 H. By (SG3), b-1 H, and therefore by (SG1), a · b-1 H.

Conversely, assume that H G and that for a,b H, we have a · b-1 H. It suffices to show that the properties (SG1)-(SG3) are satisfied. Since H , there exists a H. Therefore, 1G = a · a-1 H and thus (SG2) holds. Moreover, if b H, b-1 = 1G· b-1 H. Therefore, (SG3) holds. Finally, if a,b H, then b-1 H. by (SG3), which we have just proved. Note that (b-1)-1 = b since b-1· b = b · b-1 = 1G. Therefore, a · b = a·(b-1)-1 H and (SG1) holds.

Example 1: Let G denote the group of symmetries of the square. Two subgroups of G are given by

H1 = {I, R, R2, R3},
H2 = {I, F}.

Example 2: More generally, the dihedral group Dn contains two subgroups.

H1 = {I, R, R2,...,Rn-1},
H2 = {I, F}.

Example 3: Let k Z, and let

kZ = {k · r | r Z}.

Then kZ is a subgroup of Z, considered as a group under addition.

Example 4: The group C of continuous functions on R is a subgroup of the group of all functions on R.

Example 5: Let f be the polynomial (x2- 2)(x2- 3) with roots +, +. The set of permutations of the roots forms a group (essentially S4). The four permutations of this group defined by +, -+, +, and -+ form a subgroup.

If is any nonempty collection of subgroups of the group G, then the intersection H* = is a subgroup of G.

Theorem 3: If is any nonempty collection of subgroups of the group G, then the intersection

H* =

is a subgroup of G.

Proof: First observe that H* since 1G H for all H , so that 1G H*. Let us apply Proposition 2. Let a,b H*. Then, for every H , we have a,b H. Thus, since H is a subgroup of G, a·b-1 H. Therefore, a·b-1 H* and H* is a subgroup of G.

We shall now consider a general technique for manufacturing subgroups of a group G. Let S be any subset of G. Let be the collection of all subgroups containing S. is nonempty because G . By Theorem 3

[S] =

is a subgroup of G and by the definition of , [S] contains S. Actually [S] is the smallest subgroup of G which contains S. For if H is a subgroup of G containing S, then H , so that [S] H.

Definition 4: [S] is called the subgroup of G generated by S. If [S] = G, then S is said to be a set of generators for G.

We can give another description of [S]. It is clear that [S] contains all products of the form

(1)
a1·a2·a3·...·an,

where either ai S or ai-1 S (1 < i < n). But the set of all these products forms a subgroup H of G. And this subgroup contains S. Therefore [S] H. But we also have H [S]. Therefore, H = [S]. In other words, [S] is the subgroup of G consisting of all products of the form (1). For example, Dn is generated by S = {R, F}.

Definition 5: A group G is said to be cyclic if G is generated by a single element. That is, G is cyclic if there exists a G such that G = [S], where S = {a}.

From our above characterization of [S] we see that G is cyclic if and only if there exists a G such that

G = {...,a-2,a-1,1G,a,a2,...}.

The element a is usually not unique. Moreover, the various powers of a need not all be distinct. We will study this possibility more closely below.

Cyclic groups are the simplest groups. Later we will prove the fundamental theorem of abelian groups, which states that the cyclic groups are the building blocks from which abelian groups with a finite number of generators can be built.

We have already met several examples of cyclic groups.

Example 6: G = Z is a cyclic group. As a generator we may take 1.

Example 7: G = Zn(residue classes modulo n) is a finite cyclic group of order n. As a generator we may take 1.

Example 8: Let G be an arbitrary group, a G. Set S = {a}. Then [S] is a cyclic subgroup of G. We will usually denote this subgroup by [a].

Definition 6: Let G be a group and let a G. If [a] is finite, then we define the order of a to be the number of elements in [a]. If [a] is infinite, we define the order of a to be infinity.

Proposition 7: Suppose that a has finite order r. Then r is the smallest positive integer such that ar = 1G, and [a] = {1G,a,...,ar-1}.

Proof: Since [a] is finite, not all of the powers am (m N) are distinct. Suppose that am = an (m, n > 0, m > n). Then am-n = 1G and m - n > 0. Therefore, there exist positive integers r such that ar = 1G. Let r be the smallest such. We will prove that [a] = {1G=a0, a, a2,...,ar-1}, where the powers of a mentioned are all distinct. Indeed, if ai = aj (0 < i < j < r-1), then aj-i = 1G and 0 < j-i < r, which is a contradiction to the definition of r. Therefore, the powers aj (0 < j < r-1) are all distinct. Let [a]. In order to prove our assertion, it suffices to show that = aj for some j (0 < j < r-1). But = an for some n Z. Assume for the moment that n > 0. By the division algorithm, there exist p,q N such that

n = pr + q    (0 < q < r - 1).

Then

= an = apr+q = (ar)paq
= aq    (since ar = 1).

Thus, we are done in the case n > 0. If n < 0, then -n > 0, so that by what we have already proved, we see that -1 = a-n = aj for some j (0 < j < r - 1). If j = 0, then we may take n = 0, in which case the assertion has already been proved. Thus we may assume that j > 0. Then

= a-j = ara-j = ar-j

and 0 < r - j < r - 1. Thus, the assertion is proved for n < 0.

Proposition 8: Suppose that a has infinite order. Then ar 1G for all r Z-{0}, and [a] = {...,a-2,a-1,1G,a,a2,...}, where all the powers of a are distinct.

Proof: It suffices to consider the case r > 0, for if ar = 1G, then a-r = 1G. By exactly the same reasoning as we used to prove Proposition 7, we see that if, for some r > 0, we have ar = 1G, then

[a] = {1G = a0, a1,..., ar-1}.

(The powers of a may not all be distinct, however.) But this contradicts the fact that [a] is infinite. Moreover, if ai = aj, then ai-j= 1G, so that i - j = 0 by what we just proved. Thus, all powers of a are distinct.

Combining Propositions 7 and 8 we can say something about cyclic groups. Let G be a cyclic group with generator a. There are two cases to consider

Case 1: G is finite. Suppose that G has order r. Then by Proposition 7,

G = {1G= a0, a1, a2,..., ar-1},

and ar = 1G.

Case 2: G is infinite. In this case,

G = {...,a-2, a-1, a0 = 1G, a1, a2,...},

where all powers of a are distinct.

Note that in case 1, G closely resembles Zr, while in case 2, G closely resembles Z. In fact, in a later section, we will show that for purposes of group theory, any cyclic group is either Z of Zr.

Let us now return to the consideration of the subgroups of an arbitrary group G. One very important, but difficult, problem is to determine all of the subgroups of G. When G is finite, the problem can be solved by brute force. For we can list all of the subsets of G and then test each subset to determine whether it is a subgroup. But this solution to the problem is not very practical. Therefore, we must look for some simple criteria which can rule out most subsets of G from being subgroups. The simplest criterion is due to Lagrange and is one of the most fundamental theorems in the theory of groups.

Theorem 9(Lagrange): Let G be a finite group, H a subgroup of G. Then the order of H divides the order of G.

Before proving Lagrange's theorem, it will be necessary for us to build up some machinery. This machinery may seem very ad hoc at this time, but the ideas we will develop here will be quite natural and will be extremely important later when we define quotient groups

Let a G and set

Ha = {ha | h H},

The set Ha is called a right coset of G with respect to H. We could just as easily consider left cosets of the form

aH = {ah | h H}.

But throughout this argument, we will stick to right cosets. We will denote the set of all right cosets of G with respect to H by H\G. The set of all left cosets will be denoted G/H. The element a is called a representative of aH.

Lemma 10: All right cosets contain |H| elements.

Proof: It is clear that Ha contains at most |H| elements. In order to prove that the number is exactly |H|, it suffices to show that all the elements h · a (h H) are different. But if

h1·a = h2·a    (h1, h2 H),

we have h1= h2 on multiplying on the right by a-1.

Lemma 11: If Ha Hb , then Ha = Hb.

Proof: Let g Ha Hb. Then

g = h1· a = h2· b   (h1,h2 H)

Therefore, a = h1-1· h2· b and

(1)
Ha = Hh1-1·h2·b.

Since H is a subgroup, h1-1· h2 H, so that Hh1-1·h2 H. Moreover, if h H, then h = (h · h2-1· h1) · (h1-1· h2) Hh1-1· h2. Therefore, H Hh1-1· h2 and we have shown that H = Hh1-1· h2. Thus, by (1),

Ha = Hb.

Every element of G is contained in some right coset. For example, a is contained in Ha. Let the number of distinct cosets of G with respect to H be k. Then if the right cosets are

Ha1, Ha2, ..., Hak,

we can write

(2)
G = Ha1 Ha2 ... Hak.

By Lemma 11, the union of (2) defines a partition of G and, by Lemma 10, each subset of the partition contains |H| elements.

Proof of Lagrange's Theorem: Let |G| = n, |H| = m. Then by (2) and the remarks just made, we see that

n = km |H||G|.

Earlier we showed that with every partition of a set, there is associated an equivalence relation such that the subsets in the partition are precisely the equivalence classes of the equivalence relation. In the case of the partition (2), the equivalence relation is

(3)
a ~ b b · a-1 H.

Remark: Lagrange's theorem does not assert that if m is a positive integer which divides the order of G, then there exists a subgroup H of G having order m. In fact, this statement is false.

Lagrange's theorem has a number of very important consequences. To mention but a few:

Corollary 12: Let G be a finite group, a G. Then the order of a divides |G|.

Proof: The order of a equals the order of the subgroup [a] of G. Therefore, the assertion follows directly from Lagarange's theorem.

Corollary 13: Let G be a finite group of order n, a G. Then an = 1G.

Proof: Let m denote the order of a. Then by Corollary 12, m|n n = m · k for some positive integer k. Therefore,

an = amk = (am)k = 1Gk = 1G.

Corollary 14: A group of prime order is cyclic.

Proof: Let G have a prime order p. Then the only positive divisors of p are 1 and p. Let a G, a 1G. By Corollary 12, the order of [a] divides p, so that [a] has either 1 or p elements. But [a] contains 1G and a, so that [a] has p elements. Therefore, G = [a] and G is cyclic.

Corollary 15: Let n be a positive integer, (a,n) = 1. Then

a(n)1 (mod p).

where (n) denotes Euler's function. In particular, if p is prime and p a, then

ap-1 1 (mod p).

Proof: Let us apply Corollary 13 to the element a of the group Znx of order (n). We get that

a(n) = a(n) = 1.

Therefore,

a(n) 1 (mod n).

Corollary 15 was first discovered by Pierre Fermat in case n = a prime number and is known as "Fermat's little theorem." The general form of Corollary 15 is due to Euler.

Let m be a positive integer. Since [am] is a subgroup of [a], Corollary 12 implies that the order of am divides the order of a. However, we can be much more specific:

Theorem 16: Let a have order n. then am has order n/(n,m). In particular if (m,n) = 1, then am has order n.

Proof: Let us first consider two special cases of the theorem:

Case 1: m|n. Suppose that n = k · m. Then (n,m) = m, so that we must prove that am has order n/m = k. First, it is clear that (am)k = an = 1G. Suppose that r is a positive integer less than k such that (am)r = 1G. Then amr = 1G and m · r < n. But this contradicts the assumption that n is the smallest positive integer such that an = 1G. Thus, k is the smallest positive integer such that (am)k = 1G; that is am has order k.

Case 2: (m,n) = 1. In this case we must prove that am has order n. Let r be the smallest positive integer such that (am)r = 1G. Since (m,n) = 1, there exists integers s,t such that ms + nt = 1 Therefore,

msr + ntr = r

and

ar = amsr · antr
=(am)rs · (an)tr
= 1G.

Therefore, since a has order n, we see that r > n. But since (am)n = 1G, we have r = n; that is, am has order n.

General Case: Suppose that (m,n) = p. Set

m = m0p,  n = n0p.

Then (m0,n0) = 1, since if (m0,n0) > 1, we have (m,n) > p. By case 1, ap has order n/p = n0. Therefore, by Case 2, am = (ap)m0 has order n0 = n/(n,m).

Definition 17: Let G be a group, and let H be a subgroup of G. The number of right cosets in H\G is called the index of H in G and is denoted [G:H].

The mapping f:H\G G/H which maps the right coset Ha onto the left coset a-1H is easily seen to be a bijection, so [G:H] could just as well be defined as the number of left cosets in G/H. From our proof of Lagrange's theorem we see that |G| = |H|·[G:H], in case G is a finite group.

Before leaving this section, it is important to reiterate the notion that the cosets of subgroup H of G form a partition of G. This is of fundamental importance in our studies. To summarize this fact we present the following theorem which is actually just rewording what was already stated. Proof of which is given by Lemma 10 and Lemma 11.

Theorem 18: If H is a subgroup of G and aH and bH are cosets of H then

(1) aH = bH or aH and bH are disjoint.

(2) aH and bH are equivalent sets.