Groups

Groups
Groups
Integers mod n

Integers mod n
Recall that congruence modulo n is an equivalence relation
Also recall that there are n equivalence classes also known as
congruence classes. These are
[0] = {nk : k ∈ Z} , [1] = {1 + nk : k ∈ Z},
· · · , [n − 1] = {(n − 1) + nk : k ∈ Z}
When no confusion can arise, we will use 0, 1, · · · , n − 1 to
indicate the equivalence classes.
We will denote the set of these equivalence classes by Zn
Therefore Zn = {[0], [1] · · · , [n − 1]} (or equivalently if no
confuson arises Zn = {0, 1, · · · , n − 1}
Groups
Integers mod n
Integers mod n

Integers mod n
For two integers a and b, define addition modulo n to be

(a + b) (mod n)

that is, the remainder when a + b is divided by n.

Similarly, multiplication modulo n is defined as

(ab) (mod n)

, the remainder when ab is divided by n.

Therefore, we have
7+4≡1 (mod 5)
3+5≡0 (mod 8)
7×3≡1 (mod 5)
3×4≡0 (mod 6)
Note that it is possible that the product of two nonzero
numbers modulo n can be equivalent to 0 modulo n.
Groups
Integers mod n
Integers mod n

Integers mod n
Most, but not all, of the usual laws of arithmetic hold for
addition and multiplication in Zn
For instance, it is not necessarily true that there is a
multiplicative inverse. (Note that A non-zero element x ∈ Zn
has a multiplicative inverse if ∃y ∈ Zn [Link]. xy ≡ 1 (mod n)
To appreciate this observation, let’s consider the following
multiplication table for Z8
Groups
Integers mod n
Integers mod n

Integers mod n
. 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 2 5
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
6 0 6 4 2 0 6 4 2
7 0 7 6 5 4 3 2 1
Observe that only 1, 3, 5 and 7 are invertible (have inverses),
on the other hand 2, 4,6 have no inverses
Groups
Integers mod n
Integers mod n

Proposition
Let Zn be the set of equivalence classes of the integers (mod n)
and a, b, c ∈ Zn . Then
Addition and multiplication are commutative:
a + b ≡ b + a (mod n)
ab ≡ ba (mod n)
Addition and multiplication are associative:
(a + b) + c ≡ a + (b + c) (mod n)
(ab)c ≡ a(bc) (mod n)
There are both additive and multiplicative identities:
a + 0 ≡ a (mod n)
a.1 ≡ a (mod n)
Multiplication distributes over addition:
a(b + c) ≡ ab + ac (mod n)
Groups
Integers mod n
Integers mod n

Proposition contd.
For every integer a there is an additive inverse −a [Link].
a + (−a) ≡ 0 (mod n).
Let a be a nonzero integer. Then gcd(a, n) = 1 if and only if
there exists a multiplicative inverse b for a (mod n); that is, a
nonzero integer b such that ab ≡ 1 (mod n).
Groups
Integers mod n
Integers mod n

Proof
We will only prove the first and last result.
Addition is commutative modulo n since the remainder of
a + b divided by n is the same as the remainder of b + a
divided by n. Similarly the remainder of ab divided by n is the
same as the remainder of ba divided by n, hence
multiplication is commutative
Suppose that gcd(a, n) = 1. Then there exist integers r and s
such that ar + ns = 1.
Since ns = 1 − ar , it must be the case that ar ≡ 1 (mod n).
Letting b be the equivalence class of r , we have ab ≡ 1
(mod n).
Conversely, suppose that there exists an integer b such that
ab ≡ 1 (mod n). Then n divides ab − 1, so there is an integer
k such that ab − nk = 1. Let d = gcd(a, n). Since d divides
ab − nk, d must also divide 1; hence, d = 1.
Groups
Symmetry

Symmetry
A symmetry of a geometric figure is a rearrangement of the
figure preserving the arrangement of its sides and vertices as
well as its distances and angles.
For a rectangle, a rotation of 180◦ or 360◦ returns a rectangle
in the plane with the same orientation as the original
rectangle and the same relationship among the vertices.
A reflection of the rectangle across either the vertical axis or
the horizontal axis can also be seen to be a symmetry.
However, a 90◦ rotation in either direction cannot be a
symmetry unless the rectangle is a square.
Groups
Symmetry
Symmetry

Symmetry
Groups
Symmetry
Symmetry

Symmetries of an equilateral triangle

Consider an equilateral triangle ∆ABC . By considering the
permutations of the three letters A, B, C we observe that
there are at most 3! = 6 symmetries of ∆ABC .
To denote the permutation of the vertices of an equilateral
triangle that sends A to B, B to C, and C to A, we write the
array
 
A B C
B C A
In fact we obtain the following symmetries;
Groups
Symmetry
Symmetry

Symmetries of an equilateral triangle

Groups
Symmetry
Symmetry

Symmetries of an equilateral triangle

Groups
Symmetry
Symmetry

Symmetries of an equilateral triangle

Now what happens if one motion of the triangle ABC is
followed by another?
We consider µ1 and ρ1 and try to find out which symmetry is
µ1 ρ1 ; that is, what happens when we do the permutation ρ1
and then the permutation µ1 ?
We have
(µ1 ρ1 )(A) = µ1 (ρ1 (A)) = µ1 (B) = C
(µ1 ρ1 )(B) = µ1 (ρ1 (B)) = µ1 (C ) = B
(µ1 ρ1 )(C ) = µ1 (ρ1 (C )) = µ1 (A) = A
and this yields µ2 .
Observe (try it) that ρ1 µ1 = µ3 , as such ρ1 µ1 6= µ1ρ1
The complete multiplication table (also called Cayley table) is
as follows
Groups
Symmetry
Symmetry

Symmetries of an equilateral triangle

Groups
Symmetry
Symmetry

Symmetries of an equilateral triangle

Notice that in the multiplication table for the symmetries of
an equilateral triangle, for every motion of the triangle α there
is another motion β such that αβ = id;
That is, for every motion there is another motion that takes
the triangle back to its original orientation.
Groups
Definitions and Examples

Definition - Binary operation

A binary operation or law of composition on a set G is a function
G × G → G that assigns to each pair (a, b) ∈ G × G a unique
element a ◦ b, or ab in G , called the composition of a and b.
Groups
Definitions and Examples
Definitions and Examples

Definition - Group
A group (G , ◦) is a set G together with a law of composition
(a, b) → a ◦ b that satisfies the following axioms.
The law of composition is associative. That is,

(a ◦ b) ◦ c = a ◦ (b ◦ c)

for a, b, c ∈ G .
There exists an element e ∈ G , called the identity element,
such that for any element a ∈ G

e ◦ a = a ◦ e = a.

For each element a ∈ G , there exists an inverse element in G ,

denoted by a−1 , such that

a ◦ a−1 = a−1 ◦ a = e.
Groups
Definitions and Examples
Definitions and Examples

Note
Most of the time we will write ab instead of a ◦ b; however, if the
group already has a natural operation such as addition in the
integers, we will use that operation.

Definition - Abelian Group

A group G with the property that a ◦ b = b ◦ a for all a, b ∈ G is
called abelian or commutative. Groups not satisfying this property
are said to be nonabelian or non-commutative.
Groups
Definitions and Examples
Definitions and Examples

Examples
The integers Z = {· · · , −2, −1, 0, 1, 2, · · · } form a group
under the operation of addition.
The binary operation on two integers m, n ∈ Z is just their
sum. Since the integers under addition already have a
well-established notation, we will use the operator + instead
of ◦; that is, we shall write m + n instead of m ◦ n.
The identity is 0, and the inverse of n ∈ Z is written as n
instead of n−1 .
Notice that the set of integers under addition have the
additional property that m + n = n + m and therefore form an
abelian group.
Groups
Definitions and Examples
Definitions and Examples

Examples
The integers mod n form a group under addition modulo n.
Thus Zn is a group under addition mod n.
We consider Z5 , consisting of the equivalence classes of the
integers 0, 1, 2, 3 and 4.
We define the group operation on Z5 by modular addition.
We write the binary operation on the group additively; that is,
we write m + n.
The element 0 is the identity of the group and each element
in Z5 has an inverse. For instance, 2 + 3 = 3 + 2 = 0.
The following is a Cayley table for Z5 .
Groups
Definitions and Examples
Definitions and Examples

Examples
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
Groups
Definitions and Examples
Definitions and Examples

Examples
Not every set with a binary operation is a group.
For example, if we let modular multiplication be the binary
operation on Zn , then Zn fails to be a group.
The element 1 acts as a group identity since 1.k = k.1 = k
for any k ∈ Zn ; however, a multiplicative inverse for 0 does
not exist since 0.k = k.0 = 1 for every k in Zn .
Even if we consider the set Zn \ {0}, we still may not have a
group. For instance, let 2 ∈ Z6 . Then 2 has no multiplicative
inverse since
0.2 = 0, 1.2 = 2 2.2 = 4, 3.2 = 0, 4.2 = 2, 5.2 = 4.
Groups
Definitions and Examples
Definitions and Examples

Examples
Recall that every nonzero k does have an inverse in Zn if k is
relatively prime to n. Denote the set of all such nonzero
elements in Zn by U(n)
Then U(n) is a group called the group of units of Zn .
The following is a Cayley table for the group U(8)
. 1 3 5 7
1 1 3 5 7
3 3 1 7 5
5 5 7 1 3
7 7 5 3 1
Groups
Definitions and Examples
Definitions and Examples

Examples
The symmetries of an equilateral triangle form a nonabelian
group.
We will denote this group by either S3 or D3 .
Groups
Definitions and Examples
Definitions and Examples

Examples
M2 (R) denotes the set of all 2 × 2 matrices.
Let GL2 (R) be the subset of M2(R) consisting
 of invertible
a b
matrices; that is, a matrix A = is in GL2 (R) if
c d
there exists a matrix A−1 [Link]. AA−1 = A−1 A = I , where I is
a 2 × 2 matrix.
For A to have an inverse is equivalent to requiring that the
determinant of A be nonzero; that is, det A = ad − bc 6= 0.
The set of invertible matrices forms a group called the general
linear group.
 
1 0
The identity of the group is the identity matrix I =
0 1
Groups
Definitions and Examples
Definitions and Examples

Examples
 
d -b
The inverse of A ∈ GL2 (R) is A−1= 1
ad−bc -c a
The product of two invertible matrices is again invertible.
Matrix multiplication is associative, satisfying the other group
axiom.
For matrices it is not true in general that AB = BA, hence,
GL2 (R) is a nonabelian group.
Groups
Definitions and Examples
Definitions and Examples

Examples
    
1 0 0 1 0 i
Let 1 = ,I = ,J= ,
0 1 -1 0 i 0
 
i 0
K= where i 2 = −1.
0 -i
Then the relations I 2 = J 2 = K 2 = −1, IJ = K , JK = I , KI =
J, JI = −K , KJ = −I and IK = −J hold.
The set Q8 = {±1, ±I , ±J, ±K } is a group called the
quaternion group.
Notice that Q8 is noncommutative.
Groups
Definitions and Examples
Definitions and Examples

Examples
Let C∗ be the set of nonzero complex numbers.
Under the operation of multiplication C∗ forms a group.
The identity is 1.
If z = a + bi is a nonzero complex number, then z −1 = a−bi
a2 +b 2
is the inverse of z.
It is easy to see that the remaining group axioms hold.
Groups
Definitions and Examples
Definitions and Examples

Examples
A group is finite, or has finite order, if it contains a finite
number of elements; otherwise, the group is said to be infinite
or to have infinite order.
The order of a finite group is the number of elements that it
contains.
If G is a group containing n elements, we write |G | = n.
The group Z5 is a finite group of order 5;
The integers Z form an infinite group under addition, and we
sometimes write |Z| = ∞.
Groups
Basic Properties of Groups

Basic Properties of Groups - Proposition

The identity element in a group G is unique; that is, there exists
only one element e ∈ G such that eg = ge = g for all g ∈ G .

Basic Properties of Groups - Proof

Suppose that e and e 0 are both identities in G . Then eg = ge = g
and e 0 g = ge 0 = g for all g ∈ G . We need to show that e = e 0 . If
we think of e as the identity, then ee 0 = e 0 ; but if e 0 is the
identity, then ee 0 = e. Combining these two equations, we have
e = ee 0 = e 0 .
Groups
Basic Properties of Groups
Basic Properties of Groups

Basic Properties of Groups - Proposition

If g is any element in a group G , then the inverse of g , (denoted
by g −1 ), is unique.

Basic Properties of Groups - Proof

If g 0 and g 00 are both inverses of an element g in a group G , then
gg 0 = g 0 g = e and gg 00 = g 00 g = e. We want to show that
g 0 = g 00 . Now g 0 = g 0 e = g 0 (gg 00 ) = (g 0 g )g 00 = eg 00 = g 00 .
Groups
Basic Properties of Groups
Basic Properties of Groups

Basic Properties of Groups - Proposition

Let G be a group. If a, b ∈ G , then (ab)−1 = b −1 a−1 .

Basic Properties of Groups - Proof

Let a, b ∈ G . Then abb −1 a−1 = aea−1 = aa−1 = e. Similarly,
b −1 a−1 ab = e. But by the previous proposition, inverses are
unique; hence, (ab)−1 = b −1 a−1 .

Basic Properties of Groups - Proposition

Let G be a group. If a1 , a2 , · · · an ∈ G , then
(a1 a2 · · · an )−1 = an−1 · · · a2−1 a1−1 .
Groups
Basic Properties of Groups
Basic Properties of Groups

Basic Properties of Groups - Proposition

Let Let G be a group. For any a ∈ G , (a−1 )−1 = a.

Basic Properties of Groups - Proof

Observe that a−1 (a−1 )−1 = e.
Therefore we have that

(a−1 )−1 = e(a−1 )−1 = aa−1 (a−1 )−1 = a a−1 (a−1 )−1 = ae =
a.
Groups
Basic Properties of Groups
Basic Properties of Groups

Basic Properties of Groups - Proposition

Let G be a group and a and b be any two elements in G . Then the
equations ax = b and xa = b have unique solutions in G .

Basic Properties of Groups - Proof

Suppose that ax = b. We must show that such an x exists.
Multiplying both sides of ax = b by a−1 , we have
x = ex = a−1 ax = a−1 b.
To show uniqueness, suppose that x1 and x2 are both solutions of
ax = b, then ax1 = b = ax2 . So
x1 = ex1 = a−1 ax1 = a−1 ax2 = ex2 = x2 . The proof for the
existence and uniqueness of the solution of xa = b is similar.
Groups
Basic Properties of Groups
Basic Properties of Groups

Basic Properties of Groups - Proposition (right and left

cancellation laws)
If G is a group and a, b, c ∈ G , then ba = ca implies b = c and
ab = ac implies b = c.

Basic Properties of Groups

We can use exponential notation for groups just as we do in
ordinary algebra.
If G is a group and g ∈ G , then we define g 0 = e.
For n ∈ N, we define

g n = g .g · · · g (n times)

and
g −n = g −1 .g −1 · · · g −1 (n times)
Groups
Basic Properties of Groups
Basic Properties of Groups

Basic Properties of Groups - Theorem

In a group, the usual laws of exponents hold; that is, for all
g, h ∈ G,
1 g m g n = g m+n for all m, n ∈ Z;
2 (g m )n = g mn for all m, n ∈ Z;
3 (gh)n = (h−1 g −1 )−n for all n ∈ Z. Furthermore, if G is
abelian, then (gh)n = g n hn .

Basic Properties of Groups

If the group is Z or Zn , we write the group operation additively
and the exponential operation multiplicatively; that is, we write ng
instead of g n . The laws of exponents now become
1 mg + ng = (m + n)g for all m, n ∈ Z;
2 m(ng ) = (mn)g for all m, n ∈ Z;
3 m(g + h) = mg + mh for all n ∈ Z.