• 1-781-515-5000
RSA LABORATIORIES
11 Cambridge Center
Cambridge, MA 02142 - USA

# RSA Laboratories

## A.3 Groups

Consider a prime number p. The procedures of adding elements in Zp and multiplying elements in Z*p share certain properties:

1. Both operations are associative, that is, a + (b + c) = (a +b) + c and a (b c) = (a b) c.
2. 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.
3. For each a Î Zp, 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 Î Zp*. 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:

1. The operation * is associative, that is, a*(b*c) = (a*b)*c for any a, b, c Î G.
2. There exists an identity element e Î G such that a*e = e*a = a for each element a Î G.
3. 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, gn means multiplication of g with itself n times (for example, g3 = ggg), while g-n is the inverse of gn. g0 is the identity element. Note that ga gb = ga+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

 s1a1 ¼snan,

where s1, ¼, sn are (not necessarily distinct) elements in S and a1, ¼, an 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 gk 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 Zn is a cyclic group under addition. If n = ab is a composite number with a, b > 1, then the set {1, ¼,n-1} 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 Zn* is a group under multiplication. If n is a prime, then Zp* is a cyclic group of order p-1.
• The set Z under subtraction is not a group. Namely, subtraction is not associative; a - (b-c) ¹ (a-b)-c unless c = 0.
• For a given set A, the set SA 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, SA is not abelian. For example, with A = Z3, 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).

Top of the page

Notes: