Groups and Group Actions: Lecture 6

In which we think about cyclic groups, and renew an old friendship with equivalence relations.

• Theorem 21: Let $G$ be a cyclic group.  Let $H$ be a subgroup of $G$.  Then $H$ is cyclic.  We proved this using the division algorithm.  We said that if $H$ contains something other than the identity, then we can pick the smallest positive integer $d$ with $g^d \in H$.  Clearly $\langle g^d \rangle \subseteq H$, and to show the reverse inclusion we used the division algorithm to argue that if $g^k \in H$ then $d$ divides $k$ and so $g^k \in \langle g^d \rangle$.
• Proposition 22: Let $m$, $n$ be integers.  Let $h$, $\ell$ be positive integers such that $\langle m, n \rangle = \langle h \rangle$ and $\langle m \rangle \cap \langle n \rangle = \langle \ell \rangle$.  Then
1. $h \mid m$ and $h \mid n$;
2. there are integers $a$, $b$ such that $am + bn = h$[Bézout‘s Lemma]
3. if $d \mid m$ and $d \mid n$, then $d \mid h$;
4. $m \mid \ell$ and $n \mid \ell$;
5. if $m \mid c$ and $n \mid c$, then $\ell \mid c$.

These were all reasonably straightforward to check. Parts (i), (ii), (iv) and (v) all had a similar flavour, whereas (iii) followed from (ii). For example, for (i) we said that $m \in \langle m, n \rangle = \langle h \rangle$, so $h \mid m$, and similarly for $n$.

• Definition of the highest common factor (hcf) and least common multiple (lcm) of two integers.
• Lemma 23: Let $G$ be a group.  Let $g \in G$ be an element with finite order $d$.  Then $g^k = e$ if and only if $d \mid k$.  One direction is almost immediate, for the other direction we used the division algorithm, in an argument of a familiar kind.
• Theorem 24 (Chinese Remainder Theorem): Let $m$, $n$ be coprime positive integers.  Then $C_m \times C_n$ is cyclic, and is isomorphic to $C_{mn}$.  We showed that if $C_m = \langle g \rangle$ and $C_n = \langle h \rangle$, then $(g,h) \in C_m \times C_n$ has order $mn$, using Lemma 23 and Bézout at appropriate points, and then noted that $C_m \times C_n$ is a group of order $mn$ containing an element of order $mn$.
• Definition of a (binary) relation on a set $S$.
• Definition of an equivalence relation.
• Proposition 25: Let $n \geq 2$ be an integer.  Define a relation $\sim$ on $\mathbb{Z}$ by $a \sim b$ if and only if $a - b$ is a multiple of $n$.  Then $\sim$ is an equivalence relation.  This was a routine check using the definition of an equivalence relation (we checked that $\sim$ is reflexive, symmetric and transitive).
• Definition of congruence modulo $n$.
• Definition of what it means for two elements of a group to be conjugate (building on a definition for permutations).
• Proposition 26: Let $G$ be a group.  Conjugacy in $G$ is an equivalence relation.  This was another routine check.

A student pointed out to me at the end of the lecture that I had at least one typo on the board (and very possibly more).  When we used the division algorithm (in the proofs of Theorem 21 and Lemma 23), I meant to write something like $g^r = g^{k - qd} = g^k (g^d)^{-q}$, but the minus sign in the final exponent might have been missing.  Very sorry if it caused any confusion, happily it doesn’t make a difference of any substance (apart from making the equation true…).

Understanding today’s lecture

I gave a couple of examples of equivalence relations (in addition to the ones in Propositions 25 and 26), can you show that they really are equivalence relations?

I’ve written about Bézout’s lemma (or theorem or whatever) before on this blog.  I’ve also written about the Chinese Remainder Theorem, phrased in a different way.  Linking that version of the theorem with the group theory one we saw today is a good exercise.

I mentioned that our work on highest common factors fits into a bigger and more general picture in rings.  You will learn lots more about this if you take the second-year Rings and Modules course (which has online notes available at that webpage).  The key concepts I mentioned were that of a ring, a Euclidean domain (that’s two links hidden in there), and a principal ideal domain.  You can read a little more about Euclid’s algorithm for the integers in my blog post on Bézout’s lemma (or theorem or whatever).

For an important approach to common factors, you should watch this short video by Vi Hart.

Preparation for Lecture 7

Remind yourself of the definition of an equivalence class.  Can you show that the equivalence classes for an equivalence relation form a partition of the set on which the relation is defined?  If I give you a partition, must it necessarily correspond to an equivalence relation?  You might want to use some of these ideas when working on Sheet 3, but you’ve had a sneak preview in the Introduction to University Level Maths course, which should help.

4 Responses to “Groups and Group Actions: Lecture 6”

1. Groups and Group Actions: Lecture 8 | Theorem of the week Says:

[…] I reminded you of what an equivalence relation is, I gave as an example the relation on a group , defined by if […]

2. Groups and Group Actions: Lecture 9 | Theorem of the week Says:

[…] .  Moreover, if is an isomorphism then .  We showed that , and then the first part follows using Lemma 23.  For the second part, we noted that if is injective then if and only if […]

3. Groups and Group Actions: Lecture 8 | Theorem of the week Says:

[…] here that and are coprime!)  Can you prove this?  There’s a nice connection with the Chinese Remainder Theorem.  You can read more about the function in a number theory book (such as The Higher Arithmetic by […]

4. Groups and Group Actions: Lecture 8 | Theorem of the week Says:

[…] here that  and  are coprime!)  Can you prove this?  There’s a nice connection with the Chinese Remainder Theorem.  You can read more about the function in a number theory book (such as The Higher Arithmetic by […]