Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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:
Connect with EMCConnect with EMC
Need help immediately? EMC Sales Specialists are standing by to answer your questions real time.
Use Live Chat for fast, direct access to EMC Customer Service Professionals to resolve your support questions.
Explore and compare EMC products in the EMC Store, and get a price quote from EMC or an EMC partner.
We're here to help. Send us your sales inquiry and an EMC Sales Specialist will get back to you within one business day.
Want to talk? Call us to speak with an EMC Sales Specialist live.