Lagrange’s Theorem
Introduction
Lagrange’s
theorem is about finite groups. A finite group G is a special kind of a set
with a natural number n of elements, n > 0.
In general,
a group G is a set in which there is defined an operation like addition,
multiplication or any other. Let´s call * a generic operation. The following
conditions define a group G, with respect to the operation *: (G, *).
1. If a, b are elements of G, then a*b
is an element of G
2. (a * b) * c = a * (b * c), for all
a, b, c elements of G
3. There is a unique element e in G
such that x * e = x = x * e, for all x in G
4. For each x in G there is exactly one
x’ in G such that x *x’ = e = x´ *x
If a * b =
b * a for all a, b in G then the group is commutative (or abelian)
The element
e is called neutral or identical. For each element a in G; a’ is called the
inverse of a with respect to the operation *.
One of the
more known groups is Z, the set of
integers, an infinite group. For this group, the operation is addition (* is
+), the identical element is 0 (e is 0) and a’, the inverse of integer a with
respect to addition, is -a (a’ is -a).
The set
{[0], [1], [2], [3], [4]} of integers, mod 5 is a finite group with respect to
addition mod 5. In this case, [0] is the identical, [3]’ = [2], [4]’ = [1].
Subgroups of a group
If H is a
subset of a group G and H itself is a group, with respect to the operation
defined in G, then H is a subgroup of G. For each group G there are two trivial
subgroups: G and {e}. Any other subgroups of a group are called proper
subgroups of it.
Example:
the set of even integers is a proper subgroup of the group (Z, +).
Cosets
The concept
of coset for a given subgroup will be useful in the development of
Lagrange’s Theorem.
Let H be a
subgroup of the group (G, *). If g is an element of G, then the set
g*H = {g*x| x is an element of H}
Is called a
left coset for H.
Analogously,
H*g is defined as a right coset for H. If G is an abelian group, there is no
difference between right and left cosets.
Example. Let
G = {[1], [2], [3], [4], [5], [6]}. This is the set of integers mod 7, without
[0]. It may be verified that G is a group under multiplication. Also, it may be
seen that H = {[1], [2], [4]} is a subgroup of G. The following are the left
cosets for H:
[1].H =
{[1], [2], [4]}
[2].H =
{[2], [4], [1]}
[3].H =
{[3], [6], [5]}
[4].H =
{[4], [1], [2]}
[5].H =
{[5], [3], [6]}
[6].H =
{[6], [5], [3]}
It can be
seen that [1].H = [2].H = [4].H; also [3].H = [5].H = [6].H; but [2].H and
[3].H are disjoint sets.
From above description
it can be obtained a partition of G:
{{[1], [2],
[4]}, {[3], [6], [5]}}
It can be verified
also that the set J = {[1], [6]} is another subgroup of G. The following are
the left cosets for J:
[1].J =
{[1], [6]}
[2].J =
{[2], [5]}
[3].J =
{[3], [4]}
[4].J =
{[4], [3]}
[5].J =
{[5], [2]}
[6].J =
{[6], [1]}
In this
case, [1].J = [6]. J, [2].J = [5].J, [3].J = [4].J; but the cosets [6].J ,
[5].J and [3].J have not elements in common. It can be obtained the
following partition of G: {{[1], [6]}, {[2], [5]}, {[3], [4]}}.
The
described partitions can be obtained in a different way: starting with the subgroup
H = {[1], [2], [4]}, take an element of G, not in H. If [3] is chosen, construct
the left coset [3].H = {[3], [6], [5]}. There are not any elements of G that
are not included in H or [3].H. So, the process has ended and a partition of G
has been obtained: {{[1], [2], [4]}, {[3], [6], [5]}}.
Similarly,
for the subgroup J = {[1], [6]}, an element of G not in J is [2]; the
corresponding left coset is [2]. J = {[2], [5]}. Now, take another element of
G, not in J or [2]. J; if [4] is chosen, [4]. J = {[4], [3]}. There are not any
elements of G that are not included in J or [2]. J or [4]. J. So, the process has
ended and a partition of G has been obtained: {{[1], [6]}, {[2], [5]}, {[3],
[4]}}.
The last
process described for above example can be generalized to obtain directly a
partition of a given group G. If G is a group and H is a subgroup of it, take
an element g1 of G, not in H and construct the left coset g1*H. Claim: H and
g1*H are disjoint sets. To prove this (by contradiction), suppose that a
belongs to H and g1*H. Then a = g1*h, for some h in H. As H is a group, h’, the
inverse of h, is in H. Then a*h´ is in H. That is, g1 is in H. But this
contradicts that the element g1 has been chosen out of H. The following note
shows details.
Note: As a
= g1*h, then a*h’ = (g1*h)*h’ = g1*(h*h’) = g1*e = g1. That is, a*h’ = g1.
Take an
element g2 in G which is not in H or g1*H, and construct g2*H. It can be shown,
as before, that H and g2*H are disjoint sets. Claim: g1*H an g2*H are disjoint
sets too. This will be shown by contradiction.
Suppose
that b is an element of G which belongs to g1*H and g2*h. Then b = g1*h1, for
some h1 in H, and b = g2*h2, for some h2 in H.
From g1*h1
= g2*h2 it follows that (g1*h1)*h2’ = g2 and g1*(h1*h2’) = g2. As h1 and h2 are
elements of subgroup H, h2’ is in H and h1*h2’ = h3, for some h3 in H.
It follows
that g*h3 = g2 is in H. But this contradicts what has been supposed before: g2
is not in H.
With the
same restrictions for g1, g2 there can be constructed the left cosets g3*H, …,
gk*H, where g1, g2, … gk are elements of G and k is not greater than n.
In this
process all the elements of G are used in the list of cosets without repetition
as it occurred in the first construction of left cosets in above example.
If gr*H =
gs*H for gr, gs in G, but not in H, or gr*H, or gs*H then gr*h1 = gs*h2 for some
h1 and h2 in H. In this case, (gr*h1)*h2’ = gs, that is gr*(h1*h2’) = gs that
is gr*ht = gs, for some ht in H. But then, gs is in gr*H, a contradiction with
previous statement.
As g1, g2, …, gk are chosen with the
conditions above described, any two of the left cosets g1*H, g2*H, …, gk*H are
disjoint sets.
The union
of all the left cosets of H, is G, since each element of G have been used. In
this process it has been obtained a partition of G.
If H has m
elements, the left coset g*H has m elements too. This means that all the left cosets
of H have the same number m of elements. The total number of left cosets (without
repetitions) is k.
As G has n
elements, and all of them have been used in the construction of the left cosets
of H, it follows that m.k = n.
This result
is known as Lagrange’s Theorem: If a finite group G has n elements, and H is a
subgroup of it with m elements, then m is a factor of n.
In above
discussion the concept of left coset of a subgroup has been used. It can be
repeated using the concept of right coset. This is necessary, from a strict
point of view, since this theorem is valid for a finite group G, abelian or
not.
