# document.write (document.title)

## 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 φ(12), where φ 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,

So the residues, mod n, of the elements {aa1, aa2, aa3, ..., aaφ(n)} are {a1, a2, a3, ..., aφ(n)}, in some order.  In particular, one of the elements aak 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.

### Multiplicative Group

Proof that any finite multiplicative subgroup of a field (not necessarily finite) is cyclic.

First, note Euler's formula that the sum of totients of divisors of n is n:

 ∑ m|n φ(m) = n, or   φ(n) = n − ∑ m|n, m≠n φ(m)

Second, note the Fundamental Theorem of Algebra, which says that in any field, xm-1=0 has at most m roots.

By showing that the number of elements of order m is no greater than φ(m), and the sum of all ele orcing there to be an element of the highest order by bounding the total number of elements of any smaller order. I like it.

Proof.  Let G be a finite group of order n.  Partition G into disjoined subsets Gm of elements of same order m and, for these m, we have

 ∑ m |Gm| = n, or   |Gn| = n - ∑ m≠n |Gm|

Now, for an arbitrary m, pick g in Gm, then the first m powers of g are solutions for the equation xm-1=0.  Thus the elements of G of order m, namely the elements of Gm, are contained in the cyclic group generated by g. These elements are actually the generators of <g>, the number of which is given by φ(m).  Thus |Gm|=φ(m).   By Euler's formula (the second formulation, above), and the fact that |Gm|=φ(m), it follows that in particular, |Gn|=φ(n)>0.  Therefore, there is an element of G of order n, and G is cyclic.

. . . . . . this proof, above, seems messed-up, because it doesn't really use the Euler formula.  I think some of the = signs should be replaced by inequalities, and then it will make more sense.

. . . . . . 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.

Groups - a set with a group operation xy (multiplication), that satisfies the four group axioms.

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 this Math Help site is Graeme McRae.