All right cosets contain |H| elements. If Ha intersection Hb not equal empty set, 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 element of H, we have x · y element of H. 1G element of H. If x element of H, then x-1 element of H. Let H subset of G, H not equal empty set. Then H is a subgroup if and only if for a,belement of H, we have a · b-1 element of 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 subset of 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 element of H, we have x · y element of H.

SG2: 1G element of H.

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

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

Proposition 2: Let H subset of G, H not equal empty set. Then H is a subgroup if and only if for a,b element of H, we have a · b-1 element of H.

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

Conversely, assume that H subset of G and that for a,b element of H, we have a · b-1 element of H. It suffices to show that the properties (SG1)-(SG3) are satisfied. Since H not equalempty set, there exists a element of H. Therefore, 1G = a · a-1 element of H and thus (SG2) holds. Moreover, if b element of H, b-1 = 1G· b-1element of H. Therefore, (SG3) holds. Finally, if a,b element of H, then b-1 element of 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 element of 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 element of Z, and let

kZ = {k · r | r element of 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 f of all functions on R.

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

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

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

H* = intersection of subgroups

is a subgroup of G.

Proof: First observe that H*not equalempty set since 1G element of H for all Helement of collection, so that 1G element of H*. Let us apply Proposition 2. Let a,b element of H*. Then, for every Helement of collection, we have a,b element of H. Thus, since H is a subgroup of G, a·b-1element of H. Therefore, a·b-1element of 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 collection be the collection of all subgroups containing S. collection is nonempty because G element of collection. By Theorem 3

[S] = intersection of subgroups

is a subgroup of G and by the definition of collection, [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 element of collection, so that [S] subset of 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 aielement of S or ai-1element of S (1 < i < n). But the set of all these products forms a subgroup H of G. And this subgroup contains S. Therefore [S] subset of H. But we also have H subset of [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 element of 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 element of 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 element of 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 element of 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 element of 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 alphaelement of [a]. In order to prove our assertion, it suffices to show that alpha = aj for some j (0 < j < r-1). But alpha = an for some n element of Z. Assume for the moment that n > 0. By the division algorithm, there exist p,q element of N such that

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

Then

alpha = 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 alpha-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

alpha = 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 not equal 1G for all r element of 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 element of G and set

Ha = {ha | h element of 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 | helement of 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 element of H) are different. But if

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

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

Lemma 11: If Ha intersection Hb not equal empty set, then Ha = Hb.

Proof: Let g element of Ha intersection Hb. Then

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

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

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

Since H is a subgroup, h1-1· h2element of H, so that Hh1-1·h2 subset of H. Moreover, if h element of H, then h = (h · h2-1· h1) · (h1-1· h2) element of Hh1-1· h2. Therefore, H subset of 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 union Ha2 union ... union 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 implies |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 equivalent to b · a-1 element of 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 element of 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 element of G. Then an = 1G.

Proof: Let m denote the order of a. Then by Corollary 12, m|n implies 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 element of G, a not equal 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

aphi(n)congruent to1 (mod p).

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

ap-1 congruent to 1 (mod p).

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

aphi(n) = aphi(n) = 1.

Therefore,

aphi(n) congruent to 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 maps 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.