A.3 Groups
Consider a prime number p. The procedures of adding elements in Z_{p} and multiplying elements in Z^{*}_{p} share certain properties:
 Both operations are associative, that is, a + (b + c) = (a +b) + c and a (b c) = (a b) c.
 There is an additive identity 0 with the property that 0+a = a+0 = a for all a. The corresponding multiplicative identity is the element 1; 1 ·a = a ·1 = a.
 For each a Î Z_{p}, there is a b such that a+b = 0; namely, b = a has this property. By (3) in Section A.2, the equation ax = 1 has an integer solution x : = a^{1} for each a Î Z_{p}^{*}. Namely, since p is a prime, gcd(a,p) = 1. The elements a and a^{1} are the additive and multiplicative inverses of a, respectively.
Structures with these three properties have turned out to be of such a great importance that they have a name; they are called groups.
Formally, a group consists of a set G (finite or infinite) together with a binary operation * : G ×G ® G called (group) multiplication. Note that ``* : G ×G ® G'' means that G is closed under multiplication, that is, the product a*b is in G for any two elements a, b in G. A group must satisfy the following axioms:
 The operation * is associative, that is, a*(b*c) = (a*b)*c for any a, b, c Î G.
 There exists an identity element e Î G such that a*e = e*a = a for each element a Î G.
 Each element a Î G has an inverse b Î G satisfying a*b = b*a = e = the identity.
If, in addition, multiplication in G is commutative, that is, a*b = b*a for any two elements a,b Î G, then the group is abelian.
A group is usually identified with its underlying set, unless the group operation is not clear from context. From now on, we will suppress the group operation * and simply write ab instead of a*b. For n ³ 1, g^{n} means multiplication of g with itself n times (for example, g^{3} = ggg), while g^{n} is the inverse of g^{n}. g^{0} is the identity element. Note that g^{a} g^{b} = g^{a+b} for all integers a, b.
A subgroup H of a group G is a group such that the set H is a subset of G. Any subset S of G generates a subgroup áS ñ of G consisting of all elements of the form
s_{1}^{a1} ¼s_{n}^{an}, 
where s_{1}, ¼, s_{n} are (not necessarily distinct) elements in S and a_{1}, ¼, a_{n} are (not necessarily positive) integers. If G = ág ñ for some g Î G, then G is cyclic with generator g. This means that every element in G is of the form g^{k} for some integer k. All cyclic groups are abelian.
Examples
 The set Z of integers is a cyclic group under addition with generator 1. However, the set of nonzero integers is not a group under multiplication. Namely, for a ¹ ±1, there is no integer b such that ab = 1.
 The sets Q, R, and C of rational, real, and complex numbers are all abelian groups under addition. Moreover, Q^{*}, R^{*}, and C^{*} (the above sets with 0 removed) are all abelian groups under multiplication. Namely, the inverse of a number x is 1/x.
 The set Z_{n} is a cyclic group under addition. If n = ab is a composite number with a, b > 1, then the set {1, ¼,n1} is not a group under multiplication modulo n. Namely, the product of a and b is equal to 0 modulo n, which implies that the set is not even closed under multiplication. However, the subset Z_{n}^{*} is a group under multiplication. If n is a prime, then Z_{p}^{*} is a cyclic group of order p1.
 The set Z under subtraction is not a group. Namely, subtraction is not associative; a  (bc) ¹ (ab)c unless c = 0.

For a given set A, the set S_{A} of permutations (bijective functions) p: A ® A is a group under composition °. For example, composition is associative, because
p°(r°s) (a) = p(r(s(a))) = (p°r) °s(a). However, unless A consists of at most two elements, S_{A} is not abelian. For example, with A = Z_{3}, p(a) = a +1, and s(a) = 2 a, we have
p°s(0) = p(s(0)) = p(0) = 1 ¹ 2 = s(1) = s(p(0)) = s°p(0).