Math 111A
Lecture 1, Friday 9/23/22
Time Topic
10:00-10:15
Welcome to Math 111A!
• Course Overview and Expecations
• Office Hour Policy
• Textbook
• Grading Policy
• Homework, Regrades
10:15:10:20
The Basics: Prime Factorization and GCD, and Euler’s Totient Function
- Every positive integer x has a unique prime factorization: x = pn11 · · · pnrr , for some unique
primes p1 < p2 < · · · pn and unique positive integers n1, · · · , nr. -Let x, y ∈ Z−{0}. The
greatest common divisor of x and y, denoted gcd(x, y) or just (x, y) is the (unique) positive
integer d such that:
• d | x and d | y
• If e | x and e | y, then e | d.
- If (x, y) = 1, we say x and y are relatively prime.
- Ex: x = 360 = 23 · 32 · 5, y = 1350 = 2 · 33 · 52, then gcd(x, y) = 2 · 32 · 5 = 90
10:20:10:30
The Euler Totient Function
The Euler totient function is the function φ : Z+ → Z+ defined by φ(n) = |{a ∈ Z | 1 ≤
a ≤ x, (a, x) = 1}|.
Some facts:
• φ(p) = p− 1 if and only if p is prime.
• If p is prime, what is φ(pn)? The only numbers with a common factor are the multiples
of p, of which there are pn−1. Thus φ(pn) = pn − pn−1 = pn−1(p− 1).
• If (x, y) = 1, then φ(xy) = φ(x)φ(y). (We will prove this in 111B!) This allows you
to compute φ(n) easily if you know the prime factorization of n. φ(pn11 · · · pnrr ) =
φ(pn11 ) · · ·φ(pnrr ) = pn1−11 (p1 − 1) · · · pnr−1r (pr − 1).
10:30-10:35
The Division Algorithm
The Division Algorithm: Let x, y ∈ Z and let y 6= 0. Then ∃!q, r ∈ Z such that x = qy + r
and 0 ≤ r < y. (x is the dividend, y is the divisor, q is the quotient, r is the remainder.)
- To prove this, hold y fixed and use strong induction on x. Once you have proved the case
where x, y > 0, the other cases follow easily.
Ex: If we divide 360 by 1350, we obtain 360 = 0(1350) + 360. More interestingly, if we
divide 1350 by 360, we get 1350 = 3(360) + 270.
1
10:35-10:45
The Euclidean Algorithm
• Calculating the prime factorization of large integers is extremely difficult, even for
computers. However, there is an extremely fast way of computing the gcd, known as
Euclid’s algorithm.
• To calculate (x, y), divide x by y using the Division Algorithm to get x = q0y + r0.
• Then, rotate the terms: Divide y by r0 to get y = q1r0 + r1.
• Keep rotating: Given rk, divide rk−1 by rk to get rk−1 = qk+1rk + rk+1.
• Since y > r0 > r1 > · · · ≥ 0, eventually the remainder must be 0, and we get
rn−1 = qn+1rn.
• Then rn = (x, y).
Ex: Applying the Euclidean Algorithm to 1350 and 360), we get:
1350 = 3(360) + 270
360 = 1(270) + 90
270 = 3(90)
Thus (1350, 360) = 90, as we saw above.
Why does the Euclidean algorithm work? You can check that (x, y) = (y, r0) = (r0, r1) =
· · · = (rn−1, rn) = rn.
10:45-10:50
Bezout’s Lemma
Let x, y ∈ Z−{0}. Then there exist a, b ∈ Z such that (x, y) = ax+ by.
Ex: We can compute the coefficients a and b using the Euclidean Algorithm:
90 = 360 + (−1)270 = 360 + (−1)(1350 + (−3)(360) = (−1)1350 + 4(360)
2
Math 111A
Lecture 2, Monday 9/26/22
Time Topic
10:00-10:10
Equivalence Relations: The basics
• A relation∼ on a setA is any subset ofA×A. Usually, rather than writing (a, b) ∈∼,
we instead write a ∼ b.
• ∼ is reflexive if a ∼ a for all a ∈ A.
• ∼ is symmetric if a ∼ b implies b ∼ a for all a, b ∈ A.
• ∼ is transitive if a ∼ b and b ∼ c implies a ∼ c for all a, b, c ∈ A.
• ∼ is an equivalence relation if ∼ is reflexive, symmetric, and transitive. In this case,
∼ behaves similarly to the equals sign. If a ∼ b, we can think of a and b as being
“equivalent” or “the same” by some criterion.
• Example: Let P be the set of people in this class. Let a ∼ b if a and b have a first
name beginning with the same letter. Then ∼ is an equivalence relation.
• Example: Let n > 1 be an integer. For any x, y ∈ Z, we say x and y are congruent
mod n, written x ≡n y if n | x − y. It is easy to check that this is an equivalence
relation on Z.
10:10-10:25
Equivalence Classes
• If ∼ is an equivalence relation on A and a ∈ A, the equivalence class of a is the set
[a] = a := {b ∈ A | b ∼ a} of all elements of A which are equivalent to a.
• The quotient set of A by ∼ is the set A/ ∼:= {[a] | a ∈ A} of all equivalence classes
of A.
• Example: For the same-letter-of-first-name relation, [Jeremy Brightbill] is the set of all
people whose names start with “J”.A/ ∼ consists of (up to) 26 sets, one for each letter
of the alphabet. (If nobody’s name starts with “Z”, the corresponding set is absent.)
• Example: For ≡6, the equivalence class of 2 is [2] = {2 + 6k | k ∈ Z}. Z / ≡6=
Z /6Z has 6 equivalence classes: [0], [1], [2], [3], [4], [5]}.
• Prop: Let a, b ∈ P . Then [a] = [b] iff a ∼ b iff [a] ∩ [b] 6= ∅.
• Cor: A =
⋃
[a]∈A/∼
[a], and the sets in this union are mutually disjoint.
• Note that these results hold for both of our examples.
3
10:25-10:40
Functions on Equivalence Classes
• Consider the “function” f : Z /6Z → Z be given by f([a]) = a. This is not actually
a function, since it’s definition is self-contradictory. [1] = [7], so does f([1]) = 1
or does f([1]) = 7? The problem is that the output of f depends on the label (or
representative) of [a], but the same equivalence class can have many representatives
(any element of the set can be used as the representative).
• Definition: A candidate function f : A ∼→ B is well-defined if [a] = [b] implies that
f([a]) = f([b]). Whenever you define a function whose domain is a quotient set, you
need to prove that it is well-defined!
• Let S be the set of letters in the English alphabet. The function f : P/ ∼→ S given by
f([a]) = first letter of a’s first name is well-defined. The function g given by g([a]) =
first letter of a’s last name is (usually!) not.
• The function f : Z /6Z → Z /15Z given by f([x]) = [x] is not well-defined, but the
function g given by g([x]) = [5x] is well-defined.
10:40-10:50
Modular Arithmetic
• Define +, · : Z /nZ×Z /nZ→ Z /nZ by [a] + [b] = [a+ b] and [a][b] = [ab].
• Proposition: Both of these functions are well-defined.
• [x] ∈ Z /nZ is a zero divisor if there exists a nonzero [y] ∈ Z /nZ such that [x][y] =
0. [x] is a unit if there exists [y] ∈ Z /nZ such that [x][y] = [1]. The set of all units in
Z /nZ is denoted Z /nZ×.
• You will prove on the homework that [x] ∈ Z /nZ× if and only if (x, n) = 1.
4
Math 111A
Lecture 3, Wednesday 9/28/22
Time Topic
10:00-10:05
Definition of a Group
• A binary operation on a set G is a function · : G×G→ G. We usually write g1 · g2
instead of ·(g1, g2).
• A group is the data (G, ·) of a set G and a binary operation · on G, satisfying three
axioms:
– Associativity: ∀a, b, c,∈ G, (a · b) · c = a · (b · c). This allows us to write a · b · c,
since the parentheses don’t matter!
– Identity: ∃e ∈ G, ∀a ∈ G, a · e = a = e · a. e is called the identity element of
G.
– Inverses: ∀a ∈ G, ∃a−1 ∈ G, aa−1 = e = a−1a. a−1 is called the inverse of a.
• Commutativity: ∀a, b ∈ G, ab = ba. If G satisfies this additional axiom, we call G an
abelian or commutative group.
• If G is a finite set, we will call (G, ·) a finite group.
• We will mostly be studying finite groups this quarter, many of which will be non-
abelian!
10:05-10:30
Examples of Groups
• (Z,+), (Q,+), (R,+), (C,+) are abelian groups. The identity is 0, and the inverse
of x is −x.
• (Z+,+) is not a group. Why not?
• (Q−{0}, ·), (R−{0}, ·) ,(C−{0}, ·) are abelian groups. The identity is 1, and the
inverse of x is 1x .
• (Q, ·) is not a group. Why not?
• (Z−{0}, ·) is not a group. Why not?
• For any n > 1, (Z /nZ,+) is an abelian group, and so is (Z /nZ×, ·).
• Any vector space is an abelian group, under addition.
• A nonabelian example: Let F be a field, and letGLn(F) be the set of all n×n invertible
matrices. Then (GLn(F), ·) is a group which is not abelian.
• Another nonabelian example: Let S = {a, b}. The free group on S is the group
F (S) of all “words” consisting of the letters a, b, a−1, b−1. To compose two words,
we concatenate them and delete any strings of the form aa−1, etc. One can define the
free group on any set similarly.
5
10:30-10:35
Additive vs Multiplicative Notation
• Note that in our examples, both addition and multiplication can serve as the group
operation.
• We will use two different systems of notation to describe an arbitrary group: additive
and multiplicative notation.
• If I write + for the operation of a group G, I will always assume G is abelian, and I
will always write 0 for the identity and −x for the inverse of x.
• If I write · for the operation of G, the group may or may not be abelian. I will write e
for the identity, and x−1 for the inverse of x. I will also write ab instead of a · b. I will
always use multiplicative notation unless
• In an additive group, I will abbreviate x+ x+ · · ·x (n times) by nx. Similarly, I will
write (−n)x for −x+ (−x) + · · ·+ (−x) and 0x for 0.
• In a multiplicative group, I will write xn = x · x · · ·x, x−n = x−1x−1 · · ·x−1, and
x0 = e.
10:35-10:45
Basic Properties of Groups
Proposition: Let (G, ·) be a group. Then:
1) The identity element is unique.
2) The inverse of x ∈ G is unique.
3) For all a ∈ G, (a−1)−1 = a.
4) For all a, b ∈ G, (ab)−1 = b−1a−1.
5) For all a, b, x ∈ G, ax = bx⇒ a = b.
6) For all a, b, x ∈ G, xa = xb⇒ a = b.
Prove these!
10:45-10:50
Order of Elements
• Let (G, ·) be a group, and let x ∈ G. The order of x, denoted |x|, is the smallest
positive integer n such that xn = e. If such an n does not exist, then we write |x| =∞.
• Example: In any group, |x| = 1 if and only if x = e.
• In (Z,+), if x 6= 0, |x| =∞.
• In (Q−{0}, ·), | − 1| = 2. All other elements (except 1) have infinite order.
• In Z /6Z, |2| = |4| = 3, |3| = 2, |1| = |5| = 6, and |0| = 1.
• In Z /5Z×, |2| = |3| = 4, |4| = 2, |1| = 1.
• In GL2(R), the matrix
(
0 −1
1 0
)
has order 4.
6
Math 111A
Lecture 4, Friday 9/30/22
Time Topic
10:00-10:10
The Symmetric Group
• Let X be any set. Let SX := {f : X → X | f is a bijection}. An element of SX is
called a permutation of X .
• Note that composition is a binary operation on SX . With this operation, SX is called
the symmetric group on X .
• Proposition: (SX , ◦) is a group.
• The actual elements of X don’t really matter, only the number of elements. So, if
|X| = n, we might as well replace X with the set {1, · · · , n}. In this case, we denote
the group Sn, the symmetric group on n letters.
• What is |Sn|? Answer: n!
• The symmetric group is a very important group, and we would like to understand it
better.
• S1 is the trivial group, and S2 is the same thing as Z /2Z.
10:10-10:25
Notation and Cycles
• Let σ ∈ Sn. One way to describe σ is by simply writing down
all the inputs and outputs. Example: Consider σ ∈ S13 given by(
1 2 3 4 5 6 7 8 9 10 11 12 13
12 13 3 1 11 9 5 10 6 4 7 8 2
)
.
• This approach takes a lot of space! Is there a better way?
• A k-cycle in Sn is a list of k distinct integers in {1, · · · , n}. For each cycle
(x1x2, · · ·xk), there is a unique permutation which cyclically permutes the xi. That
is, it sends xi to xi+1 for 1 ≤ i < k and it sends xk to x1. All numbers not appearing
in the cycle are sent to themselves. We use the same notation for the cycle and the
permutation it describes.
• Note that we can cyclically permute the terms of a cycle without changing the under-
lying permutation. Thus (1234) = (2341) = (3412) = (4123).
• Cycles are very convenient ways to describe permutations: S3 =
{id, (12), (13), (23), (123), (132)}.
• Two cycles σ, τ are said to be disjoint if they have no integers in common. Note that
if σ, τ are disjoint cycles, then στ = τσ. For instance (12)(345) = (345)(12).
• Permutations which are not disjoint need not commute: (12)(23) = (123) and
(23)(12) = (132). Thus Sn is not abelian if n ≥ 3. (Note that S1 and S2 are abelian!)
• Not every permutation is a cycle. However, every permutation can be written uniquely
as a product of disjoint cycles (up to reordering the cycles and rotating the numbers
within a cycle)! Doing so is very easy: Apply the permutation to 1 until you get back
to 1. Then repeat for the next number which has not previously appeared. Use example
above.
7
10:25-10:35
The Dihedral Group
• A rigid motion in R3 is any function T : R3 → R3 which is a composition of a
rotation and a translation. If X ⊆ R3 is any set, a symmetry of X is a rigid motion T
such that T (X) = X . The composition of two symmetries is a symmetry, so the set
Sym(X) of all symmetries of X forms a group under composition.
• In general, Sym(X) can be very complicated, but we will study a simple special case.
Suppose X is a regular n-gon. In this case, we call Sym(X) the dihedral group of
order 2n, and write it D2n.
• Label the vertices of the n-gon by the numbers 1 through n, going clockwise. Note
that a symmetry of an n-gon must permute its vertices, and can therefore be described
by a permutation. However, not all permutations correspond to symmetries, since any
symmetry must send adjacent vertices to adjacent vertices.
• How many symmetries are there? We have n choices of where to send vertex 1, and 2
choices of where to send vertex 2. Once these choices are made, the rest of the vertices
are fixed in place. Thus there are 2n possible symmetries, and so |D2n| = 2n.
• Notice that n of the symmetries preserve the clockwise labeling of the vertices. These
symmetries are called rotations. The remaining n symmetries produce a counterclock-
wise labeling and are called reflections.
• Example: Describe the rotations and reflections of D6, D8.
10:35-10:45
Generators and Relations for D2n
• The dihedral groups are much simpler to understand and compute with than the sym-
metric groups. The key to understanding these groups is to examine two key elements.
• Let r denote the clockwise rotation by 2pin radians. This corresponds to the permutation
(123 · · ·n). Clearly, r is a rotation and |r| = n.
• Note that all n rotations are just the n different powers of r.
• Let s be the reflection about the line passing through vertex 1 and the center of the
n-gon. Clearly |s| = 2 and s is a reflection. s corresponds to the permutation
(2, n)(3, n− 1) · · · (bn+22 c, dn+22 e).
• Applying s produces a counterclockwise labeling. If we then apply the n different
rotations, we will obtain all of the counterclockwise-labeled symmetries. Thus all the
reflections are of the form ris.
• This describes all 2n elements of the dihedral group: D2n = {e =
r0, r, r2, · · · , rn−1, s, rs, r2s, · · · , rn−1s}.
• At first glance, multiplying elements of D2n seems tricky. (It is not very easy to
visualize!) However one key trick will allow us to do computations in D2n extremely
quickly. Since every element is just a product of r’s and s’s, all we need to do is figure
out how r and s interact with each other.
• Key Fact: rs = sr−1. Both symmetries map 1 to 2 and 2 to 1, so they must be equal!
Note also that sr = r−1s. (Multiply both sides by r on the left!)
• Examples in D10: rks = sr−k. (sr3)(sr2) = s2r−1 = r4. srksrk = id.
8
10:45-10:50
Presentation for D2n
• D10 is easy to work with because every element can be written as a product of two
symbols, r and s, and the entire multiplication table can be deduced from three simple
rules: rn = e, s2 = e, rs = sr−1. We can summarize this information as follows:
D2n = 〈r, s | rn = s2 = e, rs = sr−1〉. This is called a presentation of D2n by
generators and relations.
• Once we know the presentation of D2n, we can forget our original description of the
D2n in terms of symmetries of the n-gon, and simply view the group as a collection of
symbols obeying certain rules. All groups have presentations!
9
Math 111A
Lecture 5, Monday 10/3/22
Time Topic
9:00-9:10
The Dihedral Group
• A rigid motion in R3 is any function T : R3 → R3 which is a composition of a
rotation and a translation. If X ⊆ R3 is any set, a symmetry of X is a rigid motion T
such that T (X) = X . The composition of two symmetries is a symmetry, so the set
Sym(X) of all symmetries of X forms a group under composition.
• In general, Sym(X) can be very complicated, but we will study a simple special case.
Suppose X is a regular n-gon. In this case, we call Sym(X) the dihedral group of
order 2n, and write it D2n.
• Label the vertices of the n-gon by the numbers 1 through n, going clockwise. Note
that a symmetry of an n-gon must permute its vertices, and can therefore be described
by a permutation. However, not all permutations correspond to symmetries, since any
symmetry must send adjacent vertices to adjacent vertices.
• How many symmetries are there? We have n choices of where to send vertex 1, and 2
choices of where to send vertex 2. Once these choices are made, the rest of the vertices
are fixed in place. Thus there are 2n possible symmetries, and so |D2n| = 2n.
• Notice that n of the symmetries preserve the clockwise labeling of the vertices. These
symmetries are called rotations. The remaining n symmetries produce a counterclock-
wise labeling and are called reflections. (Give concrete example!)
9:10-9:20
Generators and Relations for D2n
• The dihedral groups are much simpler to understand and compute with than the sym-
metric groups. The key to understanding these groups is to examine two key elements.
• Let r denote the clockwise rotation by 2pin radians. This corresponds to the permutation
(123 · · ·n). Clearly, r is a rotation and |r| = n.
• Note that all n rotations are just the n different powers of r.
• Let s be the reflection about the line passing through vertex 1 and the center of the
n-gon. Clearly |s| = 2 and s is a reflection. s corresponds to the permutation
(2, n)(3, n− 1) · · · (bn+22 c, dn+22 e).
• Applying s produces a counterclockwise labeling. If we then apply the n different
rotations, we will obtain all of the counterclockwise-labeled symmetries. Thus all the
reflections are of the form ris.
• Thus, D2n = {e = r0, r, r2, · · · , rn−1, s, rs, r2s, · · · , rn−1s}.
• Multiplying elements of D2n is hard to visualize. However one key trick will allow us
to do computations in D2n extremely quickly. Since every element is just a product of
r’s and s’s, all we need to do is figure out how r and s interact with each other.
• Key Fact: rs = sr−1. Both symmetries map 1 to 2 and 2 to 1, so they must be equal!
Note also that sr = r−1s. (Multiply both sides by r on the left!)
• Examples in D10: rks = sr−k. (sr3)(sr2) = s2r−1 = r4. srksrk = id.
10
9:20-9:25
Presentation for D2n
• D10 is easy to work with because every element can be written as a product of two
symbols, r and s, and the entire multiplication table can be deduced from three simple
rules: rn = e, s2 = e, rs = sr−1. We can summarize this information as follows:
D2n = 〈r, s | rn = s2 = e, rs = sr−1〉. This is called a presentation of D2n by
generators and relations.
• Once we know the presentation of D2n, we can forget our original description of the
D2n in terms of symmetries of the n-gon, and simply view the group as a collection of
symbols obeying certain rules. All groups have presentations!
10:25-10:40
Subgroups
• Let (G, ·) be a group and H ⊆ G. We say H is a subgroup of G if
– H is nonempty
– H is closed under products: ∀x, y ∈ H,xy ∈ H
– H is closed under inverses: ∀x ∈ H,x−1 ∈ H
If H is a subgroup of G, we will often write H ≤ G (to indicate that it is not just a
subset).
• Prop: If H is a subgroup of (G, ·), then · defines a binary operation on H and (H, ·)
is a group.
• In any group G, {e} and G are subgroups. {e} is called the trivial subgroup.
• Let nZ = {nx | x ∈ Z}. Then nZ is a subgroup of Z.
• The intersection of two subgroups is always a subgroup. The union is almost never a
subgroup.
• Let S ⊆ G be any subset. We define 〈S〉 := {s1s2 · · · sn | n ≥ 0, si ∈ S or s−1i ∈ S}
to be the set of all “words” built from the letters of S and their inverses. (By definition,
we consider a length 0 word to be e.) It is easy to check that this is a subgroup. This
set is called the subgroup generated by S. You will prove that 〈S〉 is the smallest
subgroup of G containing S.
9:40-9:50
Lattice of Subgroups
• One way of understanding a group G is to find all of its subgroups, and understand
which subgroups are contained in which.
• We can draw a picture of these related subgroups, called the subgroup lattice of G.
• Find all subgroups of Z /6Z.
• Find all subgroups of Z /8Z.
• Find all subgroups of S3. (We can’t yet prove this is all of them.)
• Find all subgroups of D6. (We can’t yet prove this is all of them.)
11
Math 111A
Lecture 6, Wednesday 10/3/22
Time Topic
9:00-9:05
Group Homomorphisms
• In linear algebra, we studied a structure (vector spaces), as well as structure-preserving
maps between them (linear transformations). We continue this patter in group theory.
• Def: Let (G, ·), (H, ◦) be groups. A group homomorphism fromG toH is a function
f : G→ H satisfying two conditions:
– f preserves products: ∀x, y ∈ G, f(x · y) = f(x) ◦ f(y)
– f preserves inverses: ∀x ∈ G, f(x−1) = f(x)−1
• If f is also a bijection, then we call f an isomorphism. In this case, we say G and H
are isomorphic, and we write G ∼= H .
• Exercise: If f is a bijection, then f−1 : H → G is also a group homomorphism.
• Exercise: If f : G→ H is a group homomorphism, then f(eG) = eH .
9:05-9:15
Kernel and Image
• Let f : G→ H be a group homomorphism. The kernel of f is the set ker(f) := {x ∈
G | f(x) = e} of all elements which get sent to the identity element. (Effectively,
the kernel represents all information which is destroyed by the homomorphism.) The
image of f is the set im(f) := f(G) = {h ∈ H | ∃g ∈ G, h = f(g)}.
• Prop: ker(f) and im(f) are subgroups. f is injective iff ker(f) = {e}. f is surjective
iff im(f) = H .
• Recall: If |G| = |H|, then f : G → H is injective iff f is surjective iff f is bijective.
This is very false for infinite groups!
12
9:15-9:40
Examples
• Caution: For vector spaces, proving that a given map is linear was usually very easy.
For groups, it is harder. Checking that f(xy) = f(x)f(y) for every single x, y ∈ G is
tedious and impractical for large groups! Later, we will develop tools to make defining
homomorphisms easier.
• Let G be any group. The identity map idG : G→ G is an isomorphism.
• Let H ≤ G. The inclusion map i : H ↪→ G is an injective homomorphism.
• Let G,H be any groups. The trivial homomorphism f : G→ H is given by f(g) =
eH for all g ∈ G.
• Fix n ∈ Z. f : Z→ Z given by f(x) = nx is a group homomorphism.
• Fix n > 1, k ∈ Z. Let f : Z → Z /nZ be given by f(x) = [kx]. Then f is a
homomorphism.
• Consider the map f : Z /14Z → Z /6Z given by f([x]) = [3x]. Then f is a well-
defined group homomorphism.
• Define exp : R→ R× by exp(x) := ex. Then exp is a group homomorphism.
• Define f : D6 → Z /3Z by f(sirj) = [i + j], where 0 ≤ i ≤ 1, 0 ≤ j ≤ 3. f is not
a group homomorphism. For instance, f(s) + f(s) 6= f(s2) = f(e). The problem is
that s has order 2, but f(s) has order 3.
• Similarly, f : D6 → Z /3Z by f(sirj) = [j] is not a group homomorphism. f(rs) =
f(sr−1) = [−1] but f(r) + f(s) = [1]. r and s satisfy the equation rs = sr−1 holds
in D6, but f(r) and f(s) don’t satisfy the same equation.
• It turns out that f : D6 → Z /2Z 4 given by f(sirj) = [i] is actually a group homo-
morphism! So, it is not always easy to tell what is or is not a homomorphism just by
eyeballing it!
• f : Z /6Z → Z /3Z×Z /2Z given by f([x]6) = ([x]3, [x]2) is a well-defined group
homomorphism, which is also an isomorphism!
• If |X| = |Y |, then S(X) ∼= S(Y ). (Can you write down an isomorphism?)
• Every element σ ∈ D2n can be viewed as a permutation of the vertices of an n-gon.
Let f : D2n → Sn be the resulting function. Then f is an injective homomorphism.
When n = 3, |D6| = 6 = |Sn|, hence this map is also surjective, and so D6 ∼= S3!
9:40-9:45
Classification of Groups
• If two groups G and H are isomorphic, then G and H are the “same” group, just
written using different symbols. In particular, they should have the same cardinality,
the same number of subgroups, the same number of elements of order k, etc. Any
property G has should also be shared by H .
• Showing that two groups are isomorphic can be difficult, but showing that two groups
are not isomorphic is often quite easy.
• Ex: Z /4Z Z /2Z×Z /2Z, since only one of them has an element of order 4.
13
9:45-9:50
The Quaternion Group
• The Quaternion Group, denoted Q8 is a subgroup of GL2(C).
• Notation: Let 1 =
[
1 0
0 1
]
,−1 =
[−1 0
0 −1
]
, iˆ =
[√−1 0
0
√−1
]
, jˆ =[
0 −1
1 0
]
, kˆ =
[
0 −√−1√−1 0
]
• Q8 is the subgroup generated by iˆ and jˆ, that is Q8 = 〈ˆi, jˆ〉.
• It is easy to check that iˆ2 = jˆ2 = kˆ2 = −1, and that iˆjˆ = kˆ. From these rules, you
can deduce thatQ8 = {±1,±iˆ,±jˆ,±kˆ}, and you can deduce the entire multiplication
table (without ever using matrix multiplication!).
14
Math 111A
Lecture 7, Friday 10/7/22
Time Topic
BEFORE CLASS Write Lagrange’s Theorem on the board.
9:00-9:15
Cosets
• To prove Lagrange’s Theorem we will need some technical machinery.
• Let G be a group, H ≤ G be a subgroup, and let g ∈ G. The left coset of H in G
is the set gH := {gh | h ∈ H}. The right coset Hg is defined similarly. If G is an
additive group, we instead write g + H or H + g, and if G is abelian, these two sets
are the same!
• Let G/H := {gH | g ∈ G} denote the set of all left cosets of H in G. We call G/H
the (left) quotient of G by H . Similarly, H\G is the set of all right cosets. It doesn’t
matter whether you use left or right cosets; we will work with left ones.
• The index of H in G is the cardinality of G/H , which is denoted [G : H].
• Example: Let G = Z, H = 〈6〉 = 6Z. Then the cosets of 6Z (in additive notation)
are 0 + 6Z, 1 + 6Z, etc. Note that k + 6Z = [k]6, and that the quotient space Z /6Z
agrees exactly with our old notation.
• Example: LetG = D8 andH = 〈s〉. Then the cosets ofH are eH = sH , rH = rsH ,
r2H = r2sH , r3H = r3sH .
• Example: Let G = Q8 and H = 〈ˆi〉. Then the cosets of H are eH and jˆH .
• Proposition: Let G be a group, H ≤ G a subgroup. Then:
– Let h ∈ H . Then hH = H .
– Let g ∈ G. gH is subgroup of G if and only if g ∈ H .
– Let x, g ∈ G. Then x ∈ gH if and only if g−1x ∈ H .
9:15-9:30
Cosets and Equivalence Relations
• If H ≤ G is a subgroup, we can define a relation ≡H on G, called congruence mod
H . For x, y ∈ G, write x ≡H y if y−1x ∈ H .
• Proposition: ≡H is an equivalence relation on H . The equivalence class of g ∈ G is
precisely gH .
• Since we understand how equivalence relations work, we immediately deduce the fol-
lowing.
• Corollary: For x, y ∈ G, either xH ∩ yH = ∅ or xH = yH . The latter happens
precisely when x−1y ∈ H . Additionally, G =
⋃
gH∈G/H
gH .
• Check that this works for above examples.
15
9:30-9:40
Proof of Lagrange’s Theorem
• Proposition: Let H ≤ G and let g ∈ G. Then |gH| = |H|.
• Proof: Use left multiplication by g, g−1 to get a bijection. between the sets.
• Lagrange’s Theorem, Part 1 Let G be a finite group and let H be a subgroup. Then
|G| = |H| · [G : H]. In particular, |H| | |G|.
9:40-9:50
Order of Elements
• Proposition: Let x ∈ G. Let |x| = n < ∞. Then 〈x〉 = {e, x, x2, · · · , xn−1}, and
these elements are distinct.
• Proof: Use Division Algorithm
• Lagrange’s Theorem, Part 2 Let G be a finite group and let g ∈ G. Then |g| | |G|.
• Proof: Note that |g| = |〈g〉|.
• Application: Find all subgroups of D6.
16
Math 111A
Lecture 8, Monday 10/10/22
Time Topic
BEFORE CLASS Write Lagrange’s Theorem on the board.
9:00-9:15
Cosets
• To prove Lagrange’s Theorem we will need some technical machinery.
• Let G be a group, H ≤ G be a subgroup, and let g ∈ G. The left coset of H in G
is the set gH := {gh | h ∈ H}. The right coset Hg is defined similarly. If G is an
additive group, we instead write g + H or H + g, and if G is abelian, these two sets
are the same!
• Let G/H := {gH | g ∈ G} denote the set of all left cosets of H in G. We call G/H
the (left) quotient of G by H . Similarly, H\G is the set of all right cosets. It doesn’t
matter whether you use left or right cosets; we will work with left ones.
• The index of H in G is the cardinality of G/H , which is denoted [G : H].
• Example: Let G = Z, H = 〈6〉 = 6Z. Then the cosets of 6Z (in additive notation)
are 0 + 6Z, 1 + 6Z, etc. Note that k + 6Z = [k]6, and that the quotient space Z /6Z
agrees exactly with our old notation.
• Example: LetG = D8 andH = 〈s〉. Then the cosets ofH are eH = sH , rH = rsH ,
r2H = r2sH , r3H = r3sH .
• Example: Let G = Q8 and H = 〈ˆi〉. Then the cosets of H are eH and jˆH .
• Proposition: Let G be a group, H ≤ G a subgroup. Then:
– Let h ∈ H . Then hH = H .
– Let g ∈ G. gH is subgroup of G if and only if g ∈ H .
– Let x, g ∈ G. Then x ∈ gH if and only if g−1x ∈ H .
9:15-9:30
Cosets and Equivalence Relations
• If H ≤ G is a subgroup, we can define a relation ≡H on G, called congruence mod
H . For x, y ∈ G, write x ≡H y if y−1x ∈ H .
• Proposition: ≡H is an equivalence relation on H . The equivalence class of g ∈ G is
precisely gH .
• Since we understand how equivalence relations work, we immediately deduce the fol-
lowing.
• Corollary: For x, y ∈ G, either xH ∩ yH = ∅ or xH = yH . The latter happens
precisely when x−1y ∈ H . Additionally, G =
⋃
gH∈G/H
gH .
• Check that this works for above examples.
17
9:30-9:40
Proof of Lagrange’s Theorem
• Proposition: Let H ≤ G and let g ∈ G. Then |gH| = |H|.
• Proof: Use left multiplication by g, g−1 to get a bijection. between the sets.
• Lagrange’s Theorem, Part 1 Let G be a finite group and let H be a subgroup. Then
|G| = |H| · [G : H]. In particular, |H| | |G|.
9:40-9:50
Order of Elements
• Proposition: Let x ∈ G. Let |x| = n < ∞. Then 〈x〉 = {e, x, x2, · · · , xn−1}, and
these elements are distinct.
• Proof: Use Division Algorithm
• Lagrange’s Theorem, Part 2 Let G be a finite group and let g ∈ G. Then |g| | |G|.
• Proof: Note that |g| = |〈g〉|.
• Application: Find all subgroups of D6.
18
Math 111A
Lecture 9, Wednesday 10/12/22
Time Topic
9:00-9:10
Cyclic Groups: Elements
• Definition: A group G is cyclic if G = 〈x〉 for some x ∈ G.
• Proposition: Let G = 〈x〉 be a cyclic group. Then G = {xk | k ∈ Z}. If |x| = ∞,
then these elements are distinct. If |x| = n, then {e, x, x2, · · ·xn−1} are the distinct
elements of G.. In either case, |〈x〉| = |x|.
• Proof: The first statement was proved in the homework, and the second statement was
proved in the previous lecture.
9:10-9:25
Cyclic Groups: Isomorphism Class
• Theorem: Let G = 〈x〉 be a cyclic group. If |x| = ∞, then 〈x〉 ∼= Z. If |x| = n, then
〈x〉 ∼= Z /nZ.
• Proof: If |x| = ∞, the map φ : Z → 〈x〉 given by φ(k) = xk is clearly a surjective
homomorphism, and is injective since |x| =∞. If |x| = n, the map φ : Z /nZ→ 〈x〉
given by φ([k]) = xk is a well-defined, surjective homomorphism, and is injective
since the sets have the same cardinality.
• Notation: We write Zn for the cyclic group of order n, using multiplicative notation.
9:25-9:50
Cyclic Groups: Subgroups
• Theorem: Let 〈x〉 be a cyclic group. Then:
– If H ≤ 〈x〉 is a subgroup, then H is cyclic. If H 6= {e}, H = 〈xm〉 = 〈x−m〉,
where m = min{k ∈ Z+ | xk ∈ H}.
– If |x| =∞, the distinct subgroups of 〈x〉 are precisely 〈xm〉, m ≥ 0. All of these
subgroups have infinite order.
– If |x| = n, the distinct subgroups of 〈x〉 are precisely 〈xd〉, d > 0, d | n. This
subgroup has order nd .
• Proof: 1) Clearly the trivial group is cyclic, so assume H is nontrivial. Since H is
closed under inverses and nontrivial, it must contain some positive power of x, hence
m is defined. Since xm ∈ H , 〈xm〉 ⊆ H . For the reverse containment, take any
xk ∈ H . Dividing k by m, we obtain k = qm+ r for some q, r ∈ Z with 0 ≤ r < m.
Then xk = xqmxr, hence xr = xk(xm)−q ∈ H . To avoid contradicting the definition
of m, we must have r = 0. Thus k = qm and so xk = (xm)q ∈ 〈xm〉. Thus
H = 〈xm〉.
• 2) By part 1), every subgroup of 〈x〉 can be written in the form 〈xm〉, m ≥ 0. If
m,n > 0, and 〈xm〉 = 〈xn〉, then n | m and m | n, so m = n.
• 3) By part 1), every subgroup of 〈x〉 can be written in the form 〈xm〉, m ≥ 0. If
m 6= 0, let d = (n,m). I claim that 〈xm〉 = 〈xd〉. Since d | m, clearly xm ∈ 〈xd〉,
hence 〈xm〉 ⊆ 〈xd〉. Write d = am + bn for some a, b ∈ Z. Then xd = xam+bn =
xamxbn = xam. Thus xd ∈ 〈xm〉, so the reverse containment holds. Clearly |xd| = nd ,
so the various 〈xd〉 are distinct for the different factors of n.
19
Math 111A
Lecture 10, Friday 10/14/22
Time Topic
9:00-9:15
Introduction to Quotients
• Conisder the groupsZ andZ /nZ. In some sense, Z /nZ is the “same group” asG, but
with the added rule n = 0, which causes the group to collapse into a smaller structure.
Another way of looking at it is that all of the elements of Z /nZ have become zero.
• Given a group G and a subgroup H , what happens if we try to “collapse” H by adding
the rule that h = e for every element of H? This process is called “quotienting by H”
and is a useful way of building new groups from old ones.
• Example: In D6, let H = 〈s〉. If s = e, then the equation sr = r−1s becomes
r = r−1. Multiplying by r2, we have e = r. Thus if we “collapse” H , we actually end
up collapsing the entire group!
• The key issue: If we add the rule that h = e, then for every g ∈ G, we have the
additional consequence that gxg−1 = geg−1 = e, so we may accidentally end up
destroying more information than we intended.
9:15-9:30
Conjugation and Normality
• Definition: Let G be a group, and let g ∈ G. Define a function cg : G → G given
by cg(x) = gxg−1. The expression gxg−1 is called the conjugation of x by g. cg is
called conjugation by g.
• Based on the discussion above, if we destroy the element h ∈ G by introducing the
rule that h = e, we also destroy every conjugate of h.
• Prop: For any g ∈ G, cg is an automorphism of G (that is, an isomorphism from G to
itself).
• If H ≤ G is a subgroup and g ∈ G, the conjugate of H by g is the set gHg−1 =
{ghg−1 | h ∈ H}.
• Note that gHg−1 is a subgroup of G, which may or may not be equal to H .
• Example: Look at conjugates of subgroups in D6, Z.
• Note that if we quotient out by H , we also destroy every element of gHg−1 for every
g ∈ G. Thus, we can only avoid destroying “too much” information if gHg−1 = H
for every g ∈ G.
• Definition: Let G be a group and let N be a subgroup. We say N is normal in G if
gNg−1 = N for all g ∈ G. In this case we write N C G.
20
9:30-9:50
Quotient Groups
• Based on our discussion, if we “collapse” a normal subgroup N , we should destroy
only the information in N . Let us introduce a formal theory of quotients.
• Definition: Let G be a group and let N be a subgroup. Recall the quotient set G/N =
{gN | g ∈ G} is the set of all left cosets of N . Define a binary operation on G/N as
follows: (xN) · (yN) := xyN .
• Caution: There are multiple different ways of writing the same coset, so we need to
check that this operation is well-defined!
• Theorem: If N C G, then this operation is well-defined. G/N is a group under this
operation, called the quotient of G by N .
• Theorem: Let N C G. The function pi : G → G/N given by pi(x) = xN is a group
homomorphism. ker(pi) = N and im(pi) = G/N .
• Examples: Z /nZ. Describe D6/〈r〉. Describe Z20/〈x5〉.
21