theorem.

Abelian groups are lurking everywhere, as the following examples illus-

trate.

Example 8.1. The set of integers Z under addition forms an abelian group,

with 0 being the identity, and ’a being the inverse of a ∈ Z. 2

Example 8.2. For integer n, the set nZ = {nz : z ∈ Z} under addition

forms an abelian group, again, with 0 being the identity, and n(’z) being

the inverse of nz. 2

Example 8.3. The set of non-negative integers under addition does not

form an abelian group, since additive inverses do not exist for positive inte-

gers. 2

Example 8.4. The set of integers under multiplication does not form an

abelian group, since inverses do not exist for integers other than ±1. 2

Example 8.5. The set of integers {±1} under multiplication forms an

abelian group, with 1 being the identity, and ’1 its own inverse. 2

Example 8.6. The set of rational numbers Q = {a/b : a, b ∈ Z, b = 0}

under addition forms an abelian group, with 0 being the identity, and (’a)/b

being the inverse of a/b. 2

182 Abelian groups

Example 8.7. The set of non-zero rational numbers Q— under multiplica-

tion forms an abelian group, with 1 being the identity, and b/a being the

inverse of a/b. 2

Example 8.8. The set Zn under addition forms an abelian group, where

[0]n is the identity, and where [’a]n is the inverse of [a]n . 2

Example 8.9. The set Z— of residue classes [a]n with gcd(a, n) = 1 under

n

multiplication forms an abelian group, where [1]n is the identity, and if b is

a multiplicative inverse of a modulo n, then [b]n is the inverse of [a]n . 2

Example 8.10. Continuing the previous example, let us set n = 15, and

enumerate the elements of Z— . They are

15

[1], [2], [4], [7], [8], [11], [13], [14].

An alternative enumeration is

[±1], [±2], [±4], [±7]. 2

Example 8.11. As another special case, consider Z— . We can enumerate

5

the elements of this groups as

[1], [2], [3], [4]

or alternatively as

[±1], [±2]. 2

Example 8.12. For any positive integer n, the set of n-bit strings under

the “exclusive or” operation forms an abelian group, where the “all zero”

bit string is the identity, and every bit string is its own inverse. 2

Example 8.13. The set of all arithmetic functions f , such that f (1) = 0,

with multiplication de¬ned by the Dirichlet product (see §2.6) forms an

abelian group, where the special arithmetic function I is the identity, and

inverses are provided by the result of Exercise 2.27. 2

Example 8.14. The set of all ¬nite bit strings under concatenation does

not form an abelian group. Although concatenation is associative and the

empty string acts as an identity element, inverses do not exist (except for

the empty string), nor is concatenation commutative. 2

Example 8.15. The set of 2 — 2 integer matrices with determinant ±1,

together with the binary operation of matrix multiplication, is an example of

a non-abelian group; that is, it satis¬es properties (i)“(iii) of De¬nition 8.1,

but not property (iv). 2

8.1 De¬nitions, basic properties, and examples 183

Example 8.16. The set of all permutations on a given set of size n ≥

3, together with the binary operation of function composition, is another

example of a non-abelian group (for n = 1, 2, it is an abelian group). 2

Note that in specifying a group, one must specify both the underlying set

G as well as the binary operation; however, in practice, the binary operation

is often implicit from context, and by abuse of notation, one often refers to

G itself as the group. For example, when talking about the abelian groups

Z and Zn , it is understood that the group operation is addition, while when

talking about the abelian group Z— , it is understood that the group operation

n

is multiplication.

Typically, instead of using a special symbol like “ ” for the group oper-

ation, one uses the usual addition (“+”) or multiplication (“·”) operations.

For any particular, concrete abelian group, the most natural choice of no-

tation is clear (e.g., addition for Z and Zn , multiplication for Z— ); however,

n

for a “generic” group, the choice is largely a matter of taste. By conven-

tion, whenever we consider a “generic” abelian group, we shall use additive

notation for the group operation, unless otherwise speci¬ed.

If an abelian group G is written additively, then the identity element is

denoted by 0G (or just 0 if G is clear from context), and the inverse of an

element a ∈ G is denoted by ’a. For a, b ∈ G, a ’ b denotes a + (’b). If

n is a positive integer, then n · a denotes a + a + · · · + a, where there are n

terms in the sum”note that 1 · a = a. Moreover, 0 · a denotes 0G , and if n

is a negative integer, then n · a denotes (’n)(’a).

If an abelian group G is written multiplicatively, then the identity element

is denoted by 1G (or just 1 if G is clear from context), and the inverse of

an element a ∈ G is denoted by a’1 or 1/a. As usual, one may write ab in

place of a · b. For a, b ∈ G, a/b denotes a · b’1 . If n is a positive integer,

then an denotes a · a · · · · · a, where there are n terms in the product”note

that a1 = a. Moreover, a0 denotes 1G , and if n is a negative integer, then

an denotes (a’1 )’n .

An abelian group G may be in¬nite or ¬nite. If the group is ¬nite, we

de¬ne its order to be the number of elements in the underlying set G;

otherwise, we say that the group has in¬nite order.

Example 8.17. The order of the additive group Zn is n. 2

Example 8.18. The order of the multiplicative group Z— is φ(n), where φ

n

is Euler™s phi function, de¬ned in §2.4. 2

Example 8.19. The additive group Z has in¬nite order. 2

184 Abelian groups

We now record a few more simple but useful properties of abelian groups.

Theorem 8.3. Let G be an abelian group. Then for all a, b, c ∈ G and

n, m ∈ Z, we have:

(i) if a + b = a + c, then b = c;

(ii) the equation a + x = b has a unique solution x ∈ G;

(iii) ’(a + b) = (’a) + (’b);

(iv) ’(’a) = a;

(v) (’n)a = ’(na) = n(’a);

(vi) (n + m)a = na + ma;

(vii) n(ma) = (nm)a = m(na);

(viii) n(a + b) = na + nb.

Proof. Exercise. 2

If G1 , . . . , Gk are abelian groups, we can form the direct product

G := G1 — · · · — Gk , which consists of all k-tuples (a1 , . . . , ak ) with

a1 ∈ G1 , . . . , ak ∈ Gk . We can view G in a natural way as an abelian

group if we de¬ne the group operation component-wise:

(a1 , . . . , ak ) + (b1 , . . . , bk ) := (a1 + b1 , . . . , ak + bk ).

Of course, the groups G1 , . . . , Gk may be di¬erent, and the group operation

applied in the ith component corresponds to the group operation associated

with Gi . We leave it to the reader to verify that G is in fact an abelian

group.

Exercise 8.1. In this exercise, you are to generalize the M¨bius inversion

o

formula, discussed in §2.6, to arbitrary abelian groups. Let F be the set

of all functions mapping positive integers to integers. Let G be an abelian

group, and let G be the set of all functions mapping positive integers to

elements of G. For f ∈ F and g ∈ G, we can de¬ne the Dirichlet product

f g ∈ G as follows:

(f g)(n) := f (d)g(n/d),

d|n

the sum being over all positive divisors d of n. Let I, J, µ ∈ F be as de¬ned

in §2.6.

(a) Show that for all f, g ∈ F and all h ∈ G, we have (f g) h = f (g h).

(b) Show that for all f ∈ G, we have I f = f .

(c) Show that for all f, F ∈ G, we have F = J f if and only if f = µ F .

8.2 Subgroups 185

8.2 Subgroups

We next introduce the notion of a subgroup.