3Lagrange's Theorem
IA Groups
3 Lagrange’s Theorem
One can model a Rubik’s cube with a group, with each possible move correspond-
ing to a group element. Of course, Rubik’s cubes of different sizes correspond to
different groups.
Suppose I have a 4
×
4
×
4 Rubik’s cube, but I want to practice solving a
2
×
2
×
2 Rubik’s cube. It is easy. I just have to make sure every time I make a
move, I move two layers together. Then I can pretend I am solving a 2
×
2
×
2
cube. This corresponds to picking a particular subgroup of the 4
×
4
×
4 group.
Now what if I have a 3
×
3
×
3 cube? I can still practice solving a 2
×
2
×
2
one. This time, I just look at the corners and pretend that the edges and centers
do not exist. Then I am satisfied when the corners are in the right positions,
while the centers and edges can be completely scrambled. In this case, we are
not taking a subgroup. Instead, we are identifying certain moves together. In
particular, we are treating two moves as the same as long as their difference is
confined to the centers and edges.
Let
G
be the 3
×
3
×
3 cube group, and
H
be the subgroup of
G
that only
permutes the edges and centers. Then for any
a, b ∈ G
, we think
a
and
b
are “the
same” if
a
−1
b ∈ H
. Then the set of things equivalent to
a
is
aH
=
{ah
:
h ∈ H}
.
We call this a coset, and the set of cosets form a group.
An immediate question one can ask is: why not
Ha
=
{ha
:
h ∈ H}
? In
this particular case, the two happen to be the same for all possible
a
. However,
for a general subgroup
H
, they need not be. We can still define the coset
aH
=
{ah
:
h ∈ H}
, but these are less interesting. For example, the set of all
{aH}
will no longer form a group. We will look into these more in-depth in the
next chapter. In this chapter, we will first look at results for general cosets. In
particular, we will, step by step, prove the things we casually claimed above.
Definition (Cosets). Let
H ≤ G
and
a ∈ G
. Then the set
aH
=
{ah
:
h ∈ H}
is a left coset of H and Ha = {ha : h ∈ H} is a right coset of H.
Example.
(i)
Take 2
Z ≤ Z
. Then 6 + 2
Z
=
{all even numbers}
= 0 + 2
Z
. 1 + 2
Z
=
{all odd numbers} = 17 + 2Z.
(ii) Take G = S
3
, let H = ⟨(1 2)⟩ = {e, (1 2)}. The left cosets are
eH = (1 2)H = {e, (1 2)}
(1 3)H = (1 2 3)H = {(1 3), (1 2 3)}
(2 3)H = (1 3 2)H = {(2 3), (1 3 2)}
(iii)
Take
G
=
D
6
(which is isomorphic to
S
3
). Recall
D
6
=
⟨r, s | r
3
e
=
s
2
, rs
=
sr
−1
⟩
.Take
H
=
⟨s⟩
=
{e, s}
. We have left coset
rH
=
{r, rs
=
sr
−1
}
and
the right coset Hr = {r, sr}. Thus rH = Hr.
Proposition. aH = bH ⇔ b
−1
a ∈ H.
Proof.
(
⇒
) Since
a ∈ aH
,
a ∈ bH
. Then
a
=
bh
for some
h ∈ H
. So
b
−1
a
=
h ∈ H.
(
⇐
). Let
b
−1
a
=
h
0
. Then
a
=
bh
0
. Then
∀ah ∈ aH
, we have
ah
=
b
(
h
0
h
)
∈
bH. So aH ⊆ bH. Similarly, bH ⊆ aH. So aH = bH.
Definition (Partition). Let
X
be a set, and
X
1
, · · · X
n
be subsets of
X
. The
X
i
are called a partition of
X
if
S
X
i
=
X
and
X
i
∩ X
j
=
∅
for
i
=
j
. i.e. every
element is in exactly one of X
i
.
Lemma. The left cosets of a subgroup
H ≤ G
partition
G
, and every coset has
the same size.
Proof.
For each
a ∈ G
,
a ∈ aH
. Thus the union of all cosets gives all of
G
. Now
we have to show that for all
a, b ∈ G
, the cosets
aH
and
bH
are either the same
or disjoint.
Suppose that
aH
and
bH
are not disjoint. Let
ah
1
=
bh
2
∈ aH ∩ bH
. Then
b
−1
a = h
2
h
−1
1
∈ H. So aH = bH.
To show that they each coset has the same size, note that
f
:
H → aH
with
f
(
h
) =
ah
is invertible with inverse
f
−1
(
h
) =
a
−1
h
. Thus there exists a bijection
between them and they have the same size.
Definition (Index of a subgroup). The index of
H
in
G
, written
|G
:
H|
, is the
number of left cosets of H in G.
Theorem (Lagrange’s theorem). If
G
is a finite group and
H
is a subgroup of
G, then |H| divides |G|. In particular,
|H||G : H| = |G|.
Note that the converse is not true. If
k
divides
|G|
, there is not necessarily a
subgroup of order
k
, e.g.
|A
4
|
= 12 but there is no subgroup of order 6. However,
we will later see that this is true if k is a prime (cf. Cauchy’s theorem).
Proof.
Suppose that there are
|G
:
H|
left cosets in total. Since the left cosets
partition G, and each coset has size |H|, we have
|H||G : H| = |G|.
Again, the hard part of this proof is to prove that the left cosets partition
G
and have the same size. If you are asked to prove Lagrange’s theorem in exams,
that is what you actually have to prove.
Corollary. The order of an element divides the order of the group, i.e. for any
finite group G and a ∈ G, ord(a) divides |G|.
Proof.
Consider the subgroup generated by
a
, which has order
ord
(
a
). Then by
Lagrange’s theorem, ord(a) divides |G|.
Corollary. The exponent of a group divides the order of the group, i.e. for any
finite group G and a ∈ G, a
|G|
= e.
Proof.
We know that
|G|
=
k ord
(
a
) for some
k ∈ N
. Then
a
|G|
= (
a
ord(a)
)
k
=
e
k
= e.
Corollary. Groups of prime order are cyclic and are generated by every non-
identity element.
Proof.
Say
|G|
=
p
. If
a ∈ G
is not the identity, the subgroup generated by
a
must have order
p
since it has to divide
p
. Thus the subgroup generated by
a
has the same size as
G
and they must be equal. Then
G
must be cyclic since it
is equal to the subgroup generated by a.
A useful way to think about cosets is to view them as equivalence classes.
To do so, we need to first define what an equivalence class is.
Definition (Equivalence relation). An equivalence relation
∼
is a relation that
is reflexive, symmetric and transitive. i.e.
(i) (∀x) x ∼ x (reflexivity)
(ii) (∀x, y) x ∼ y ⇒ y ∼ x (symmetry)
(iii) (∀x, y, z) [(x ∼ y) ∧ (y ∼ z) ⇒ x ∼ z] (transitivity)
Example. The following relations are equivalence relations:
(i) Consider Z. The relation ≡
n
defined as a ≡
n
b ⇔ n | (a − b).
(ii)
Consider the set (formally: class) of all finite groups. Then “is isomorphic
to” is an equivalence relation.
Definition (Equivalence class). Given an equivalence relation
∼
on
A
, the
equivalence class of a is
[a]
∼
= [a] = {b ∈ A : a ∼ b}
Proposition. The equivalence classes form a partition of A.
Proof.
By reflexivity, we have
a ∈
[
a
]. Thus the equivalence classes cover the
whole set. We must now show that for all
a, b ∈ A
, either [
a
] = [
b
] or [
a
]
∩
[
b
] =
∅
.
Suppose [
a
]
∩
[
b
]
=
∅
. Then
∃c ∈
[
a
]
∩
[
b
]. So
a ∼ c, b ∼ c
. By symmetry,
c ∼ b
.
By transitivity, we have
a ∼ b
. Now for all
b
′
∈
[
b
], we have
b ∼ b
′
. Thus by
transitivity, we have
a ∼ b
′
. Thus [
b
]
⊆
[
a
]. Similarly, [
a
]
⊆
[
b
] and [
a
] = [
b
].
Lemma. Given a group
G
and a subgroup
H
, define the equivalence relation
on G with a ∼ b iff b
−1
a ∈ H. The equivalence classes are the left cosets of H.
Proof. First show that it is an equivalence relation.
(i) Reflexivity: Since aa
−1
= e ∈ H, a ∼ a.
(ii) Symmetry: a ∼ b ⇒ b
−1
a ∈ H ⇒ (b
−1
a)
−1
= a
−1
b ∈ H ⇒ b ∼ a.
(iii)
Transitivity: If
a ∼ b
and
b ∼ c
, we have
b
−1
a, c
−1
b ∈ H
. So
c
−1
bb
−1
a
=
c
−1
a ∈ H. So a ∼ c.
To show that the equivalence classes are the cosets, we have
a ∼ b ⇔ b
−1
a ∈
H ⇔ aH = bH.
Example. Consider (
Z,
+), and for fixed
n
, take the subgroup
nZ
. The cosets
are 0 +
H,
1 +
H, · · ·
(
n −
1) +
H
. We can write these as [0]
,
[1]
,
[2]
· · ·
[
n
]. To
perform arithmetic “mod
n
”, define [
a
] + [
b
] = [
a
+
b
], and [
a
][
b
] = [
ab
]. We
need to check that it is well-defined, i.e. it doesn’t depend on the choice of the
representative of [a].
If [
a
1
] = [
a
2
] and [
b
1
] = [
b
2
], then
a
1
=
a
2
+
kn
and
b
1
=
b
2
+
kn
, then
a
1
+
b
1
=
a
2
+
b
2
+
n
(
k
+
l
) and
a
1
b
1
=
a
2
b
2
+
n
(
kb
2
+
la
2
+
kln
). So [
a
1
+
b
1
] =
[a
2
+ b
2
] and [a
1
b
1
] = [a
2
b
2
].
We have seen that (
Z
n
,
+
n
) is a group. What happens with multiplication?
We can only take elements which have inverses (these are called units, cf. IB
Groups, Rings and Modules). Call the set of them
U
n
=
{
[
a
] : (
a, n
) = 1
}
. We’ll
see these are the units.
Definition (Euler totient function). (Euler totient function) ϕ(n) = |U
n
|.
Example. If p is a prime, ϕ(n) = p − 1. ϕ(4) = 2.
Proposition. U
n
is a group under multiplication mod n.
Proof. The operation is well-defined as shown above. To check the axioms:
0.
Closure: if
a, b
are coprime to
n
, then
a · b
is also coprime to
n
. So
[a], [b] ∈ U
n
⇒ [a] · [b] = [a · b] ∈ U
n
1. Identity: [1]
2.
Let [
a
]
∈ U
n
. Consider the map
U
n
→ U
n
with [
c
]
7→
[
ac
]. This is injective:
if [
ac
1
] = [
ac
2
], then
n
divides
a
(
c
1
− c
2
). Since
a
is coprime to
n
,
n
divides
c
1
− c
2
, so [
c
1
] = [
c
2
]. Since
U
n
is finite, any injection (
U
n
→ U
n
) is also a
surjection. So there exists a c such that [ac] = [a][c] = 1. So [c] = [a]
−1
.
3. Associativity (and also commutativity): inherited from Z.
Theorem (Fermat-Euler theorem). Let n ∈ N and a ∈ Z coprime to n. Then
a
ϕ(n)
≡ 1 (mod n).
In particular, (Fermat’s Little Theorem) if
n
=
p
is a prime, then for any
a
not
a multiple of p.
a
p−1
≡ 1 (mod p).
Proof.
As
a
is coprime with
n
, [
a
]
∈ U
n
. Then [
a
]
|U
n
|
= [1], i.e.
a
ϕ(n)
≡
1
(mod n).