Group

A group is a set and an operation (the group operation, which you can think of as multiplication) that satisfies the four group properties:

1. Closure: if A and B are two elements in group G then their product AB is also an element of G.

2. Associativity: if A, B, and C are elements of G then (AB)C = A(BC)

3. Identity: an element, I, of G exists such that IA = AI = A for every element, A, of G.

4. Inverse: for each element, A, of G, there exists an inverse of A, denoted A^-1, such that AA^-1=A^-1A=I

Examples of Groups

The integers under addition form a group.  You can check this by testing each of the four properties.  Closure is assured because whenever you add two integers, the result is another integer.  Associativity is another property that is part of the definition of integers.  Zero is the identity element under addition, and -- sure enough! -- zero is an integer.  Finally, if A is an integer, then -A is also an integer.

Note that the integers under multiplication do not form a group, because the inverse property is not satisfied.  However the non-zero rationals do form a group under multiplication.

The two groups mentioned above are "infinite" groups -- that is, they have an infinite number of elements.  Finite groups are those that have a finite number (called the group's "order") of elements.

Consider the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} under addition (mod 12).  This is a group because it is closed, associative, 0 is the identity element, and -a is the inverse of a.  (-a is equivalent to 12-a (mod 12).)

The set is also closed under multiplication (mod 12), but not every element has an inverse.  In fact, no element that shares a factor with 12 has an inverse, because there isn't any way to multiply such an element with another element to shed that factor.  For example, 2 times any element (mod 12) is divisible by 2, and so can't be equivalent to 1 (mod 12).

This suggests a trick that will turn this set into a group under multiplication, mod 12: remove all the elements that share a factor with 12.  Or, more exactly, leave in just those elements that are coprime to 12.  They are {1, 5, 7, 11}.  The number of such elements is f(12), where f is the Euler Totient Function. Surprisingly, the coprimes of n form a group under multiplication, mod n.  It's not hard to test each of the four properties to verify it's true.

Let G = {x | GCD(x,n)=1} be a set, considered under the operation of multiplication, mod n.

Closure: if a and b, elements of G, are coprime to n, i.e. no factor of a is also a factor of n, and no factor of b is a factor of n, then their product, ab, has no factor that is also a factor of n, so ab is an element of G.

Associativity: ab=ba, which is a property of multiplication.

Identity: 1 is coprime with every number, so it is coprime with n, and thus 1 is an element of G.

Inverse: This one is tricky.  If a, b, and c are elements of G, and b ≠ c, then ab ≠ ac

Proof: Suppose ab=ac, (mod n).
That means ab-ac=nk, for some integer, k.
a(b-c)=nk, and since n is larger than (b-c) in absolute value, k must be smaller than a in absolute value.
a is coprime to n, because a is an element of G, so a|k, and since a is larger than k, k must be zero,
hence b=c, a contradiction.

So the residues, mod n, of the elements {aa₁, aa₂, aa₃, ..., aa_f(n)} are {a₁, a₂, a₃, ..., a_f(n)}, in some order.  In particular, one of the elements aa_k is equivalent, mod n, to 1.  So a has an inverse.

See Euler's Totient Theorem, which is a generalization of Fermat's Little Theorem.  Its proof uses the same logic we just use to prove that an inverse exists.

Additional topics

 . . . . . . add introductory information about these topics, with reference to BasicAAGroup.htm for more in-depth infoc:

Subgroup

Coset

Lagrange's Theorem

There are two dueling "Group" pages in this website -- BasicAAGroup.htm was created, but a lot of information is in BasicSetGroup.htm, so these pages need to be coordinated (BasicSetGroup.htm should be elementary, with more advanced theory in BasicAAGroup.htm.)  

Internet References

Group, from Mathworld

Related pages in this website

Basic Principles

Sets - how to construct sets of integers, reals, etc.

Rings - sets with two operations (+ and *), identity elements, and other properties.

Fermat's Theorems -- Fermat's Little Theorem, in particular.

Euler's Totient Theorem -- a generalization of Fermat's Little Theorem

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]